底层代码分析
·📄 4604 字·🍵 10 分钟
重要属性 #static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int MAXIMUM_CAPACITY = 1 << 30; static final float......
HashMap相关
目录
底层数据结构 #
在JDK1.7 和JDK1.8 中有所差别：
在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
- 当链表超过 8 且数据总量超过 64 才会转红黑树。
- 将链表转换成红黑树前会判断，如果数据总量小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
转红黑树的条件？ #
为什么当链表超过 8 且数据总量超过 64 才会转红黑树。
源码分析之后确实是这样的。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//......
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//TREEIFY_THRESHOLD=8
//binCount是从0开始加到7的
if (binCount >= TREEIFY_THRESHOLD - 1) //
treeifyBin(tab, hash);
break;
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY不可更改且为 64
//先判断是否小于，小于则扩容。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//转为红黑树
//.....
}
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
通过查看源码可以发现，默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，这体现了时间和空间平衡的思想.
最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。对于何时应该从链表转化为红黑树，需要确定一个阈值，这个阈值默认为 8，并且在源码中也对选择 8 这个数字做了说明，原文如下：
In usages with well-distributed user hashCodes, tree bins
are rarely used. Ideally, under random hashCodes, the
frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because
of resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
上面这段话的意思是，如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。
总量小于64先进行扩容：因为扩容之后会发生 rehash，有的键值对可以在 rehash之后转移到别的位置上去从而减少了链表的长度。从一定程度上使得链表长度大于8不那么快成立，但是也不能一直使用扩容来解决链表的问题，因为扩容会使数组空间扩大一倍，仅仅为了解决链表的问题而扩容得不偿失，因此设定了一个64的阈值。
解决hash冲突的办法 #
解决Hash冲突方法有: 开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。
HashMap中采用的是 链地址法 。
- 开放定址法也称为
再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。 - 再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当
R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。 - 链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
- 建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
为什么不直接用红黑树？而选择先用链表，再转红黑树? #
因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。
默认加载因子 #
回答这个问题前，我们来先看下HashMap的默认构造函数：
int threshold; // 容纳键值对的最大值
final float loadFactor; // 负载因子
int modCount;
int size;
Node[] table的初始化长度 length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳键值对的最大值。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空间比较特殊的情况下 ：
- 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值 。
- 相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
我们来追溯下作者在源码中的注释（JDK1.7）：
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.
Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations.
If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
翻译过来大概的意思是：作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
Hash值的计算？ #
首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。看看源码的实现：
// jdk1.7
方法一：
static int hash(int h) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode(); // 为第一步：取hashCode值
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
方法二：
//在hashMap的length等于2的n次方的时候，才会有hash%length==hash&(length-1)；哈希算法的目的是为了加快哈希计算以及减少哈希冲突，所以此时&操作更合适，所以在length等于2的幂次方的时候，可以使用&操作加快操作且减少冲突，所以hashMap长度是2的幂次方
//h是hash值，length是数组长度
//jdk1.7的源码，jdk1.8没有这个方法，但实现原理一样
static int indexFor(int h, int length) {
return h & (length-1); //第三步：取模运算
}
// jdk1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
/*
h = key.hashCode() 为第一步：取hashCode值
h ^ (h >>> 16) 为第二步：高位参与运算
*/
}
这里的 Hash 算法本质上就是三步：取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。其中，JDK1.7和1.8的不同之处，就在于第二步。我们来看下详细过程，以JDK1.8为例，n为table的长度。
Hash值为什么这么计算？ #
先看下hash(Object key)方法，
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- h »> 16 是什么？h是hashcode。h »> 16是用来取出h的高16，(»>是无符号右移)
- 为什么 h = key.hashCode()) 与 (h »> 16) 异或？
先看看HashMap数组下标的计算：
static int indexFor(int h, int length) {
return h & (length-1);
}
由于和（length-1）运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。
所以这样高16位是用不到的，如何让高16也参与运算呢。所以才有hash(Object key)方法。让他的hashCode()和自己的高16位^运算。所以(h »> 16)得到他的高16位与hashCode()进行^运算。
而且&和|都会使得结果偏向0或者1 ,并不是均匀的概念。所以选择用^。
HashMap长度为什么是2的幂次方? #
因为只有在hashMap的length等于2的n次方的时候，才会有hash%length==hash&(length-1)；哈希算法的目的是为了加快哈希计算以及减少哈希冲突，所以此时&操作更合适，所以在length等于2的幂次方的时候，可以使用&操作加快操作且减少冲突，所以hashMap长度是2的幂次方。
/**
*
* 直接【求余】和【按位】运算的运算效率差别验证
*/
public static void main(String[] args) {
long currentTimeMillis = System.currentTimeMillis();
int a=0;
int times = 10000*10000;
for (long i = 0; i < times; i++) {
a=9999%1024;
}
long currentTimeMillis2 = System.currentTimeMillis();
int b=0;
for (long i = 0; i < times; i++) {
b=9999&(1024-1);
}
long currentTimeMillis3 = System.currentTimeMillis();
System.out.println(a+","+b);
System.out.println("%: "+(currentTimeMillis2-currentTimeMillis));
System.out.println("&: "+(currentTimeMillis3-currentTimeMillis2));
}
/**
结果：
783,783
%: 359
&: 93
**/
HashMap的put方法流程？ #
简要流程如下：
- 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
- 如果数组是空的，则调用 resize 进行初始化；
- 如果没有哈希冲突直接放在对应的数组下标里；
- 如果冲突了，且 key 已经存在且相同，就覆盖掉 value；
- 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
- 如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在且相同，就覆盖掉 value。
public V put(K key, V value) {
//首先当然是计算key的hash值，具体可以参见我写的第一篇文章，
//然后调用putVal
return putVal(hash(key), key, value, false, true);
}
//onlyIfAbsent为false，说明如果已经存在相同(== 、equals)的key，则覆盖并返回旧值。
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）//此时table已经不为空
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//没有产生hash碰撞，即table的第i个桶还没有元素，直接插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//此时第i个桶已经存在元素，且p是这个桶的第一个元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//先比较第一个元素，如果hash值相等并且 (是同一个key || 两个key equals)，直接跳到最后进行旧值覆盖
e = p;
else if (p instanceof TreeNode)
//如果第i个桶是红黑树的话，执行红黑树的插入逻辑
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果第i个桶是一个链表，则遍历整个链表
for (int binCount = 0; ; ++binCount) { //利用binCount来计数链表的节点数
if ((e = p.next) == null) {
//已经遍历到链表最后，则在尾部添加一个节点
p.next = newNode(hash, key, value, null);
//假如此时链表有8个结点，遍历到第8个结点的时候（此时binCount为7，binCount初始值为0），在链表尾部新加了一个结点，
//此时链表有9个结点，而且binCount >= TREEIFY_THRESHOLD - 1 （7 >= 8-1）,条件成立，将链表转变为红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//遍历的过程中，如果与其中一个节点的key的hash值相等并且(同一个key || 两个key equals)，直接跳出循环到最后进行旧值覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
//onlyIfAbsent为false，或者oldValue为null，进行旧值的覆盖
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //Do nothing！
//直接返回旧值，后面的逻辑不会执行，因为结构没有发生变化，而且size也没有增加
return oldValue;
}
}
++modCount; //modCount为HashMap结构修改的次数，如新加入一个key-value（覆盖旧值不算，因为结构没有发生变化）、删除一个key-value、扩容等等。
if (++size > threshold)
//插入一个key-value之后，如果此时的size > threshold，进行扩容
resize();
afterNodeInsertion(evict);//do nothing
return null;
}
HashMap 的扩容方式？ #
HashMap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无法自动扩容的，方法是将 HashMap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。默认容量是16。
那扩容的具体步骤是什么？让我们看看源码。
先来看下JDK1.7 的代码 #
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //！！将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话）。
扩容在JDK1.8中有什么不一样？ #
JDK1.8做了两处优化：
resize 之后，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）。不需要像 JDK1.7 的实现那样重新计算hash ，只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”。这个设计非常的巧妙，省去了重新计算 hash 值的时间。
如下图所示，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例，图（b）表示扩容后 key1 和key2 两种 key 确定索引位置的示例，其中 hash1 是 key1 对应的哈希与高位运算结果。
元素在重新计算 hash 之后，因为 n 变为 2倍，那么 n-1 的 mask 范围在高位多 1 bit(红色)，因此新的index就会发生这样的变化：
JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，使用尾插法。
下图为 16扩充为 32 的 resize 示意图：
一般用什么作为HashMap的key? #
一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。
- 因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是 HashMap 中的键往往都使用字符串的原因。
- 因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了 hashCode() 以及 equals() 方法。
还知道哪些hash算法？ #
Hash函数是指把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存。 比较出名的有MurmurHash、MD4、MD5等等。
key 可以为 Null 吗? #
可以，key 为 Null 的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。
用可变类当 HashMap 的 key 有什么问题? #
hashcode 可能发生改变，导致 put 进去的值，无法 get 出。如下所示
HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
System.out.println(changeMap.get(list));
list.add("hello world");//hashcode发生了改变
System.out.println(changeMap.get(list));
/**
输出值如下
java.lang.Object@74a14482
null
**/
HashMap为什么线程不安全？ #
- 多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
- 多线程的put可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
- put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。
具体分析可见这篇文章：面试官：HashMap 为什么线程不安全？
底层代码分析 #
