HashMap底层机制及数据结构
如下图,HashMap底层其实是一个k-v结构的Entry数组,同时为了解决hash冲突问题,也存在链表结构。另外在1.8版本之后,为了优化链表结构,又引入红黑树,使得数据存储更加合理。
名词 | 解释 | 补充 |
---|---|---|
Entry | 是一种数据结构单元,存储key-value类型,key不可以重复,value可以重复。还有,entry持有一个指向下一个元素的引用,这就构成了链表。 | |
HashCode | 哈希码并不是完全唯一的,它是一种算法,让同一个类的对象按照自己不同的特征尽量的有不同的哈希码,但不表示不同的对象哈希码完全不同。 | |
红黑树 | 是一种自平衡二叉查找树,是对链表结构的优化,是一种在更删改查的效率方面更为均衡的数据结构。 | |
Hash冲突 | 当数据经过hashcode得出来的hash值一样,在entry中就会映射同一个key值对应的index位置,就会出现”冲突“。但是通过链表结构可以解决这个问题,当一个index有多个数据时,就会将数据通过链表的方式存储,但是链表长度过长会削弱链表结构的优势。jdk1.8之后为了解决这个问题,将链表结构优化成红黑树。 | |
扩容(负载)因子 | 在jdk1.7中,默认为0.75,是决定是否扩容的一个参考因素,但并非达到扩容阈值threshold(数组长度*负载因子)就会扩容。扩容条件是(size >= threshold) && (null != table[bucketIndex]),表示不但要满足已有键值对数量达到扩容阀值,还得确定数组位置已存在数据,发生hash冲突。反过来说就是,如果数组位置是空的,没有hash冲突,该位置可用,那么即使达到了扩容阀值也不会扩容。也就是说,未达到阀值或未发生hash冲突时是不会扩容的。 |
几点介绍:
-
jdk1.8之前,hashmap的默认数组长度为16,扩容机制如下
(1)、就是hashmap在存值的时候(默认大小为16,负载因子0.75,阈值12),可能达到最后存满16个值的时候,再存入第17个值才会发生扩容现象,因为前16个值,每个值在底层数组中分别占据一个位置,并没有发生hash碰撞。
(2)、当然也有可能存储更多值(超多16个值,最多可以存26个值)都还没有扩容。原理:前11个值全部hash碰撞,存到数组的同一个位置(这时元素个数小于阈值12,不会扩容),后面所有存入的15个值全部分散到数组剩下的15个位置(这时元素个数大于等于阈值,但是每次存入的元素并没有发生hash碰撞,所以不会扩容),前面11+15=26,所以在存入第27个值的时候才同时满足上面两个条件,这时候才会发生扩容现象。
-
jdk1.8及其以后,hashmap的默认数组长度为64,扩容机制如下
(1)、因为扩容比较消耗资源,所以应该尽量避免。但是在链表结构中,如果链表长度过长,会极大影响数据的查改效率,因此引入性能更加均衡的红黑树。
(2)、扩大数组长度也是为了减少扩容机制的触发,其负载因子与jdk1.8之前一样为0.75。但是不同于jdk1. 7,放入key之前先扩容,放入后不重新判断是否扩容。达到阀值且hash冲突时才扩容。不发生hash冲突,可超过阀值。因此jdk1.7最多存个数:threshold+table.length-1,如介绍1。jdk1.8中,放入key之后再判断是否达到阈值,超过阈值就扩容,与是否hash冲突无关,因此最多存放key个数与阀值相同。
-
jdk1.8中hash“冲突”时的解决方案
(1)、如果冲突数量小于8,则是以链表方式解决冲突。
(2)、而当冲突大于等于8时,就会将冲突的Entry转换为红黑树进行存储。
(3)、而又当数量小于6时,则又转化为链表存储。