亲宝软件园·资讯

展开

HashMap详解

LeeBoom 人气:0
  • HashMap源码解析(以jdk1.8为例)
    • 简介
    • put方法
    • 初始化 && 扩容
      • 扩容的具体过程
  • 1.7 和 1.8 jdk中HashMap的对比
    • 链表死循环问题

HashMap源码解析(以jdk1.8为例)

HashMap结构图

简介

HashMap是一个哈希表,它是 非线程安全的,且允许key和value为null.
HashMap采用 数组 + 链表 + 红黑树 的形式来存储数据.不保证插入顺序

put方法

  1. 判断table是否为空,如果为空或者大小为0,则调用resize()对table进行初始化
  2. 将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)相当于抹除其高位,剩下的就是余数。
  3. 如果table指定下标位置上为空,则新建一个链表,将键值对作为节点插入
  4. 否则依次遍历下标指向的链表上的每一个节点,通过key.equals()来判断是否是要找的那个entry。
  5. 如果当前链表上没有相同的key,则采用尾插法向链表尾部插入数据。如果当链表插入完成后,链表存储的节点的个数>=8时,会调用treeifyBin方法,将链表转换成红黑树.(之所以选择8是根据概率得出的,注释里有说明),当节点删除完,红黑树大小<=6时,会退化成链表
  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其实是因为取余方便。

扩容的具体过程

  1. 判断数组容量是否大于0
  2. 等于0则进行初始化
    1. 如果加载因子和容量都为0,则调用默认的大小和阈值
    2. 如果有设置加载因子和容量,则使用构造函数中的初始化的容量
  3. 大于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表中,高并发下,同时有两个或以上线程执行这段代码,会发生链表死循环。具体流程如下:

  1. 旧表因容量为2太小发生扩容,新建一个新的哈希表,大小为4

    扩容并重新分配

  2. 旧表数据向新表逐个迁移

  3. 线程1卡在获取旧哈希表的链表上.此时线程1的e指向键值对3,next指向键值对7

  4. 而线程2已经完成了整个的数据再分配

    1. 将3分配到下标3
    2. 将5分配到下标1
    3. 将7分配到下标3
  5. 线程1回来继续执行

    1. 将节点3的next指针指向原下标3的链表,新数组下标3为null,所以和之前一样 e.next = newTable[i];
    2. 并将下标3指向节点3 newTable[i] = e;到此头插法完成
    3. 将e指向节点7 e = next; 而新一轮循环中,Entry next = e.next; 节点3又被选为next
    4. 线程一接着工作。把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移。又因为e = next,节点3再次被选为e,而next为null
    5. 下一次循环中,将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);
        }
    }
} 

加载全部内容

相关教程
猜你喜欢
用户评论