Java集合类-HashMap原理

HashMap源码

JDK 1.7：

• https://sourcegraph.com/github.com/zxiaofan/JDK/-/blob/JDK1.7-Java%20SE%20Development%20Kit%207u80/src/java/util/HashMap.java

JDK 1.8：

• https://sourcegraph.com/github.com/zxiaofan/JDK/-/blob/JDK1.8/src/java/util/HashMap.java

HashMap特点

1. 非线程安全，所以存取速度快
2. 可以接受null的键和值
3. 不保证key有序
4. key的顺序会随时间变化（动态调整大小后会变化）

散列过程

1. 通过散列函数，用元素的key计算出元素在数组中的索引位置
2. 解决散列冲突，即相同散列值（数组索引位置）元素如何存取

散列函数的选取标准

1. 易于计算
2. 均匀分布所有键

拉链法查找一个元素的最少、最坏、平均次数分别是多少？

设哈希表大小为m，已存储的元素个数为n

如果散列函数把所有元素散列到一个位置，链表的长度就是n，最坏情况下就是查找链表中最后一个元素，查找次数是n

如果散列函数散列到哈希表每个位置的概率相同，此时元素分布最均匀，拉链法相当于把n个元素分为m组，那么每组（链表）长度最多为n/m，最坏情况下查找链表最后一个元素，需要n/m次

桶（bucket）是什么意思？

HashMap内部的哈希表由数组实现，数组的每一个位置称为桶，存储一个链表的头结点，或红黑树的根节点，一个桶下所有元素key的hashCode都相同，元素存储在哪一个桶是根据元素key计算出数组索引位置而定的

什么情况下会要求哈希表的大小要是质数？

简述：

• 关注哈希表的大小是因为求得元素在哈希表中存储存储位置是通过 key的hashCode % 哈希表大小 得到，如果散列函数计算结果不均匀，容易产生散列冲突，提高了查找次数。
• 质数不容易被整除，故而可以让计算出的索引分布的比较均匀。合数有公因子，计算出的索引位置容易聚集在公因数的位置，产生较多的散列冲突。

key与哈希表大小互质，这样取模的结果就分散的比较均匀。

如果key可以整除哈希表大小，如果key容易在公因数的位置产生聚集，就会产生较多的散列冲突。

使用质数作为容量，可以使元素更分散，减少冲突；

如果用合数作为容量，会使元素聚集，增加冲突，增加查找次数。

一般是通过除留取余法确定元素在数组中存储索引位置，即：

元素在数组中的存储位置 = key的hashCode % 哈希表长度

假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。

例如2 4 6 8 10 12这6个数，如果对 6 取余 得到 2 4 0 2 4 0 只会得到3种HASH值，冲突会很多，并且呈现以合数的因子为间隔增长；如果对 7取余 得到 2 4 6 1 3 5 得到6种HASH值，没有冲突。

用质数作为数组容量使得任何数想整除它是不可能的，因此探测序列最终会检查到所有单元，冲突较少。

当散列函数计算结果的均匀性较差时，最好使用质数作为哈希表大小可以在除留取余时使得计算出的索引位置分布的更均匀。

但是库一般都会提供散列比较均匀的散列函数，只要散列函数设计的均匀，什么数做桶的大小都行，有时为了方便支持桶的动态扩容或者避免使用除法，桶的大小使用2的幂。

参考资料：

• Hash时取模一定要模质数吗？
• 算法分析：哈希表的大小为何是素数
• 为何在散列表中除留余数法取模运算中，要尽量取素数

为什么桶容量要是2的次方？

散列表用数组实现时，要计算元素应当存储在数组的哪个位置（索引），应当将元素key的hashCode对散列表大小取模，取模结果就是元素要存放在数组的索引位置。

如果key的hashCode函数不能把key散列的均匀，就需要用质数作为哈希表大小，在除留取余的求数组索引时能够让元素分布的比较均匀。

如果key的hashCode能够散列的比较均匀，那么其实用什么数作为哈希表大小都可以。

桶容量为2的幂时取模的好处：
1.可以用位运算取模，计算速度更快，位运算也很方便。
2.可以让元素分布的均匀，减少散列冲突。
3.方便扩容计算，扩容也只需要乘以2，容量左移一位。

