HashMap实现原理
HashMap的底层使用数组+链表/红黑树实现。
transient Node<K,V>[] table;这表示HashMap是Node数组构成，其中Node类的实现如下，可以看出这其实就是个链表，链表的每个结点是一个<K,V>映射。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}HashMap的每个下标都存放了一条链表。
常量/变量定义
/* 常量定义 */
// 初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子，当键值对个数达到DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR会触发resize扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当链表长度大于8，且数组长度大于MIN_TREEIFY_CAPACITY，就会转为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当resize时候发现链表长度小于6时，从红黑树退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 在要将链表转为红黑树之前，再进行一次判断，若数组容量小于该值，则用resize扩容，放弃转为红黑树
// 主要是为了在建立Map的初期，放置过多键值对进入同一个数组下标中，而导致不必要的链表->红黑树的转化，此时扩容即可，可有效减少冲突
static final int MIN_TREEIFY_CAPACITY = 64;
/* 变量定义 */
// 键值对的个数
transient int size;
// 键值对的个数大于该值时候，会触发扩容
int threshold;
// 非线程安全的集合类中几乎都有这个变量的影子，每次结构被修改都会更新该值，表示被修改的次数
transient int modCount;关于modCount的作用见这篇blog
在一个迭代器初始的时候会赋予它调用这个迭代器的对象的modCount，如何在迭代器遍历的过程中，一旦发现这个对象的modCount和迭代器中存储的modCount不一样那就抛异常。
Fail-Fast机制：java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map。
注意初始容量和扩容后的容量都必须是2的次幂，为什么呢?
hash方法
先看散列方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap的散列方法如上，其实就是将hash值的高16位和低16位异或，我们将马上看到hash在与n - 1相与的时候，高位的信息也被考虑了，能使碰撞的概率减小，散列得更均匀。
在JDK 8中，HashMap的putVal方法中有这么一句
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);关键就是这句(n - 1) & hash，这行代码是把待插入的结点散列到数组中某个下标中，其中hash就是通过上面的方法的得到的，为待插入Node的key的hash值，n是table的容量即table.length，2的次幂用二进制表示的话，只有最高位为1，其余为都是0。减去1，刚好就反了过来。比如16的二进制表示为10000，减去1后的二进制表示为01111，除了最高位其余各位都是1，保证了在相与时，可以使得散列值分布得更均匀（因为如果某位为0比如1011，那么结点永远不会被散列到1111这个位置），且当n为2的次幂时候有(n - 1) & hash == hash % n, 举个例子，比如hash等于6时候，01111和00110相与就是00110，hash等于16时，相与就等于0了，多举几个例子便可以验证这一结论。最后来回答为什么HashMap的容量要始终保持2的次幂
- 使散列值分布均匀
- 位运算的效率比取余的效率高
注意table.length是数组的容量，而transient int size表示存入Map中的键值对数。
int threshold表示临界值，当键值对的个数大于临界值，就会扩容。threshold的更新是由下面的方法完成的。
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;
}
该方法返回大于等于cap的最小的二次幂数值。比如cap为16，就返回16，cap为17就返回32。
put方法
put方法主要由putVal方法实现：
- 如果没有产生hash冲突，直接在数组
tab[i = (n - 1) & hash]处新建一个结点； - 否则，发生了hash冲突，此时key如果和头结点的key相同，找到要更新的结点，直接跳到最后去更新值
- 否则，如果数组下标中的类型是TreeNode，就插入到红黑树中
- 如果只是普通的链表，就在链表中查找，找到key相同的结点就跳出，到最后去更新值；到链表尾也没有找到就在尾部插入一个新结点。接着判断此时链表长度若大于8的话，还需要将链表转为红黑树（注意在要将链表转为红黑树之前，再进行一次判断，若数组容量小于该值，则用resize扩容，放弃转为红黑树）
get方法
get方法由getNode方法实现：
- 如果在数组下标的链表头就找到key相同的，那么返回链表头的值
- 否则如果数组下标处的类型是TreeNode，就在红黑树中查找
- 否则就是在普通链表中查找了
- 都找不到就返回null
remove方法的流程大致和get方法类似。
HashMap的扩容，resize()过程？
newCap = oldCap << 1resize方法中有这么一句，说明是扩容后数组大小是原数组的两倍。
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
// 数组下标处的链表长度大于1，非红黑树的情况
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// oldCap是2的次幂，最高位是1，其余为是0，哈希值和其相与，根据哈希值的最高位是1还是0，链表被拆分成两条，哈希值最高位是0分到loHead。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 哈希值最高位是1分到hiHead
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// loHead挂到新数组[原下标]处；
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// hiHead挂到,新数组中[原下标+oldCap]处
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;举个例子，比如oldCap是16，二进制表示是10000，hash值的后五位和oldCap相与，因为oldCap的最高位（从右往左数的第5位）是1其余位是0，因此hash值的该位是0的所有元素被分到一条链表，挂到新数组中原下标处，hash值该位为1的被分到另外一条链表，挂到新数组中原下标+oldCap处。举个例子：桶0中的元素其hash值后五位是0XXXX的就被分到桶0种，其hash值后五位是1XXXX就被分到桶4中。
by @sunhaiyu
2018.7.26
- 还没有人评论，欢迎说说您的想法！
客服
