java集合主要有两类：Collection和Map。Collection接口主要有三个派生接口：Queue，List，Set，这三个派生接口又派生出很多实现类，总体来说，java集合的种类有这四个Queue，List，Set，Map。以下是这它们的关系图：
- 目录：
-
Collection集合
一. List
- ArrayList
- LinkedList
- Stack
- ArrayDeque
- LinkedList
- HashSet
- TreeSet
- LinkedHashSet
-
Map集合
一.HashMap
二.LinkedHashMap
三.TreeMap
四.HashTable
Collection集合
Iterable接口定义了iterator()方法，Queue，List，Set接口的实现类均实现了此方法，因此，Collection下所有集合都可以通过此方法获取Iterator 对象，从而遍历集合中的元素。
Iterable接口：
public interface Iterable<T> {
Iterator<T> iterator();
}
Iterator 遍历元素：
Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
}
一. List
List接口下的具体实现类大都实现了 Cloneable和java.io.Serializable接口，因此它们都拥有克隆和序列化的能力。
查看List接口提供的方法，可知List的一大特点是：可以通过下标来存取元素（索引存取）
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
1. ArrayList
ArrayList内部定义一个数组，用于保存元素。如果插入的时候不指定下标，将会按照数组下标顺序插入。
//无参构造函数。创建一个空数组，在第一次add元素时，会判断是否需要扩容，此时会设置默认容量大小为10，再执行arraycopy的操作，也就创建了容量为10的数组。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = ;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//有参构造函数，创建指定容量的数组
public ArrayList(int initialCapacity) {
if (initialCapacity > ) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == ) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//不指定下标插入。判断是否需要扩容，再插入数组的末尾。
public boolean add(E e) {
ensureCapacityInternal(size + ); // Increments modCount!!
elementData[size++] = e;
return true;
}
//指定下标插入。判断是否需要扩容，再拷贝移动元素并插入。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + ); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + , size - index);
elementData[index] = element;
size++;
}
//判断是否需要扩容，如果此时elementData仍然为空（首次创建无参ArrayList时），设置默认容量大小为DEFAULT_CAPACITY = 10
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > )
grow(minCapacity);
}
//扩容，重新计算容量大小（之前容量的1.5倍），重新创建一个新的数组，并把之前数组中的元素拷贝到新的数组中。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> );
if (newCapacity - minCapacity < )
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > )
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
//ArrayList中数组容量的最大值设定为MAX_VALUE = 2^(32-1)-1
private static int hugeCapacity(int minCapacity) {
if (minCapacity < ) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - ;
public E get( int index) {
rangeCheck(index);
return elementData(index);
}
Arrays.java
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, , copy, ,
Math.min(original.length, newLength));
return copy;
}
查看以上源码，ArrayList在插入元素时，会先检查ArrayList的容量是否足够，如果容量不足，将会进行扩容。扩容时会重新创建一个新的数组，并把之前数组中的元素拷贝到新的数组中。插入指定下标的元素时，会拷贝并移动元素。跟扩容时一样，使用了System.arraycopy()进行了拷贝和移动。
ArrayList的时间复杂度：
get(int index)，add(E e)，时间复杂度为O(1)
add(int index, E element)，remove(int index)，remove(Object o)，indexOf(Object o)，时间复杂度为O(n)
2. LinkedList
LinkedList继承自List和Queue，它是一个双向队列的集合。LinkedList的实现方式不再是操作数组，而是通过双向链表实现。每个元素的插入都生成一个Node对象保存，并各自指向前后两个Node对象。可以使用LinkedList来实现队列，双向队列，堆栈等数据结构。另外，由于LinkedList也继承自List，它也包含了List的特点，可以通过下标存取元素。
//定义Node类。item用来保存元素，Node的引用prev，next用来指向上一个节点，下一个节点。
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
public boolean add(E e) {
linkLast(e);
return true;
}
//从First端插入元素
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//从Last端插入元素：
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
//从First端获取第一位元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//从Last端获取第一位元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//获取指定下标的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//在指定下标插入元素
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
我们知道链表里面一般是没有下标（索引）的概念，那么这里是怎么实现下标存取的呢？ 关键就在这个node()方法，在get()和set()方法中，都使用这个node()方法来定位元素。node()方法通过遍历链表元素，并计数索引的方法，来支持LinkedList中的索引存取。如下：
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> )) {
Node<E> x = first;
for (int i = ; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - ; i > index; i--)
x = x.prev;
return x;
}
}
LinkedList的时间复杂度：
getFirst()，getLast()，removeFirst()，removeLast()，addFirst(E e)，addLast(E e)，时间复杂度为O(1)
add(int index, E element)，set(int index, E element)，remove(int index)，get(int index)，时间复杂度为O(n)
3. Stack
Stack继承自Vector，它的功能实现依赖于vector。先来看看vector与ArrayList的区别：
- vector扩容时是原来容量的2倍。ArrayList扩容时是原来容量的1.5倍。
- vector中的多数方法都加了synchronized来修饰，是线程安全的。而ArrayList是线程不安全的。
- vector是已经过时的类，为了支持老的程序，vector中有大量功能重复的冗余方法
除了这几点，vector中功能的现实基本和ArrayList一样，因此可以把vector当成ArrayList来看。vector中也是定义一个数组，来保存元素，如果插入的时候不指定下标，将会按照数组下标顺序插入。
Stack继承了Vector的线程安全特性，因此，在性能上比较低，如果不考虑线程安全的问题的话，不建议使用Stack来实现堆栈，应该使用LinkedList来替代。
Stack在取元素的时候，总是从数组保存的最后一个元素取。见pop()方法。
public E push(E item) {
addElement(item);
return item;
}
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + );
elementData[elementCount++] = obj;
}
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - );
return obj;
}
public synchronized E peek() {
int len = size();
if (len == )
throw new EmptyStackException();
return elementAt(len - );
}
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < ) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - ;
if (j > ) {
System.arraycopy(elementData, index + , elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
Stack的时间复杂度：
push(E item)， pop()， peek()，时间复杂度为O(1)
search(Object o)，时间复杂度为O(n)
二. Queue
1. ArrayDeque
ArrayDeque也是一个双向队列的集合。不同于LinkedList，它的实现方式是使用数组。通过操作下标，把分配到的数组当成一个循环的数组来插入和删除元素。
transient int head;
transient int tail;
public boolean add(E e) {
addLast(e);
return true;
}
//从First端添加新元素（其实就是数组末尾），如果head和tail下标相同，说明数组已经使用完，需要扩容
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - ) & (elements.length - )] = e;
if (head == tail)
doubleCapacity();
}
//从Last端添加新元素（其实就是数组开头），如果head和tail下标相同，说明数组已经使用完，需要扩容
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + ) & (elements.length - )) == head)
doubleCapacity();
}
//扩容,重新计算容量（之前容量的两倍）创建一个新的数组，并把之前数组的元素拷贝到新数组中
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << ;
if (newCapacity < )
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, , r);
System.arraycopy(elements, , a, r, p);
elements = a;
head = ;
tail = n;
}
//从First端（数组末尾）取元素
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
//从Last端（数组开头）取元素
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - ) & (elements.length - )];
if (result == null)
throw new NoSuchElementException();
return result;
}
循环数组的理解，我们可以重点看addFirst()方法和addLast()方法，head和tail两个下标在ArrayDeque对象创建的时候并没有初始化，只是进行了定义，那么默认值都为0，如果一直使用addFirst()插入数据，那么addFirst()中head下标的变化为：
elements[head = (head - 1) & (elements.length - 1)] = e;
假定定义一个elements.length = 6的数组，
head = 0；
head = (0-1) & (6-1) = -1 & 5 = 5
head = (5-1) & (6-1) = 4 & 5 = 4
head = (4-1) & (6-1) = 3 & 5 = 3
head = (3-1) & (6-1) = 2 & 5 = 2
head = (2-1) & (6-1) = 1 & 5 = 1
head = (1-1) & (6-1) = 0 & 5 = 0
其实addFirst()就是从数组末尾执行的插入。
同理，addLast()方法中tail下标的变化为：
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
tail = 0;
tail = (0+1) & (6-1) = 1 & 5 = 1
tail = (1+1) & (6-1) = 2 & 5 = 2
tail = (2+1) & (6-1) = 3 & 5 = 3
tail = (3+1) & (6-1) = 4 & 5 = 4
tail = (4+1) & (6-1) = 5 & 5 = 5
addLast()就是从数组0下标开始插入元素。
如果同时在两端插入数据，那head和tail下标总会有相等的时候，说明数组容量不够了，这时候就需要扩容了。另外，ArrayDeque虽然使用了数组来存储元素，但是并没有提供索引存取的功能。
ArrayDeque的时间复杂度：
addFirst(E e)，addLast(E e)，pollFirst()，pollLast()，getFirst()，getLast() ，removeFirst()，removeLast()，由于ArrayDeque为循环数组，并没有提供索引存取的功能，因此，这些方法的时间复杂度都为O(1)
remove(Object o)，contains(Object o)，时间复杂度为O(n)
ArrayDeque和LinkedList都可以实现队列的数据结构，如果只是在首尾两端插入删除查询元素，ArrayDeque的效率要高一些。ArrayDeque不能使用索引，这个应该要注意。
2. LinkedList
…..见List中的介绍
三. Set
Set的实现多数需要依赖于Map。Map的设计是使用键值对存取，对于很多应用场景，我们并不需要这个结构来存储数据，设计Set的初衷就是为了可以简化Map，并且可以使用迭代器Iterator。比如
- HashSet，借助于HashMap散列表的设计，Hashset可以用来去重。
- TreeSet借助于TreeMap实现红黑树的数据结构。
- LinkedHashSet借助于LinkedHashMap实现了HashSet的排序。
以上Set的子类都实现了Map中的功能，但是又不需要键值对这种麻烦的数据存取形式，使用起来相当的简便。个人理解。
1. HashSet
为快速查找而设计的Set，因为设定的是快速查找，所有并没有获取HashSet内元素的直接方法get()，必须通过Iterator迭代器来获取元素。
HashSet的现实依赖于HashMap，从HashSet中存入的元素被当做HashMap中的key健值，因此必须要重写hashCode()方法和equals()方法。如果HashSet中存入相同的元素（hashCode()和equals()相同），则会发生元素覆盖。
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
2. TreeSet
保持次序的Set，底层为树形结构。因为要保持元素的有序，因此元素必须要实现Comparable接口，并重写compareTo()方法，否则将会抛出ClassCastException异常。
TreeSet的实现依赖于TreeMap。
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public E first() {
return m.firstKey();
}
public E last() {
return m.lastKey();
}
3. LinkedHashSet
具有HashSet的查询速度，且内部使用链表维护元素的插入顺序。
LinkedHashSet的实现依赖于LinkedHashMap。
public LinkedHashSet() {
super(, f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
Map集合
HashMap，LinkdeHashMap，TreeMap，HashTable均实现了 Cloneable和java.io.Serializable接口，因此它们都拥有克隆和序列化的能力。
Map使用了键值对的形式来保存元素。
由于Map接口没有继承Iterable接口，因此，它不能使用迭代器来遍历集合。但是，Map可以通过Set来使用迭代器。如下：
Iterator iterator = map.entrySet().iterator();//map.keySet().iterator()
while (iterator.hasNext()){
Objects obj = iterator.next();
}
其原理是使用了内部类机制。这里有两个内部类AbstractSet和Iterator，在keySet()被调用时，keySet 被初始化，并获得了外部类Map的引用（内部类可以访问外部类的所有数据成员和方法）。在迭代器Iterator的方法被调用时，匿名内部类Iterator也获得外部类Map和keySet 中的引用，可以访问map和set中的所有数据成员和方法，接下来执行的next()涉及的Entry其实就是Map中的数据，里面包含了指向下一个对象的引用，遍历即可得到所有的键值对。
public Set<K> keySet() {
if (keySet == null) {
keySet = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
}
return keySet;
}
一.HashMap
之前的集合要么是使用数组来实现，要么是使用链表来实现。HashMap集合的实现既使用了数组，同时还使用了链表，能结合这两种一起使用的方式就是散列。
散列：
假如键没有按照一定的顺序进行保存，那么查询的时候就只能按照顺序进行线性查询，然而，线性查询是最慢的查询方式。所以，将键值按照一定的顺序排序，并且使用二分查找能购有效的提升速度。散列在此之上，更近一步，他将键保存在数组中(数组的查询速度最快)，用数组来表示键的信息，但是由于Map的容量是可变的，而数组的容量是不变的。要解决这个问题，数组中存的并不是键本身，而是键对象生成的一个数字，将其作为数组的下标，这个数字就是散列码hashcode。
不同的健对象，有可能会产生相同的散列码，这通常也叫做哈希冲突（碰撞）。如下：
产生哈希冲突后，多个键值对（Node节点）会被保存同一个hashcode所代表的链表里面，将会影响这个Map集合的性能。如果每个hashcode所代表的链表只保存了一个键值对（数组中的Node节点），那么这个Map集合的性能将会是最完美的。所以，当我们需要把自己设计的类当成健来保存键值对，必须要重写hashCode()和equals()方法。equals()方法的重写需要满足以下条件：
- 自反性 x.equals(x) 一定返回true
- 对称性 x.equals(y)返回true，则y.equals(x) 也返回true
- 传递性 x.equals(y)返回true,y.equals(z)返回true,则x.equals(y)返回true
- 一致性 如果对象中的信息没有改变，x.equals(y)要么一直返回true，要么一直返回false
- 对任何不是null的x，想x.equals(null)一定返回false
重写hashCode()方法，最重要的因素就是：
- 无论何时，对同一个对象调用hashCode()都应该生成同样的值。
- hashCode()返回的值应该尽量分布均匀。
HashMap中定义了Node和TreeNode节点来保存键值对，为了能成功散列，Node中还定义了一个int类型的hash变量来保存散列码。一般数组是通过下标来存取元素，这里使用了散列码来替代下标的功能。根据健对象生成的散列码来确定数组中的位置。
transient Node<K,V>[] table; //Node节点的数组
final float loadFactor;//负载因子
//默认的负载因子为DEFAULT_LOAD_FACTOR = 0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//保存键值对。HashMap的构造方法中并没有初始化table数组，table的初始化在第一次put()时由resize()方法执行。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//table为null，说明HashMap对象刚创建，调用resize()进行table数组的初始化。
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;
//根据hash值找到在数组table中的对应位置，如果此位置没有值，说明没有保存过此key的键值对，保存此键值对。
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//根据hash值找到在数组table中的对应位置，但是此位置已经存有值。说明发生了哈希碰撞，需要判断是保存到单链表中还是红黑树中。
else {
Node<K,V> e; K k;
//发生了哈希碰撞，且在table数组中发现hash值，健值相同，说明相同key的键值对已经存在，直接覆盖。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/*发生了哈希碰撞，且检查到table数组中保存的是TreeNode类型，说明此后的元素都是以红黑树的形式保存，接下来要遍历红黑树。
* 如果在红黑树中找到了hash值，健值相同的元素，直接覆盖。如果遍历结束后，仍然没有找到hash值，健值相同的元素，说明没有保存过此
* key的键值对，添加到红黑树中。这个过程的实现在putTreeVal()方法中，不再细讲。
*/
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
/*发生了哈希碰撞，且检查到table中保存的不是TreeNode类型，那么就只能是单链表结构了。检查单链表，如果相同key的键值对
*已经存在，直接覆盖，如果相同key的键值对不存在，则添加。
*/
else {
//遍历单链表
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) { //遍历至链表尾部
p.next = newNode(hash, key, value, null); //元素封装到Node对象中，加入到单链表结构
//红黑树的性能要比单链表高，因此，如果单链表的长度大于TREEIFY_THRESHOLD - 1的时候，单链表转化成红黑树
if (binCount >= TREEIFY_THRESHOLD - ) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//hash值，健值相同，说明相同key的键值对已经存在，直接覆盖。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//相同key的键值对已经存在，返回value值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//threshold的值由负载因子loadFactor决定。判断是否需要扩容。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/*给table数组初始化，并判断是否需要扩容。如果需要扩容，则需要保存旧的table数组的元素，然后table数组进行两倍扩容，
*再把旧table数组的元素保存到新table数组中，并且，旧table数组中所指向的单链表，红黑树结构要链接到新的table数组中。
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? : oldTab.length;
int oldThr = threshold;
int newCap, newThr = ;
if (oldCap > ) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << ; // double threshold
}
else if (oldThr > ) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == ) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - )] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == ) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
//获取指定key的键值对。如果可以从table数组中获取，则直接返回，如果table数组中获取不到，则需要遍历相应hashcode下的单链表或者红黑树。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > &&
(first = tab[(n - ) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
负载因子：
空表的负载因子是0，而半满表的负载因子是0.5，HashMap中的默认负载因子是0.75，也就是四分之三满。如果HashMap的容量不足时（table数组的容量），会自动进行扩容，并重新将现有的对象分布到新的table集中，这个称之为再散列。是否需要扩容的判断依赖于负载因子，更高的负载因子可以降低所需的空间，但是会增加查找的代价。默认的负载因子0.75在时间和空间代价之间达到了平衡。
resize():
if (newThr == ) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
putVal():
if (++size > threshold)
resize();
二.LinkedHashMap
LinkedHashMap的特点是可以得到可以通过迭代它获取有序的HashMap集合。重点是有序。
LinkedHashMap继承自HashMap，重写了get()，afterNodeAccess()，newTreeNode()和newNode()方法（重要），put()方法则是直接继承自HashMap。当我们new一个LinkedHashMap对象后，使用LinkedHashMap对象的引用调用put()方法时，putVal()方法中调用的newNode()方法并不是HashMap中的方法，而是LinkedHashMap中的newNode()方法，这里使用了多态的机制。putVal()方法参见HashMap中的介绍，不再列出。
afterNodeAccess()在HashMap中也有定义，不过并没有具体的实现。afterNodeAccess()在putVal()中也被调用了，如下：
往HashMap中插入键值对时，如果key相同的键值对已经存在，直接覆盖此键值对，并把此键值对移动到LinkedHashMap维护的双向链表中（注意，不要跟HashMap中的单链表和红黑树混淆），并返回value值。由于HashMap中并没有定义afterNodeAccess()，如果是HashMap对象调用此方法，则什么都不会发生，这里的afterNodeAccess()主要是扩展给实现此方法的子类使用的：
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
accessOrder = false : 按插入顺序排序（LRU）
accessOrder = true : 按访问顺序排序
//头尾引用，用来构建双向链表
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder; //排序方式，默认值为false
public LinkedHashMap() {
super();
accessOrder = false;
}
//重写newNode()方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
//重写newTreeNode()方法
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
//链接双向节点
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
/*根据key获取键值对时，如果accessOrder = true(按访问顺序排序)，则把此键值对移动至LinkedHashMap维护的双向链表的末尾，
*并返回此键值对。如果accessOrder = false(按插入顺序排序),直接返回此键值对。
*/
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
//把传入的键值对移动至链表的尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
LinkedHashMap主要功能就是维护自己的双向链表，使得HashMap中的键值对变得有序。在维护双向链表时，head固定在首个插入的键值对上，tail按照插入键值对的顺序，逐个移动。所以，不需要做多余的操作，从head开始逐个取出键值对就可以达到”按插入顺序排序”的效果，因此accessOrder = false。查看以下取出所有LinkedHashMap中的键值对方法：
Iterator iterator = linkedHashMap.entrySet().iterator();
while (iterator.hasNext()){
Objects obj = iterator.next();
}
使用迭代器获取所有的key信息：LinkedKeyIterator
使用迭代器获取所有的value信息：LinkedValueIterator
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
//构造方法，next指向了head引用
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
如果想要达到”按访问顺序排序”的效果，就需要对访问时的键值对做处理，这里是把访问的键值对移动到LinkedHashMap维护的双向链表的末尾。按照上面迭代器的方式获取所有LinkedHashMap中的键值对，由于迭代器是从head开始取值，因此，我们需要在迭代器获得的结果中再反向取值就OK了
三.TreeMap
TreeMap仅使用了链表来实现，其数据结构是红黑树。HashMap根据key健值产生的散列码和key健值equals()方法来确定键值对是否重复，而TreeMap则是使用了Comparable比较器来确定健值是否重复。
TreeMap所得到的结果是经过排序的，其排序规则来自Comparable比较器，用户可以自己定义Comparable比较器，如果不定义，将会使用默认的规则来排序。
//无参构造函数，Comparable对象为null，默认规则排序
public TreeMap() {
comparator = null;
}
//根据key值获取键值对，遍历左子树，右子树
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < )
p = p.left;
else if (cmp > )
p = p.right;
else
return p;
}
return null;
}
public V put(K key, V value) {
// 如果根节点为空，则该元素置为根节点
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = ;
modCount++;
return null;
}
// 如果比较器对象不为空，也就是自定义了比较器
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {// 循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < )
t = t.left;
else if (cmp > )
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 如果比较器对象为空，使用默认的比较机制
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {// 同样是循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
parent = t;
cmp = k.compareTo(t.key);
if (cmp < )
t = t.left;
else if (cmp > )
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);// 根据key找到父节点后新建一个节点
if (cmp < )// 根据比较的结果来确定放在左子树还是右子树
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
四.HashTable
HashMap和Hashtable的区别如下：
- Hashtable是线程安全，其多数的方法都加了synchronized 修饰符。
- 插入Hashtable中的元素，其key和value值都不能为null，否则会抛出NullPointerException异常。
public Hashtable() {
this(, f);
}
//key和value值均不能为null，否则抛出NullPointerException异常
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 = key.hashCode();//key不能为null
int index = (hash & ) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & ) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}