为什么2的幂的容量可以让元素分布更均匀？

位运算对2的幂取模过程：一个二进制数乘以2的n次方相当于将该数左移n位，一个二进制数除以2的n次方相当于将该数右移n位，右移出界的部分就是余数，其实也就是原数低n位，取低n位的数，只需要将原数跟低位是n个1的二进制数做与操作就可以得到，低位是n个1的二进制数可以由2的n次方再减1得到。

如果对不是2的幂的数进行位运算取模，假设这个数是x，x-1的二进制数一定不是全部都是1，而是含有0，此时x-1与原数做与操作后，那些有0的位置都会用不到，造成空间浪费，也增大了散列冲突。如果x-1全部是1的话，只要key的hashCode的二进制中的1在低n位分布均匀，就可以保证计算index的过程是分布均匀的，要求x-1的二进制全部是1，那么x就是2的幂。

通过构造函数传入不是2的幂的容量值会怎样？

会找一个最接近传入容量的2的幂作为实际桶的容量。

哈希表容量是2的幂会有什么问题？

key的hash取余求索引时，会截断hash的高位，如果多个key的hash的低位比较固定，高位变化较大，那么最后计算的散列冲突就很多了。

所以需要扰动函数处理一下key的hash，把高位的变化信息传递到低位。

扰动函数是什么，起到什么作用？

存储一个元素时，需要决定该元素应该存储在table（桶）中哪一个位置，需要用元素的key的hashCode对桶容量做取模运算来获得要存储的数组索引位置。

如果桶容量较小，取模操作会仅对key.hashCode()的低位做运算，如果多个元素的key的hashCode()低位相同，只是高位不同，那么冲突就较多，所以需要将高位和低位结合起来取模，减少冲突，避免散列分布不均。

所以在对hashCode做取模运算之前，还需要让hashCode经过扰动函数扰动一下。

jdk1.8中对key的hashCode的扰动函数做了优化：

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

即将key.hashCode()的低16位和高16位做异或运算。

仅仅异或一下做扰动，权衡了速度、性能、质量，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

为什么是右移16位？

推测：因为java中int是32位的，高16位和低16位异或已经算是顾全到了数字的二进制的每一位。

实际：权衡了速度、性能、质量

参考资料：

• HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）

扰动函数为什么是异或运算？

1. 实现简单，运算快捷
2. 对参与运算的两方的二进制的每一位都各自有50%的概率影响结果输出

参考资料：

• Why is XOR the default way to combine hashes?

桶的最大容量为什么是2的30次方，不是2的31次方？

java中int是32位，理论上1可以最多左移31位，因为1不移动就占了1位，所以可以移动的位数是32-1=31位；而虚拟机规定int类型最高位是符号位，符号位不参与移动，可移动位数就是31-1=30位

两个key对象的hashCode相同，如何获取value对象?

在遍历该桶的链表，链表中每个节点保存了键值对信息，将目标key与每个节点的key调用equals方法比较，相等的则为想要找到的节点，取其value对象。

什么对象适合做为HashMap的key?

使用String，Integer等系统类比较好，因为他们的hashCode方法实现是比较均匀的，可以减少散列冲突。

其次这些类一旦创建都是不可变的，一来可以缓存hashCode，二来保证唯一性，三来线程安全。

自定义对象实现hashCode()方法有什么注意事项？

原则：
一个对象的hashCode应该认为有均等的机会得到2的32次方中的任意一个32位整数值。

一个优秀的散列方法需要满足三个条件：

• 一致性 - 等价的键必然产生相等的散列值
• 高效性 - 计算简便
• 均匀性 - 均匀地散列所有的键

保证均匀性的最好办法也许是保证键的每一位都在散列值的计算中起到了相同的作用，实现散列函数最常见的错误是忽略了高位的键。

可以参考String的hashCode设计，kotlin的data class自动生成的hashCode以及集合类的hashCode算法都很相似。

需要使用不可变的属性实现hashCode()方法，因为：

1. 可以在计算一次哈希值后缓存起来，提高哈希表的读取速度。
2. 如果key在放入哈希表时和取出哈希表时hashCode()发生变化，则会取不到之前存放的对象。
3. 不可变的属性是线程安全的。

装载因子是什么？

哈希表中已存储元素个数与哈希表总大小比值，即已存储元素个数与桶个数比值。

