Java集合源码分析-HashMap和IdentityHashM
HashMap基本是面试必问的数据结构了。理解了HashMap，IdentityHashMap就很简单了，所以主要分析HashMap，文章最后对IdentityHashMap简单分析下。
HashMap 底层数据结构是数组称之为哈希桶table，哈希桶的长度一定会是2的次方(这样在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效)，每个桶里面放的是链表(从源码中可以看到是单向非循环链表，只有next指针无prev指针)，链表中的每个节点，就是哈希表中的每个元素，它是线程不安全的，允许key为null,value为null。遍历时无序。
在JDK8中，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率。
因其底层哈希桶的数据结构是数组，所以也会涉及到扩容的问题。当HashMap的容量达到threshold域值时，就会触发扩容。
扩容操作时，会new一个新的Node数组作为哈希桶，然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中，相当于对原哈希表中所有的数据重新做了一个put操作。所以性能消耗很大，可想而知，在哈希表的容量越大时，性能消耗越明显。
这里再提下为啥hash桶的容量必须设计成2的x次幂，一般我们利用hash码, 计算出在一个数组的索引, 常用方式是”hash % length”, 也就是求余的方式，这种方式效率不高, 有一个公式：“当容量一定是length =2x时，hash & (length - 1) = hash % length”---公式1， 按位运算特别快。怎么证明公式1呢？我还没找到证明方法，请大神们告知。
1 HashMap类图
HashMap类图
可以看到HashMap类图要比List集合的类图简单一些，但是实现上却复杂一些。
2 HashMap成员变量和构造器
//hash桶的容量，默认是16，必须是2的指数，扩容会增加一倍容量，扩容十分耗性能
static final int DEFAULT_INITIAL_CAPACITY = 16;
//hash桶最大容量，必须是2的幂
static final int MAXIMUM_CAPACITY = 1073741824;//(1 << 30)
//默认加载因子，默认节点数大于16*0.75=12就会触发扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//如果链表的长度大于8，链表会转换成红黑树提高效率
static final int TREEIFY_THRESHOLD = 8;
//扩容或者删除操作导致链表长度小于6时就从红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
//转换成红黑树的节点数的最小阈值，也是额外判断
static final int MIN_TREEIFY_CAPACITY = 64;
//hash桶数组
transient HashMap.Node<K, V>[] table;
//节点的集合Set，通过它进行迭代器的遍历
transient Set<Entry<K, V>> entrySet;
//节点个数
transient int size;
//HashMap结构更改次数，fast-fail机制
transient int modCount;
//扩容阈值
int threshold;
//加载因子
final float loadFactor;
HashMap提供了四类构造器：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
}
这里重点分析下第三个构造器，它给定了hash桶容量initialCapacity和加载因子loadFactor，不过HashMap要求hash桶容量必须是2的幂，于是提供了一个方法tableSizeFor来寻找大于等于initialCapacity的最小的2的幂的值。下面是tableSizeFor的源码：
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;
}
第二行为什么要进行减一操作呢？如果不减一，有一种test-case会有问题：cap已经是2的幂，那么最终计算的结果将是cap * 2。为了修复这个test-case，需要进行减一操作。具体原因下面接着分析。
第三行代码开始进行了5次无符号右移操作，如果开始时n已经是0，经过无符号右移，最终的n还是0，最后返回1即2的0次幂。下面讨论的情况是n不等于0。
第一次右移
由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx。
第二次右移
注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。
第三次右移
这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。
第四次右移
会有16个连续的1，结果如00001111 1111 1111 1111xxxxxx 。
第五次右移
会有32个连续的1，结果如00001111 1111 1111 1111 1111 1111 1111 1111xxxxxx 。
最多也就32个1，但是这时已经大于了MAXIMUM_CAPACITY ，所以取值到MAXIMUM_CAPACITY 。 如果小于MAXIMUM_CAPACITY，那么加一即011111111+1=100000000的变量值就得到了2的幂的值。
下面的图来自引用。
返回的值被赋值给了threshold：this.threshold = tableSizeFor(initialCapacity);而不是this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
HashMap提供了两个重要的内部类HashMap.Node和HashMap.TreeNode(继承关系是HashMap.TreeNode->LinkedHashMap.Entry->HashMap.Node)，分别是链表的节点类型和红黑树的节点类型：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
注意equals方法，需要key和value的内容都相同才返回true。
3 HashMap的核心操作
集合的核心操作无外乎增删改查，put、remove、get，此外还有一个扩容操作resize。
3.1 put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
前三个参数很明白，第四个参数onlyIfAbsent为false的话表示如果有相同的key，把原来的value覆盖掉，但是key不变(HashSet添加相同的元素不会覆盖的，因为HashSet就是基于HashMap的key集合进行操作)。第五个参数evict为false的话表示table变量是创建模式，这个参数只有在第四类构造器调用的时候才会为false，表示是构造器调用的，这个区分是干嘛用的呢？后面分析。
可以看到，首先调用hash方法计算hash值来决定hash桶的位置：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从上面代码可以看出，hash桶的第0个桶位是专门给key=null的节点用的，而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。 即，碰撞率会增大。
扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）
JDK8是这样操作的：key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。
这与table的下标计算方式有关：
tab[i = (n - 1) & hash]
因为，table的长度都是2的x次幂，因此index仅与hash值的低x位有关，hash值的高位都被与操作置为0了。
假设table.length=24=16，此时x=4：
由上图可以看到，只有hash值的低x=4位参与了运算。高位不参与运算的话很容易产生碰撞。设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。引文
添加操作其实会调用putVal方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
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) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
这个方法是链表使用的，红黑树使用的方法是putTreeVal，但是这两个方法的返回值的意义是一样的并且很重要：当且仅当链表中或者红黑树中存在和要插入的节点的key相同的时候才不返回null，且返回的是要被覆盖的节点，其余情况下返回的是null(这个观点是我自己分析总结的，请大神斧正)。
- 第一个if是判断hash桶是否为空，如果为空就调用resize方法就行扩容，
- 第二个if是根据hash找到桶的位置并判断当前位置的节点p是否为nil，如果为nil，直接在当前位置插入一个新建的节点newNode，如果不为nil进入else
- 在else中，有个变量e很重要，这个值当且仅当存在和要插入的节点的key相同的时候才不为null
3.1 第一个if表示当前节点p的key和要插入的节点的key一样，那么把原来的节点p赋值给e进行后面的时候覆盖操作
3.2 第二个条件else if表示这个桶里的结构是红黑树，那么调用putTreeVal方法，将结果赋值给e
3.3 第三个条件else进行for循环查找尾节点或者和插入节点相同key的节点，第一个if表示找到了尾节点，那么直接插入到尾部就好了，然后判断是否转换成红黑树，然后break；第二个if表示找到了和要插入节点的key相同的节点，那么直接break；这两种情况都不满足的话继续遍历
3.4 最后的if表示存在和要插入节点的key相同的节点，并判断是否覆盖，只有在这个if条件中，整个方法的返回值才不为nil而且不修改modCount的值因为并没有更改HashMap的结构，这里会调用afterNodeAccess方法，但是是空方法，这个方法是给LinkedHashMap留的后门，这里用不到，以后再分析； - ++modCount;这不需要解释，这是集合的fast-fail机制，Java集合源码分析-ArrayList这篇文章有介绍fast-fail机制；然后判断是否进行扩容；再调用afterNodeInsertion(这里没用，也是给LinkedHashMap留的后门)。
从上面的步骤可以知道，新节点会被插入到链表的尾部，这和Hashtable不太一样，Hashtable会将新节点插入到链表的头部，其实插入头部还是尾部是无所谓的，不存在孰优孰劣(因为两个插入方式都要遍历链表，遇到相同key值则break并覆盖，没有相同key就遍历到尾部，所以两种方式性能是一样的)。Java集合源码分析-Hashtable
3.2 resize
put操作的流程介绍完了，其中的扩容操作是一个核心的方法：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 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 == 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;
}
代码中有一个for循环，循环之前的代码是将容量扩大到2倍的操作，很简单清晰，for循环的操作是将老的hash桶rehash到一个扩容过的2倍容量的新的数组中，这个操作是有点技术含量的。
遍历老的hash桶，对于hash桶的第j个位置，如果if ((e = oldTab[j]) != null)(表示当前节点e不为nil)，我们可以看到代码中分三种情况：
- 第一个条件if表示桶位j只有一个节点，很简单，将新桶的第
e.hash & (newCap - 1)个节点置为当前节点e； - 第二个else if表示桶位j是一个红黑树，那么采用红黑树特有的rehash算法
split； - 第三个else条件表示桶位j是一个节点个数大于1的链表，可以看到里面使用了do while循环进行链表遍历，在do while循环中将老的链表分割成两个链表，loHead、loTail存储第一个链表，hiHead、hiTail存储第二个链表，第一个链表放到新桶的第j位即原来的桶位，第二个链表放到新桶的第j + oldCap位，而分割链表是根据
(e.hash & oldCap) == 0这个条件，这算法，服。
有篇文章介绍了JDK1.7的HashMap在多线程下的rehash过程可能死锁，有兴趣的可以看下。
3.3 remove
前面分析的都是硬骨头，后面的代码和算法都是软柿子(柿子是不是先挑软的捏好一些呢？)。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
remove操作没什么技术含量，核心是根据key和hash找到要删除的节点，然后删掉并改变相关节点的next节点即可。
3.4 get
看代码不解释。
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) > 0 &&
(first = tab[(n - 1) & 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;
}
4 遍历
HashMap提供了三种遍历方式分别是KeySet、Values、EntrySet用来遍历，他们分别使用的迭代器是KeyIterator、ValueIterator和EntryIterator，而这三类迭代器有一个共同的父类迭代器：HashIterator，他们初始化的时候都会首先初始化基类HashIterator，HashIterator构造器会存储hash桶的数据，遍历操作都是HashIterator完成的。
关于三种遍历方式的取舍，我是这样认为的：
- 只访问key的话，优先使用KeySet，EntrySet次之(当然Values没法访问key)
- 只访问value的话，优先使用Values迭代器效率最高，EntrySet次之，KeySet最后
- 既访问key又访问value的话，优先使用EntrySet，KeySet次之(当然Values没法访问key)
由基类迭代器HashIterator的实现可以看出，遍历HashMap时，顺序是按照哈希桶从低到高，链表从前往后进行遍历的，并且是fast-fail的。
下面的性能分析参考自文章 java中hashmap容器实现查找O(1)时间复杂度的思考：
我们对一个键值对的查询，是分为四步的。
- 先根据key值计算出hash值以及h值（h值是java实现中处理得到的更优的index索引值）
- 查找table数组中的h位置，得到相应的键值对链表
- 根据key值，遍历键值对链表，找到相应的键值对，
- 从键值对中取出value值。
只有以上四步都能在O(1)时间内完成，hashmap才能拥有O(1)的时间复杂度。易知，步骤1（计算）、步骤2（数组的查找）和步骤4（从键值对中取value值）都可以在O(1)时间内完成。那么，步骤3中链表的长度决定了整个hashmap容器的查找效率，这也是hashmap容器设计的关键。必须采用优秀的hash算法以减少“冲突”，使得链表的长度尽可能短，理想状态下链表长度都为1。
结论：
hashmap容器O(1)的查找时间复杂度只是其理想的状态，而这种理想状态需要由java设计者去保证
在由设计者保证了链表长度尽可能短的前提下，由于利用了数组结构，使得key的查找在O(1)时间内完成
可以将hashmap分成两部分来看待，hash和map。map只是实现了键值对的存储，也就是以上查询步骤的第4步。而其整个O(1)的查找复杂度很大程度上是由hash来保证的。
hashmap对hash的使用体现出一些设计哲学，如：通过key.hashCode()将普通的object对象转换为int值，从而可以将其视为数组下标，利用数组O(1)的查找性能。
5 IdentityHashMap
我没有对IdentityHashMap单独写文章介绍，因为没必要而且两者很像。IdentityHashMap并不是继承HashMap，它和HashMap的类图和底层数据结构是一样的，区别在于：
- IdentityHashMap使用的是==比较key的值，而HashMap使用的是equals()
- IdentityHashMap使用的是System.identityHashCode(object)查找桶的位置，HashMap使用的是hashCode()
- IdentityHashMap理论上来说速度要比HashMap快一点
- 由于IdentityHashMap的key比较的是引用，因此key的内容是可以重复的，但是HashMap是不会的
