HashMap详解
LeeBoom 人气:0-
HashMap源码解析(以jdk1.8为例)
- 简介
- put方法
-
初始化 && 扩容
- 扩容的具体过程
-
1.7 和 1.8 jdk中HashMap的对比
- 链表死循环问题
HashMap源码解析(以jdk1.8为例)
简介
HashMap是一个哈希表,它是 非线程安全的,且允许key和value为null.
HashMap采用 数组 + 链表 + 红黑树 的形式来存储数据.不保证插入顺序
put方法
- 判断table是否为空,如果为空或者大小为0,则调用resize()对table进行初始化
- 将key的hash运算后的值 与 数组长度-1 做一次 相与即hash(key) & (table.length-1),得到指定下标。取余的方法采用hash(key) & (table.length-1),等价于hash(key)%table.length.原因是HashMap要求数组的长度必须为2的指数,因此table-1的二进制低位全部为1,hash(key) & (table.length-1)相当于抹除其高位,剩下的就是余数。
- 如果table指定下标位置上为空,则新建一个链表,将键值对作为节点插入
- 否则依次遍历下标指向的链表上的每一个节点,通过key.equals()来判断是否是要找的那个entry。
- 如果当前链表上没有相同的key,则采用尾插法向链表尾部插入数据。如果当链表插入完成后,链表存储的节点的个数>=8时,会调用treeifyBin方法,将链表转换成红黑树.(之所以选择8是根据概率得出的,注释里有说明),当节点删除完,红黑树大小<=6时,会退化成链表
如果有相同的Key,则覆盖
/** *
* 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
**/
初始化 && 扩容
HashMap在初始化的时候,如果没有指定 加载因子和容量, 会调用默认的构造函数,将加载因子设为 0.75,容量设为16。当HashMap中的元素个数超过 容量*加载因子时,HashMap会发生扩容。即++size > load factor * capacity ,这个过程发生在放入键值对之后。
每次扩容都会将当前的容量扩大2倍。为什么容量一定要2n其实是因为取余方便。
扩容的具体过程
- 判断数组容量是否大于0
- 等于0则进行初始化
- 如果加载因子和容量都为0,则调用默认的大小和阈值
- 如果有设置加载因子和容量,则使用构造函数中的初始化的容量
- 大于0,则进行扩容,扩容后的容量大小为原来的两倍,之后将元素重新进行运算并复制到新的table当中。
1.7 和 1.8 jdk中HashMap的对比
插入方法上: 1.7采用头插法,1.8采用尾插法。
1.7中hashMap的实现是采用数组+链表的形式,采用头插法容易出现逆序,且在并发情况下会产生环形链表死循环问题
1.8后HashMap则采用数组+链表+红黑树的形式,当链表长度超过8时,则会将链表转成红黑树。且采用尾插法避免了并发情况下发生的死循环问题。但是仍不建议在并发情况下使用HashMap,而是使用ConcurrentHashMap
链表死循环问题
jdk 1.7中,当扩容完成后,会把数据从老的hash表中迁移到新的hash表中,高并发下,同时有两个或以上线程执行这段代码,会发生链表死循环。具体流程如下:
旧表因容量为2太小发生扩容,新建一个新的哈希表,大小为4
旧表数据向新表逐个迁移
线程1卡在获取旧哈希表的链表上.此时线程1的e指向键值对3,next指向键值对7
而线程2已经完成了整个的数据再分配
- 将3分配到下标3
- 将5分配到下标1
- 将7分配到下标3
线程1回来继续执行
- 将节点3的next指针指向原下标3的链表,新数组下标3为null,所以和之前一样 e.next = newTable[i];
- 并将下标3指向节点3 newTable[i] = e;到此头插法完成
- 将e指向节点7 e = next; 而新一轮循环中,Entry
next = e.next; 节点3又被选为next - 线程一接着工作。把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移。又因为e = next,节点3再次被选为e,而next为null
- 下一次循环中,将e插入到链表头部,接着e.next = newTable[i],节点3的next指针指向7,环形链表出现。可以发现是头插法导致了key(3).next 指向了 key(7)
void transfer(Entry[] newTable)
{
Entry[] src = table;
int newCapacity = newTable.length;
//下面这段代码的意思是:
// 从OldTable里摘一个元素出来,然后放到NewTable中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;// <--假设线程一执行到这里就被调度挂起了
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
加载全部内容