装载因子越大，说明填充率高，空间利用率高，但是散列冲突可能性增大。

装载因子越小，说明填充率低，浪费很多空间，但是散列冲突可能性减小。

冲突越多，查找元素的时间越长，所以必须在时间和空间上进行权衡。

装载因子有什么作用？

装载因子 = 已存储的元素个数 / 桶大小

HashMap构造时可以传入一个装载因子，不传入的话会使用默认的装载因子0.75，构造时规定这个装载因子意思是装载因子的最大值。

随着哈希表中存储元素的个数增多，填充率越高，实际的装载因子会逐渐增大，当 实际装载因子 大于 预设装载因子 时，为了避免大量的散列冲突，要增大桶的数量，HashMap会将通大小调整为原来的两倍，因为桶大小要求是2的幂，所以就扩大2倍。

桶容量是如何动态扩展的？

当 已存储元素个数 超过 哈希表大小 * 装载因子，会扩容至原大小的两倍，并对部分元素重新散列。

当put元素时，发现已存储元素个数超过threshold时，会触发扩容。

threshold的首次赋值由构造HashMap时传入的初始容量和装载因子决定。

threshold = 初始容量 * 装载因子

每次扩容桶（table）大小会变为原来两倍，threshold也会变为原来的两倍。

构造函数传入不是2的幂的初始容量会怎样？

不管传什么初始容量，都会经由tableSizeFor()计算得到大于等于传入的初始容量的最小的2的幂作为桶的实际容量大小

在put()时触发resize()，threshold也会被重新赋值为桶容量乘以装载因子。

tableSizeFor()算法过程是怎样的？

/**
* Returns a power of two size for the given target capacity.
*/
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;
}

分三种情况

1. cap小于0，返回1
2. cap经过位运算后大于等于MAXIMUM_CAPACITY，返回MAXIMUM_CAPACITY
3. cap经过位运算后返回n+1

先考虑正常的情况，对于一个给定的cap，分为两种情况，cap可能是2的幂或非2的幂。

1. 当cap不是2的幂，例如10，二进制为1010，cap - 1 = 1001，几个右移操作实际的结果就是从cap - 1的二进制的1的最高位开始到最低位全部变成1，最后返回n + 1就是2的幂了
2. 当cap是2的幂，例如16，二进制为10000，cap-1 = 1111，右移操作后n还是为1111，n+1就还是16

所以正常情况下tableSizeFor()得出的就是大于等于cap的数

如果cap一开始不减1，当cap是2的幂时，最后计算得出的就会是cap的2倍

cap小于0，没有实际的意义，不能表示桶容量，故而返回最小正整数1

cap大于等于MAXIMUM_CAPACITY时，MAXIMUM_CAPACITY是2的30次方，此时cap的二进制最高位1是在第31位，逻辑右移再加1会得到32个1，int中最高位（第32位）是符号位，最高位1表示负数了，没有意义，故而将最大值限定在2的30次方，2的30次方减1的二进制是从第1位到第30位全都是1

参考资料：

• HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）

为什么要调整桶大小？

为了减少散列冲突，减少元素查找次数

为什么桶初始容量是16？

这个问题不好解答可以考虑边界情况，桶容量过大、过小会导致什么

桶容量过大会导致大量空间浪费

桶容量过小会导致频繁扩容，扩容一次是耗时的

16应当是一个权衡评估后得出的值

默认装载因子为什么是0.75？

可以先考虑装载因子过大和过小分别会有什么问题

装载因子过大，表明哈希表填充率高，但是散列冲突的可能性大，查找元素的次数多

装载因子过小，表明哈希表的空闲空间大，空间利用率低，但冲突较少，查找元素次数少

0.75乘以2的幂是整数，不需要再做四舍五入，计算方便

根据HashMap注释

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.

参考资料

• HashMap defaultLoadFactor = 0.75和泊松分布没有关系
• HashMap的loadFactor为什么是0.75？
• StackOverflow: What is the significance of load factor in HashMap?

resize()的大致过程

根据resize()方法的注释所言，resize()会将桶容量扩充两倍，由于容量是2的幂，原来桶中的元素位置要么是原封不动，要么是再移动2的幂个位置。

求元素的在table中的索引依然是 元素key的hashCode & (桶容量-1)

