key-value
的存储形式进行存放键值对。HashMap 的实现是不同步的,这意味着它不是线程安全的。他的 key、value 都可以为 null。此外,HashMap 中的映射不是有序的。将链表转换成红黑树前会进行一次判断,即使阈值大于 8,但是数组长度小于 64,此时并不会将链表变为红黑树。而是选择进行数组扩容。
这样做的目的是因为数组比较小,尽量避开红黑树结构,这种情况下编委红黑树结构,反而会降低效率。因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡。同时数组长度小于 64 时,搜索时间相对要快。
所以综上所述,为了提高性能和减少搜索时间,底层在阈值大于 8 且数组长度大于 64 时,链表才转换为红黑树。具体参考 treeifyBin
方法。
当然虽然增加了红黑树作为底层数据结构,结构变复杂了,但是阈值大于 8 且数组长度大于 64 时,链表转换为红黑树时,效率也变得更高效了。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在的一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行速度和更快的存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构:就是存储数据的一种方式。
HashMap<String,Integer> map = new HashMap<>();
Entry[] table
用来存储键值对数据的。Node[] table
用来存储键值对数据的。小明-5
,根据 key
调用 String 类中重写之后的 hashCode() 方法计算出值,然后结合 数组长度 并采用 特定算法(例如:对长度取余)计算出向 Node 数组中存储数据的空间的索引值。
王阿姨-23
,假设该键值对结合数组长度计算出的索引值也是 6 ,且此时数组空间不为 null,那么底层会比较 王阿姨
和 老王
的 hash 值是否一致。
王阿姨-23
(见图);小明-18
,那么其计算出的 索引值 值肯定是 3,且计算出的 hash 值相等,则此时发生 哈希冲突(哈希碰撞) 。此时会调用 小明-5
的 equals 方法对 小明-18
进行比较内容是否相等。
面试题 1 :哈希表底层采用何种计算方式计算hash值?还有那些算法可以计算出hash值? 解答: 1. HashMap 底层采用 key 的重写 hashCode() 方法结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引。 2. 还可以采用:平方取中值法、取余法、伪随机数。 3. 10%8=2,11%8=3,其他计算方式效率较低,而位运算效率要高。
面试题 2 :当两个对象的 hashCode 相等时会发生什么? 解答: 会发生哈希碰撞,若 key 值内容相同则替换旧的 value ,不然连接到链表的后面,直至链表长度超过阈值 8 且数组长度超过 64 时再采用红黑树存储。
面试题 3 :何时会发生哈希碰撞,什么是哈希碰撞,如何解决哈希碰撞? 解答: 只要两个元素的 key 经过计算后得到的 hash 值相同就会发生碰撞。JSDK8 以前采用链表来解决哈希碰撞。JSDK8 以后采用链表+红黑树来解决哈希碰撞。
面试题 4 :如果两个键的 hashCode 相同,如何存储键值对? 解答: hashCode 相同,通过 equals 比较内容是否相同并递归地进行如下的比较操作。 相同:将新的 value 覆盖旧的 value。 不相同:将新的键值对添加到哈希表中。
问题描述:针对传统 hashMap 的缺点,JDK1.8 为什么引入红黑树?这样结构不是更麻烦吗?为何阈值大于 8 就要换成红黑树?
说明:
HashMap继承关系如下:
补充问题: 通过上述继承关系我们发现一个问题。HashMap 已经继承了 AbstractMap 而 AbstractMap 类实现了 Map 接口,那 HashMap 为什么还要再继续实现 Map 接口呢?同样在 ArrayList 中与在 LinkedList 中都是这样的结构的设计思路是什么? 解答: 据 java 集合框架创始人 Josh Bloch 描述,这样写是一个失误。在 java 集合框架中,类似这样的写法很多,最开始写 java 集合框架的时候,他认为这样写在某些地方可能是有价值的,直到他意识到错了。很显然,JDK 的维护者,后来不认为这个小小的失误值得去修改,所以就这样保留下来了。
private static final long serialVersionUID = 362498820763181265L;
//默认的厨师容量是16 -- 1 << 4 相当于 1*2^4 -- 1*16
static final int DEFAULE_INITAL_CAPACITY = 1 << 4;
问题: 为什么必须是 2 的 n 次幂?如果输入值是 10 会怎么样? 解答: HashMap 构造方法还可以指定集合的初始化容量大小:
HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子(0.75)的空 HashMap。
综上所述,我们已经知道,当向 HashMap 中添加一个元素的时候,需要根据 key 的 hash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,要尽量减少 哈希碰撞,就是要尽量吧数据分配均匀,每个链表长度大致相同。这个实现,就是“把数据存到哪个链表中”的算法。
为什么必须是 2 的 n 次幂 该算法的实际就是取模,hash%length
,计算机中直接取余的笑料并不如位运算。所以源码中作乐优化,使用了 hash%(length-1)
,而实际上 hash%length
的前提条件就是 length
必须是 2 的 n 次幂。
为什么能均匀分布减少哈希碰撞 2 的 n 次幂实际就是 1 后面 n 个 0 ,2 的 n 次方 - 1 实际就是 n 个 1。
举例说明: 按位与运算:相同的二进制数位上,都是 1 的时候,结果为 1,否则为 0。
"如果是 2 的 n 次幂"
例如长度为 8 的时候, 3&(8-1)=3 2%(8-1)=2 , 不同位置上不碰撞。
例如长度 length 为 8 的时候, 8 是 2 的 3 次幂,二进制是:00001000
00001000 → 8
- 1
--------
00000111 → 7
如下所示:
hash & (length - 1)
3 & (8 - 1) = 3
00000011 → 3 hash
& 00000111 → 7 length-1
----------------------
00000011 → 3 数组下标
hash & (length - 1)
2 & (8 - 1) = 2
00000010 → 2 hash
00000111 → 7 length-1
----------------------
00000010 → 2 数组下标
说明:上述计算结果是不同位置上的,不发生碰撞。
"如果不是 2 的 n 次幂"
例如长度为 9 的时候, 3&(9-1)=0 2&(9-1)=0 , 都在 0 位置上发生了哈希碰撞。
例如长度 length 为 9 的时候, 9 不是 2 的 n 次幂, 二进制是:00001001
00001001 → 9
- 1
--------
00001000 → 8
如下所示:
hash & (length - 1)
3 & (9 - 1) = 0
00000011 → 3 hash
& 00001000 → 8 length-1
----------------------
00000000 → 0 数组下标
hash & (length - 1)
2 & (9 - 1) = 2
00000010 → 2 hash
& 00001000 → 8 length-1
----------------------
00000000 → 0 数组下标
说明:上述计算结果都在 0 位置上,发生了哈希碰撞。
注意:当然,如果不考虑效率,直接取余即可(就不需要要求长度必须是 2 的 n 次方了)
hash%(length-1) == hash%length
//创建HashMap集合对象,指定数组长度为10
HashMap map = new HashMap(10);
public HashMap(int initalCapacity) {
this(initalCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initalCapacity, float loadFactor) {
//initalCapacity = 10
if(initalCapacity < 0)
throw new IllegalArgumentException("Illegal inital capacity: " + initalCapacity);
if(initalCapacity > MAXIMUN_CAPACITY)
initalCapacity = MAXIMUN_CAPACITY;
if(loadFactor <= 0 || FLoat.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initalCapacity);
//initalCapacity = 10
}
static final int tableSizeFor(int cap) {
//int cap = 10
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
}
由此可以看出,当在实例化 HashMap 实例时,如果给定来 initalCapacity(假设是10)由于 HashMap 的 capacity 必须都是 2 的幂指数 ,因此这个方法用于找到大于等于 initalCapacity 的最小 2 指数(如果已经是,则直接返回)。
int n = cap - 1; // cap = 10 n = 9
n |= n >>> 1;
00000000 00000000 00000000 00001001 → 9 n
| 00000000 00000000 00000000 00000100 → 4 n>>>1
-------------------------------------
00000000 00000000 00000000 00001101 → 13 |=
由于 n 不等于 0,则 n 的二进制表示中总会有一个 bit 为 1,这是考虑最高位的 1。通过无符号右移 1 位,则将最高位的 1 右移了 1 位,再做或操作,使得 n 的二进制表示中与最高位的 1 紧邻的右边一位也为 1 。
n |= n >>> 2;
00000000 00000000 00000000 00001101 → 13 n
| 00000000 00000000 00000000 00000011 → 3 n>>>2
-------------------------------------
00000000 00000000 00000000 00001111 → 15 |=
注意,这个 n 已经经过了 n |= n >>> 1;
的操作。
n |= n >>> 4;
00000000 00000000 00000000 00001111 → 15 n
| 00000000 00000000 00000000 00000000 → 0 n>>>4
-------------------------------------
00000000 00000000 00000000 00001111 → 15 |=
以此类推。
注意,容量最大也就是 32 bit的正数,因此最后 n |= n >>> 16;
最多也就 32 个 1 (已经是负数。在执行 tableSizeFor 之前,对 initalCapacity 作了判断,如果大于 MAXIMUN_CAPACITY (2 ^ 30) 会执行位运算,所以这里面的位运算操作之后,最大为 30 个 1,不会大于等于 MAXIMUN_CAPACITY。30个 1,加 1 之后得到 2 ^ 30)
经过所有按位或运算之后将值赋给 threshold 。
问题:为什么 Map 桶中节点个数超过 8 才转为红黑树结构?
8 这个阈值定义在 HashMap 中,针对这个成员变量,在源码的注释中只说明了 8 是 bin(bucket::桶)从链表转为树的阈值,但没有说明为什么是 8。 在 HashMap 对象中的说明为:
因为树节点的大小约为普通节点的 2 倍,所以我们只在箱子包含足够的节点时才使用树节点(参考 TREEIFY_THRESHOLD)。当它们变得太小(由于删除或调整大小)时,就会被转换会普通的桶。在使用分布良好的用户 hashcode 时,很少使用树箱。理想情况下,在随机哈希码下,箱子中节点的频率服从泊松分布。 (http://en.wikipedia.org/wiki/Poisson_distribution) 默认阈值为 0.75,平均参数约为 0.5,尽管由于调整粒度的差异很大,忽略方差,列表大小 k 的预期出现次数为 (exp(-0.5) * pow(0.5,k) / factorial(k))
节点位置 | 存储概率 |
---|---|
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 |
TreeNodes 占用空间是普通 Nodes 的两倍,所以只有当 bin 包含足够多的节点时才会转换成 TreeNodes,而“是否足够多”就是有 TREEIFY_THRESHOLD 的值决定的。当 bin 中节点数变少时,又会转成普通的 bin。并且查看源码可以发现,链表长度达到 8 就转成红黑树,长度降为 6 就传承普通 bin。
这样就解释了为什么不是一开始就将其转换为 TreeNodes,而是需要一定节点数才能转换为 TreeNodes,说白就是权衡了空间与时间。
当 hashCode 离散性很好的时候,树型 bin 用到的概率非常小,因为数据均匀分布在每个 bin 中,几乎不会有 bin 中链表的长度能够达到阈值。但是在随机 hashCode 下,离散性会变差,然而 JDK 又不能阻止用户实现这种不好的 hash 算法,因此就可能导致不均匀的数据分布。
不过理想情况下随机 hashCode 算法下所有 bin 中节点的分布频率会遵循泊松分布,我们可以看到,一个 bin 中链表长度达到 8 个元素的概率仅为 0.00000006,几乎是不可能事件,所以,之所以选择 8 ,不是随便决定的,而是根据概率统计决定的。
Poisson分布(泊松分布),是一种统计与概率学里常见的离散[概率分布]。 泊松分布的概率函数为:
P(X=k)=λkk!e−λ,k=0,1,...P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda},k=0,1,... P(X=k)=k!λke−λ,k=0,1,...
泊松分布的参数 λ\lambdaλ 是单位时间(或单位面积)内随机事件的平均发生次数。泊松分布适合描述单位时间内随机事件的发生次数。
红黑树的平均查找长度是 log(n)log(n)log(n) ,如果长度为 8 ,平均查找长度为 log(8)=3log(8)=3log(8)=3 ,链表的平均查找长度为 n2\frac{n}{2}2n ,当长度为 8 时,平均查找长度为 82=4\frac{8}{2}=428=4 ,这才有转换成树的必要,链表长度如果是小于等于 6,62=3\frac{6}{2}=326=3 ,而 log(6)=2.6log(6)=2.6log(6)=2.6 ,虽然速度也很快,但是转化为树结构和生成树的时间并不会很短。
//当桶(bucket bin)上的节点数小于这个值时树转为链表
static final int UNTREEIFY_THRESHOLD = 6;
当 Map 里面的数量超过这个值时,表中的桶才能树形化,否则桶内元素太多时会发生扩容,而不是树形化。为了避免扩容操作、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD(8)
//桶中结构转化为红黑树对应的数组长度的最小值
static final int MIN_FREEIFY_CAPACITY = 64;
重难点,必须是 2 的 n 次幂
//存储元素的数组
transient Node<K,V>[] table;
table 在JDK1.8 中我们了解到 HashMap 是由数组+链表+红黑树组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry<K,V>
类型。从 JDK1.8 之后是 Node<K,V> 类型。只是换了个名字,但都实现了同样的接口:Map.Entry<K,V>
。负责存储键值对数据。
//存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;
//存放元素个数,注意这个不等于数组的长度
transient int size;
size 为 HashMap 中 key-value 的实时数量,不是数组 table 的长度。
//每次扩容和更改map机构的计数器
transient int modCount;
//临界值 当实际大小(容量 * 负载因子)超过临界值时,会进行扩容
int threshold;
//加载因子
final float loadFactor;
说明:
size/capacity
,而不是占用桶的数量去除以 capacity
。capacity 是桶的数量,也就是 table 的长度 length 。0.75
是官方给出的一个比较好的临界值。//构造方法:
HashMap(int initalCapacity, float loadFactor)
//构造一个带制定初始容量和加载因子的空 HashMap
loadFactor 越趋近于 1 ,那么数组中存放的数据(entry)也就越多、越密集,也就是会让链表的长度增加。反之成立。
如果希望链表尽可能少一些。要提前扩容,有的数组空间有可能一直没有存储数据。加载因子要尽可能地小一些。
举例:
HashMap 中重要的构造方法如下:
构造默认的初始容量为 16,默认负载因子为 0.75
public HashMap() {
//将默认的加载因子0.75赋值给loadFactor,并没有创建数组
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//指定"容量大小"的构造函数
public HashMap(int initalCapacity) {
this(initalCapacity, DEFAULT_LOAD_FACTOR);
}
/*
指定"容量大小"和"加载因子"的构造函数
initalCapacity:指定的容量
loadFactor:指定的加载因子
*/
public HashMap(int initalCapacity, float loadFactor) {
//判断初始化容量initalCapacity是否小于0
if(initalCapacity < 0)
//如果小于0,则抛出非法的参数异常
throw new IllegalArgumentException("Illegal inital capacity: " + initalCapacity);
//判断初始化容量initalCapacity是否大于最大容量(2^30)
if(initalCapacity > MAXIMUN_CAPACITY)
//如果超过回滚容量大小
initalCapacity = MAXIMUN_CAPACITY;
//判断负载因子loadFactor是否小于等于0或者是否为一个数值
if(loadFactor <= 0 || FLoat.isNaN(loadFactor))
//如果满足上述条件之一则跑出异常
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//将特定的加载因子赋值给HashMap成员变量的负载因子loadFactor
this.loadFactor = loadFactor;
//调用tableSizeFor()方法对初始化容量initalCapacity进行调整与判断
this.threshold = tableSizeFor(initalCapacity);
}
static final int tableSizeFor(int cap) {
//int cap = 10
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUN_CAPACITY : n + 1;
}
说明:
对于 this.threshold = tableSizeFor(initalCapacity);
的解释:
tableSizeFor(initalCapacity) 判断制定的初始化容量是否为 2 的 n 次幂,如果不是那么会变为比指定初始化容量稍小一点的 2 的 n 次幂。上文已提及过。 但是注意,在 tableSizeFor 方法体内部将计算后的数据返回给调用这里了,并且直接复制给 threshold 边界值。 但很多人会认为应该这样写:
this.threshold = tableSizeFor(initalCapacity) * this.loadFactor
但是,在 jdk8 以后的构造方法中,并没有对 table 这个成员变量进行初始化,table 的初始化被推迟到了 put 方法中,在 put 方法中会对 threshold 重新计算,put 方法的具体实现见下文。
//构造一个映射关系与指定 Map 相同的新的 HashMap
//利用协变将泛型向上转变
public HashMap(Map<? extends K, ? extends V> m) {
//负载因子loadFactor编委默认的负载因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
最后调用 putMapEntries()
方法:
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取参数集合的长度
int s = m.size();
if(s > 0) {
//判断参数集合长度是否大于0
if(table == null){
//判断table是否已经初始化 pre-size
//未初始化,s为m的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUN_CAPACITY) ? (int)ft : MAXIUM_CAPACITY);
//计算得到的t大于阈值,则初始化阈值
if(t > threshold)
threshold = tableSizeFor(t);
} else if(s > threshold)
//已初始化,并且m元素的个数大于阈值,进行扩容处理
resize();
//将m中的所有元素添加至HashMap中
for(Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}