Java集合-HashMap分析（jdk1.8)
HashMap存储的是键值对，可以说是最常用的map了。下面是构造方法：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
和List相比，HashMap初始化工作除了指定初始容量initialCapacity之外，还多了一个负载因子loadFactor，默认值为0.75。另外还有一个threshold变量，指定了扩容阈值。
无参构造函数只是将负载因子赋值为默认的0.75，指定容量和负载因子的构造函数，根据指定容量计算threshold：大于或等于initialCapacity的2的n次方值最小值（比如initialCapacity是16，threshold就是16, 17则threshold是32）
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
注意table这个变量，它就是用来存储数据的数组，index是根据key的hash值确定的，值就是包含了key和value的链表。
接下来看put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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，或者table的长度为0，说明此时map为空，需要先进行reSize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// n 此时为table数组的长度，& hash 得到hash值对应的index，
//table对应index位置的值如果是null，说明这个hash值没有存储过
//所以直接将key和value放入节点，节点放入数组对应位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//走入这里，说明hash值对应的index已经有值了，也就是说，新添加元素的key和已有元素的key哈希值相同
Node<K,V> e; K k;
//p此时是table中原来的数据链表的第一个元素，如果hash值相同，key也相同，直接将旧元素替换为新元素，并返回旧元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断是不是红黑树，是的话开始在树中插入数据（如果树中key已存在，添加失败，返回对应值）
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//不是红黑树，说明是链表结构，开始在链表中插入数据
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//循环到链表尾部，新建一个节点，并将最后一个节点的next指针指向新建的节点，添加数据完成
p.next = newNode(hash, key, value, null);
//添加完成以后检查长度，如果超过了TREEIFY_THRESHOLD（8），将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果链表中某个元素的hash已存在，并且key相同，直接退出循环，并将map中对应的值返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e != null 说明待存入数据的key已经存在，并且key的hash值也存在，返回map中相同key对应的数据
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//添加成功会走到这里，最终返回null
++modCount;
if (++size > threshold)
//返回之前检查添加元素以后，数组长度是否超过阈值，超过则进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
注意代码中hash值的计算方式，和数据在table数组中的存取位置：
hash值计算：
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
存放位置：
i = (n - 1) & hash //n是table数组长度
如果key是null，直接返回 0，经过位与操作结果肯定也是0，所以null可以作为key，会被放在map中index为0的位置。
存放位置的计算方式：
1. 获取key的hashCode
2. 将hashCode右移16位
3. 右移16位后的数据与自身进行异或
4. 得到的hash值与数组长度-1位与运算，保证不会超出数组长度
2和3两步的作用：如果直接与数组长度-1进行位与，参与运算的只是hashCode低位：数组长度-1 对应的位数（数组长度值远小于hash值，位与操作高位补0，所以实际参与运算的只是hash值的低位）
hash值可能是一个比较长的数据，也就是说，他们低位的数据可能是一样的，这样就导致出现冲突的概率极高，所以把hashCode右移16位以后，再与hashCode位与，使得hashCode的高位部分也参与运算，这样就降低了hash值冲突的概率。
确定了位置以后，进行添加数据的操作：
1. table为null或者长度为0，进行reSize扩容
2. 如果对应位置没有数据，直接新建节点，并添加到table对应位置
3. 如果对应位置已经有数据了，判断对应位置存放的节点（table数组中存放的是链表的第一个节点）的key是否相同，是的话，添加失败，返回该key对应的value
4. 如果对应位置有数据，但是key不相同，判断是不是红黑树，是红黑树的话用putTreeVal方法添加数据（遍历树，查找是key是否存在，是的话插入失败，返回对应值，否则插入数据）
5. 如果对应位置有数据，但是key不相同，链表又不是红黑树，开始遍历链表，查找是key是否存在，是的话返回对应值，否则插入数据到链表尾部，插入完成以后检查链表长度，超过8则转换为红黑树
6. 最后一步检查size+1是否超过阈值，超过说明数据已存满，开始扩容
接下来看reSize()是怎么确定table的容量的：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//此处的oldCap是table的长度，也就是说table一定被创建过（已经有数据存放了），才会满足条件 oldCap > 0
if (oldCap > 0) {
//旧容量达到最大值，阈值设为最大，不扩容，直接返回旧的table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//旧容量扩容（翻倍）后小于最大容量，并且旧容量大于默认初始容量（16），阈值直接翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//--------创建Hashmap从这里开始：-----------------
//oldThr>0 说明调用的有参构造函数，传入了初始容量，threshold是根据初始容量计算出的2的n次方，容量也赋值为`threshold`值
//也就是说，调用有参构造函数时传入的initialCapacity并不是实际容量，而是大于等于它的最接近的2的n次方值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//进入这里说明调用的无参构造函数，初始容量16，阈值0.75*16
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//newThr == 0 说明hashmap是有参构造函数创建的：1.第一次扩容，table尚未创建，2 table需要扩容，旧容量小于默认容量16，此时把阈值设置为 新容量*负载因子
if (newThr == 0) {
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 = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = 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) == 0) {
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;
}
table数组就是在reSize方法中创建的，一旦数组长度超过阈值，就进行扩容，创建一个新的数组并将原来的值拷贝进来，所以在使用HashMap的时候，合理设置初始长度和负载因子，可以有效的避免重复创建对象拷贝数据，提高map性能。
LinkedHashMap 和 TreeMap
先看一下LinkedHashMap，它继承了HashMap，也就是说，他们两个总体结构是相同的.构造方法如下：
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
这里多了一个成员变量accessOrder，默认值为false，它如果为true，每次调用get方法取值时，将值移动到尾部的节点。这样就会使得最近操作过的数据存放在靠近尾部的位置，而头部是不经常使用的数据。
它没有重写put方法，也就是说它实际上使用了HashMap的put方法，从上边的源码可以看到，存储数据调用的方法是newNode,LinkedHashMap重写了该方法（红黑树用的是newTreeNode，LinkedHashMap同样重写了该方法）：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
下面是HashMap的 newNode方法：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
除了将Node替换成了LinkedHashMapEntry以外，还多了一行linkNodeLast(p);
LinkedHashMap数据存放节点是LinkedHashMapEntry,它多了两个变量before和after，每次加入数据以后，分别将这两个变量指向了对应的节点。这也就是LinkedHashMap的特点：记录数据插入顺序。遍历时也会按照插入的顺序来读取数据。
TreeMap 的构造方法如下：
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
它比较特别，多了一个成员变量comparator，说明TreeMap是有序的，并且支持Comparator排序。下面看一下put方法：
public V put(K key, V value) {
TreeMapEntry<K,V> t = root;
if (t == null) {
//校验key是否合理
compare(key, key); // type (and possibly null) check
//新建root节点并存储数据
root = new TreeMapEntry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
TreeMapEntry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//使用comparator寻找key是不是已经存在（遍历树，compare返回0，说明key已存在，替换为新的值，返回旧值）
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
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 < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//如果没有返回，说明树中对应位置没有值，将key先插入到最后的位置
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//数据插入以后再调用该方法进行重排序，将数据移动到正确的位置
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
可以看到，TreeMap存储数据的节点是TreeMapEntry，它是一个红黑树。
1. 如果根节点为null，新建root节点并存储数据，返回null。注意compare(key, key);，这个方法可以检验key是否合理，key必须是实现了Comparable接口的，并且不能为null
2. 根节点不为空的情况下，用comparator将待插入的key与已存放的key挨个比对，如果有返回值为0的情况，认为key已存在，替换为新的数据，并返回旧值
3. 没有返回值为0的情况，将数据放在树的尾部，然后调用fixAfterInsertion(e);方法重排序，将数据移动到正确位置。
总结：
HashMap是数组和链表形式存放数据的，数组的每一位都是一个链表或者红黑树，而且同一个位置存放的数据，key的hash值相同，但是key不能相同（ == 和 .equals 都返回false）
HashMap中数据在数组中的存放位置是由key的hash值决定的，而不是按照顺序依次增加，所以是随机存储。
LinkedHashMap和HashMap基本相同，但是节点中增加了 before 和 after 来记录插入顺序，遍历时会按插入的顺序来读取数据。
TreeMap 只采用了一个红黑树来存储数据，它也是有序的，但是存放顺序并不是插入顺序，而是通过指定的comparator，或者key中实现的comparator来决定顺序的。key不能是null并且是实现了Comparable接口的类。
再回过头去看一下Set集合，HashSet，LinkedHashSet，TreeSet实际上就是他们对应的map中的key，只是Set实现了Iteratorable接口，可以用Iterator来进行遍历。
使用过程中，对map进行遍历的时候，也是通过set来实现的。