例如原来容量是16，二进制为10000，求元素索引时是 hashCode & 1111

扩容两倍后容量是32，二进制位100000，求元素索引的计算变成了 hashCode & 11111，比之前多了一个1，如果元素key的hashCode在该位也是1，等同于元素的索引位置增加了2的幂。

桶中是链表时，会将链表划分为两个链表，一个留在原桶，一个放入移动了2的幂的桶中。

为什么要这样调整？原封不动不行吗？

因为这样做是为了保证散列均匀，减少冲突。

参考资料：

• Java HashMap工作原理及实现

为什么在解决hash冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树？

因为节点数过少时，红黑树的插入、删除的成本比链表要高很多。

在散列均匀的情况下，冲突较少，每个桶中链表的平均长度比较短，性能可接受。

为什么链表的长度为8时变成红黑树？

根据jdk1.8的HashMap中的注释所言，假设散列分布均匀，在负载因子为0.75的条件下，某一个桶中元素出现的频率满足λ为0.5的泊松分布。从概率来看，之所以链表长度超过 8 以后要变成红黑树，因为在散列分布均匀的情况下出现这种情况的概率小到忽略不计，一旦出现，几乎可以认为是散列函数设计有问题导致的，即散列不均匀。

所以红黑树是专门应对元素key糟糕的（分布不均匀）的散列函数而准备的。

二项分布：n次重复独立伯努利试验，一次伯努利实验只有两种对立的结果。

泊松分布：当二项分布的n很大，p很小时，可以近似为泊松分布。

算法第四版465页：

散列均匀时，每个桶的链表的平均长度为 实际元素总数 / 哈希表大小，这个就是装载因子λ

现在的问题就是，将N个元素随机放入M个桶，每个桶的元素平均个数为λ（N/M），求每个桶元素个数为k的概率。

对于某一个桶而言，一个元素放入桶中是一个二元结果，要么放入，要么不放入，散列均匀的情况下，不管有多少个桶，每个元素出现在同一个桶的概率是相同，每个桶中平均有λ个元素时，那么一个元素出现在同一个桶的概率就是λ/N，就是桶元素数量占元素总数的比值，理解很直观。

参考资料：

• 谈谈 HashMap 实现中的若干数学问题
• 泊松分布 (Poisson Distributions) 的推导

为何红黑树节点数在小于等于6时又变成链表？为什么不是小于等于8时变回链表？

是为了防止频繁插入和删除元素时不停的在树和链表之间互相转换、降低性能，红黑树和链表之间的转换是有成本的。

MIN_TREEIFY_CAPACITY是做什么的？

桶中元素超过TREEIFY_THRESHOLD个（8个）后，还要保证哈希表数组table的大小大于等于MIN_TREEIFY_CAPACITY才会把链表转红黑树，容量过小时使用红黑树性价比不高，用扩容来解决桶元素堆积的问题更适合。

这个值为什么要是4 * TREEIFY_THRESHOLD，是为了避免在resize和树化之间产生冲突，比如初始容量是16，装载因子0.75，存储元素有16*0.75=12个时就应该扩容，但是此时如果是4个元素在一个桶，8个元素在另外一个桶，是要先树化的，树化后再等resize扩容了，可能又要将红黑树链表化，这样反复来回影响性能。

平衡二叉搜索树中为何选用红黑树？用AVL树会有什么问题？红黑树和AVL树有何区别？

单次的插入和删除操作：

单次插入数据，红黑树和AVL树平均都只需要几次旋转即可完成。

单次删除元素，红黑树大多数只需要几次旋转调整，AVL树需要调整查找路径上所有结点。

大量的插入和删除操作：

红黑树由于是基于2-3树，3结点的存在可以吸纳一部分不平衡性，不用做频繁的旋转调整。

AVL树需要始终保持平衡，在大量插入或删除元素后，AVL树的调整的次数多于红黑树。

在大量数据的统计意义上，红黑树的插入和删除次数相对于AVL树较少，适合插入和删除频繁的场景。

AVL树由于是高度平衡的，红黑树不是高度平衡，AVL树的查找次数比红黑树更少，适合对查询效率非常敏感，插入和删除不频繁的场景。

红黑树的查询跟AVL树仍然是同一个数量级，所以综合查询、插入、删除的性能，红黑树表现较好。

