HashMap原理
Hash原理:
1,特性:
1⃣️,键值对key-value,实现了map接口
2⃣️,允许使用null作为key
3⃣️,无序
4⃣️,线程不安全(线程安全推荐考虑currentHashMap)
2,基础属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子0.75 static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默认数组 transient int size; //HashMap中元素的数量 int threshold; //判断是否需要调整HashMap的容量
|
HashMap的扩容操作是一项很耗时的任务,所以如果能估算Map的容量,最好给它一个默认初始值,避免进行多次扩容。
3,HashMap和Hashtable的区别
|
hashMap |
hashTale |
线程安全 |
不安全 |
安全(synchronized)
|
Null作为 key |
允许 |
不允许 |
集成结构 |
Map接口的实现
|
实现了Map接口和Dictionary抽象类
|
运行速度 | 快 | 慢(推荐用currentHashMap代替) |
4,数据结构
HashMap采用Entry数组来存储k-v对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体,以此来解决Hash冲突的问题。
注:hashMap的链表中大小超过8会自动转为红黑树,当删除小于等于6时候重新转为链表。(7时不操作)
5,扩容机制
1⃣️,扩容时机 ,大于等于阀值时候扩容(数组长度*负载因子)
2⃣️,扩容方式,在java中数组无法扩容,所以新建一个数组替换容量小的数组
3⃣️,扩容大小,原来大小的2倍
4⃣️,扩容后存放位置,
Jdk1.8之前用的是mod进行hash运算,需要重新计算,消耗比较大
Jdk1.8以后用的是位与运算,经过rehash之后,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置,下面进行重点讲解:
看下图,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。
元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:
因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:
这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。