HashMap

哈希桶数组

HashMap类中有一个非常重要的字段，就是Node[] table,称作哈希桶数组，是一个Node数组。其中Node结构如下

java

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node next;   //链表的下一个node

        Node(int hash, K key, V value, Node next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。

HashMap的几个字段：

java

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;

首先，Node[]table的初始化长度length(默认值为16)，Load factor为负载因子（默认为0.75）。threshold是HashMap所能容纳的最大数据量的Node个数。threshold=length×Load_factor。size是HashMap中实际存在的键值对数量。

当size大于threshold时，就要多HashMap进行resize。

modCount字段主要用来记录HashMap结构发生变化的次数，值得注意的是，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

哈希桶数组的table的长度为2的n次方的原因

一般来说，哈希桶数组的桶数为素数比较好，但在jdk1.8中，table的长度length大小必须为2的n次方（合数），主要为了在取模和扩容（扩容时容易rehash）时做优化。

为什么一般哈希桶数组的桶数会取一个素数？

设有一个哈希函数
H( c ) = c % N;
当N取一个合数时，最简单的例子是取2^n，比如说取2^3=8,这时候
H( 11100(二进制） ) = H( 28 ) = 4
H( 10100(二进制) ) = H( 20 ）= 4
这时候c的二进制第4位（从右向左数）就”失效”了，也就是说，无论第c的4位取什么值，都会导致H( c )的值一样．这时候c的第四位就根本不参与H( c )的运算，这样H( c )就无法完整地反映c的特性，增大了导致冲突的几率。

Hash算法

数据结构书上学的hash算法中常用的就是取模，这样能使的hash值分布比较均匀。在jdk1.8中思想也是这样，具体是这么做的

取key的hashCode值，通过hashCode()函数，得到一个int。
java
1
h = key.hashCode()
其中hashCode()的计算公式如下：
java
1
2
>//hashCode()计算公式
>s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
高位运算,hash()函数，进行扰动
java
1
h ^ (h >>> 16)
如果没有高位运算，取模后总是低位的值，而低位的值就那么几个，很容易冲突。右移16位的原因是因为int的长度为32位。

扩展

>>：带符号右移。正数右移高位补0，负数右移高位补1。比如：

4 >> 1，结果是2；-4 >> 1，结果是-2。-2 >> 1，结果是-1。

>>>：无符号右移。无论是正数还是负数，高位通通补0。

对于正数而言，>>和>>>没区别。
取模运算
java
1
h & (table.length-1)
因为length总是2的n次方的缘故，对$2^n$取模，就相当于h& (table.length-1),位运算效率更高。

扩容

分为两步

扩容：创建一个新的空数组，长度是原数组的2倍。
ReHash：遍历原数组，把所有的Node重新Hash到新数组。

为什么要重新创建一个2倍大小的数组，在原数组的基础上不行吗？

java数组大小不可变。

为什么要重新Hash呢，直接复制过去不行吗？

hash规则跟table的长度有关，所以不能直接复制。

为什么扩容大小为原来的2倍，不是3倍或者4倍？

因为length变为2倍，那么取模时h & (table.length-1)就会比未扩容前多1位，且多出来的这1位只有可能是0或者1，如下图所示：

所以扩容之后我们就rehash的过程就变得特别简单，不需要像JDK1.7的实现那样重新从头计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

下图为16扩充为32的resize示意图：

冲突避免

在数据结构书中，避免冲突的算法有开放位置法和拉链法。在jdk中基于拉链法的思想，进行改进。

jdk1.7中，采用头插法：

优点
- 头插法插入方便。
- 根据程序局部性原理，后插入的更有可能被访问，插在头部查找效率高
缺点：
- 在扩容时会造成倒序，上述的优点就失效了。
- 在多线程操作中，扩容会造成链表成环（不用管，面试不会问，只知道会成环就好）。

jdk1.8中，采用尾插法：

扩容转移后前后链表顺序不变，保持之前节点的引用关系, 在同样的前提下并不会引起死循环。

那是不是意味着Java8就可以把HashMap用在多线程中呢？

即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。
采用尾插法丢失了头插法的优点，但是jdk1.8中，加入了红黑树优化。红黑树我之后会写。

参考

https://zhuanlan.zhihu.com/p/21673805