参考

• 为什么STL和linux都使用红黑树作为平衡树的实现？ - Acjx的回答 - 知乎
• 红黑树比 AVL 树具体更高效在哪里？ - 伍亦勤的回答 - 知乎
• Difference between red-black trees and AVL trees
• 为什么Java8中HashMap链表使用红黑树而不是AVL树

put方法大致过程

1. 获取key的hashCode()并扰动
2. table数组为null则通过resize()初始化table，创建HashMap对象不会立刻初始化table数组
3. 利用扰动后的hashCode除留取余求得元素在table中的索引
4. 如果没有碰撞冲突，直接存入桶中
5. 如果有碰撞冲突，桶中维护一个链表存储哈希值相同的元素，java7是头插法，java8是尾插法
6. 链表长度超过TREEIFY_THRESHOLD，链表转为红黑树
7. 如果元素已存在，替换value。元素存在先通过key的hashCode查看桶中是否有元素，没有则不存在，有元素需要依次遍历桶中元素，通过key的equals方法比较是否相等，有相等的则存在。
8. 哈希表实际存储元素数量超过了阈值threshold（哈希表大小 * 装载因子），调用resize()扩容。

get方法的大致过程

1. 获取key的hashCode()并扰动
2. 根据哈希值求得table索引
3. 若桶中第一个元素命中，直接返回
4. 有冲突则依次遍历链表或红黑树，通过key的equals比较来寻找目标节点，找到了返回其value，没有找到返回null

HashMap为什么线程不安全？高并发下会产生什么问题？

一句话：jdk7的HashMap在扩容时会改变链表中元素原本的顺序，高并发情况下容易导致链表产生环，进而导致死循环，CPU占用率飙升到100%。

jdk7中扩容采用头插法是考虑到缓存的时间局部性原则，最近访问过的数据下次大概率会再次访问，把刚访问过的元素放在链表最前面可以直接被查询到，减少查找次数。

jdk8中扩容改为尾插法，高并发情况下不会产生死循环了，但是resize依然不是原子性的，可能会产生数据丢失。

其他方法例如链表和红黑树互转的过程，都不是原子性的，都可能会产生数据丢失的问题。

参考

• 为什么HashMap线程不安全

Java 8 对HashMap做出了哪些改进？

1. 桶中链表长度超过8将链表转为红黑树，以应对不均匀的散列函数导致的查询次数增多
2. 链表插入元素由头插法改为尾插法，以解决并发下插入元素时链表产生环进而导致的死循环

modCount是做什么的？

对哈希表做出了修改（添加和删除元素），modCount就会增加，表示修改的次数，使用迭代器迭代哈希表时一旦发现modCount变化了，就会立刻抛出ConcurrentModificationException，以避免迭代时的不确定性，这称为fail-fast机制。注意修改一个已存在的元素的value不改变modCount。

HashMap的缺点是什么？想要用哈希表还有哪些选择？

缺点就是结构复杂，占用内存可能较多，对哈希表有简单需求的地方不需要这么复杂而完善的类

例如ThreadLocalMap就自己实现了一套简单的哈希表，采用开放定址法

还有Android上SparseArray、ArrayMap实现的内存消耗更低的哈希表

HashMap与Hashtable的区别？

1. Hashtable的get、put、clear、contains、size等大部分方法上都加上了synchronized关键字，给整个对象上锁，HashMap非线程安全
2. Hashtable中没有红黑树仅有链表
3. Hashtable继承Dictionary类，HashMap实现Map接口
4. Hashtable不允许null的key和value，而HashMap都允许
5. Hashtable求key的hashCode没有扰动
6. HashMap和Hashtable使用Iterator遍历元素过程中对哈希表添加或删除元素是会抛出异常的（fast-fail），但Hashtable用Enumeration迭代时不会fast-fail，因为通过Enumeration的nextElement()获取下一个元素时没有对modCount做判断，而Iterator的next方法对modCount做了判断。
7. Hashtable是jdk1添加的，HashMap是jdk2添加的

Dictionary已被废弃，所以Hashtable已经被废弃，而且同步性能较差，大多数操作都会锁住整个对象。用jdk1.5引入的采用分段锁的ConcurrentHashMap同步性能更好。