java集合类主要分为两大体系，继承自Collection的List和Set,还有自己作为根的Map.大体的结构如下.
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
├HashSet
├TreeSet
Map
├Hashtable
├HashMap
└TreeMap
└WeakHashMap
Map
HashMap通过hash表实现的key-value存储，按照key的hashCode存储，可以有null key,
TreeMap是有序的，通过key的Comparable比较器实现key-value的有序存储
LinkedHashMap也是有序的，也是通过key的hashCode存储，但是遍历是增加了有序属性，即与加入的顺序保持一致
HashMap
HashMap是基于hash算法实现的，通过hash因子的作用，将元素"比较平均"的分散，以提高元素查找的命中率.具体的实现原理如下图：
HashMap是非线程安全的，允许null key,当threshold=capacity*loadfactor时会扩容为capacity<<1,这里capacity为桶的数量.
以下是put<k,v>()方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
可以看到优先判断null key，然后计算key的hash值，通过hash值与capacity结合判断位于Hash桶的位置,然后判断是否有当前key的Entry,如果存在，替换value为新值，并返回旧的value，否则添加一个新的Entry,并且返回null，如果一个桶已有至少一个Entry，则会作为链表的第一个元素插入.
HashTable
HashTable的原理与HashMap原理类似，只是比较特殊的所有操作加上了对当前对象操作的synchronized,以达到同步锁的功能，从而实现线程同步.
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}
从上可知,HashTable不允许加入null key,null value.
还有一个就是，HashTable初始容量是11.
Collection
Hashset
Hashset本应不在map系列,但由于Hashset的实现是基于HashMap实现的，所以这里列出，
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
从上可以看出,每次add一个元素，其实是将该元素当做一个key存入Hashmap中,value为一个"dummy value"(一个Object对象).所以其实是通过Hashmap保证了元素的唯一.
LinkedList与Queue
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可知LinkedList实现了Deque，而Deque是丰富了父接口Queue，
Queue是Collection接口的子类，Collection实现了Iterable,所以是可遍历的。
而Map没有实现Iterable，但是通过一系列方法如entrySet()等转换成集合类Set来实现遍历功能.
Arraylist
Arraylist的实现是基于数组的，初始数组大小为10,容量不足时扩展为原来的1.5倍.
Collections
Collections主要是作为集合方法的一些扩展，有大量的static方法，来帮助我们方便的处理集合，在其中主要摘两点做一些研究：
不变的empty集合
Collections含有很多的静态空集合方法，其实我们使用这些特性的地方无非有两处：
- 在自己的方法中
return null处return Collections.emptyList(),这样可以避免上层调用使用时发生NullPointException.
2.返回一个不可变(引用不可变)的集合实例.
@SuppressWarnings("unchecked")
public static final <T> List<T> emptyList() {
return (List<T>) EMPTY_LIST;
}
@SuppressWarnings("unchecked")
public static final List EMPTY_LIST = new EmptyList<>();
上面是返回emptyList的源码.
不变的empty迭代器
大多数空方法返回的是不变空集合，但是有以下三个方法返回的是空迭代器：<T> Enumeration<T> emptyEnumeration() (classic iteration method), <T> Iterator<T> emptyIterator(), and <T> ListIterator<T> emptyListIterator()
作用也无非上面返回空集合的那些作用.
@SuppressWarnings("unchecked")
public static <T> Iterator<T> emptyIterator() {
return (Iterator<T>) EmptyIterator.EMPTY_ITERATOR;
}
private static class EmptyIterator<E> implements Iterator<E> {
static final EmptyIterator<Object> EMPTY_ITERATOR
= new EmptyIterator<>();
public boolean hasNext() { return false; }
public E next() { throw new NoSuchElementException(); }
public void remove() { throw new IllegalStateException(); }
}
综上，我们可以得出结论，这些空方法可以帮助我们让编码更安全，防止空引用的发生。
Extend
ConcurrentModificationException while Iterating over ArrayList
3 ways to find duplicate elements in an array Java
网友评论