深入理解HashMap

HashMap的继承关系

通过Idea,我们可以轻易得到HashMap的继承关系。如下图所示

可以看到,HashMap实现了Cloneable、Serializable、Map三个接口,继承了AbstractMap虚基类。Map是”key-value键值对”接口,AbstractMap实现了”键值对”的通用函数接口。Serializable使HashMap支持序列化,Cloneable使得HashMap覆写clone方法时不抛出异常。

基本原理和数据结构

在jdk1.8 前,HashMap内部以数组+链表的数据结构实现,jdk及1.8之后在原基础上加入了红黑树。当实例化一个HashMap时,系统会创建一个长度为Capacity的数组(这个长度是多少?),这个长度就是HashMap的容量。这个数组存放元素的位置我们称之为Hash桶。每个桶都有自己的索引,系统可以根据存入的Key计算对应的索引,并将对应的Value存入桶内。

由于数组大小有限以及计算Hash值对应的数组索引的算法的原因(出现Hash碰撞),必然会导致在数组的同一个位置内(同一个桶内)会有多个索引一样的键值对需要存储,此时就引入了链表。每个桶种的元素都可以携带一个引用变量,用于指向存放在同一个桶内的下一个元素,这样在每个桶内就有可能形成一个链表。如下图

光使用数组+链表的话就容易存在这样的问题:当桶内元素越来越多的时候,链表也越来越长,这样查找的时间复杂度就由O(1),退化到了查找链表的O(n)。由此,jdk8之后引入了红黑树。它的策略是这样的,当链表长度大于8的时候(为什么是8?),就将链表转化为红黑树,当红黑树的节点个数不大于6的时候,就转换为链表(为什么又是6?)。

HashMap的构造函数

构造函数

public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map m)

初始容量和负载因子

在上面的构造函数中,我们可以看到在实例化HashMap时可以自由设置HashMap的容量和负载因子。在源码中,默认的初始容量是1 << 4(即16),负载因子是0.75。

负载因子为什么是0.75

负载因子是用于标识何时扩容的参数,当存储量达到了0.75 * 容量时,就会开始扩容。选择0.75是为了在空间和时间上达到一个平衡,大于0.75虽然节省了空间,但是扩容时花费的时间会过长,当小于0.75时,虽然扩容快了,但是也会导致频繁扩容,浪费了大量空间。

为什么初始容量是16

其实不一定需要是16,他的要求实际上是一定要为2的幂。这样,length-1对应的二进制值就全为1。在HashMap中,以(length - 1) & hash来计算数组下标,length-1正好相当于一个“低位掩码”,只要length-1的二进制全为1且hash比较均匀,那么Hash算法的结果就是均匀的,&相当于对hash求余运算,只不过&相对%而言较快。

哈希函数与数组映射

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

hashCode是源自Object类的hashCode方法(实现方式和原理可以点此查看),该方法是一个native方法,返回了一个hash值,但HashMap没有直接使用这个值,而是采用一次16位右位移异或混合的结果作为hash。

这段代码叫“扰动函数”,在计算数组下标时,“与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做数组下标访问。在有限位下,即使Hash再分散也是容易形成数组下标分布不均的结果,这时候“扰动函数”的价值就体现出来了,右位移16位,正好是32bt的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。

为什么链表长度要选择在8的时候转变为红黑树?

TreeNode节点大小约是普通节点的两倍,且理想情况下,如果hash函数比较完美,那么存储的键值对可以相对均匀的分布在桶内,这样,元素的分布规律符合参数为0.5的泊松分布,在桶里的元素超过8的概率十分小(8: 0.00000006),所以在随机HashCoded的理想情况下,很少使用树。

其次,红黑树的平均查找长度是log(n),如果长度为8,平均查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;

为什么要在红黑树的节点为6的时候转变为链表?

链表长度如果是小于等于6,6/2=3,而log(6)=2.6,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短,这时候显然链表更合适。

Put操作源码解读

本小节以源码注释的方式讲解Put流程

源码:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal操作:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; //缓存底层数组用,都是指向一个地址的引用————>桶
    Node p; //插入数组的桶i处的键值对————>插入的数据
    int n, i; //数组的长度和要插入位置的下标

    //如果数组为空,则重新分配空间,这里可以看出,HashMap并不是实例化了就新建数组,而是在进行第一次put操作的时候新建的数组
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    ///(n - 1) & hash:根据hash值算出插入点在底层数组的桶的位置,即下标值;为p赋值,也为i赋值(不管碰撞与否,都已经赋值了)
    //如果要插入的位置为空,那么就插入节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//发生了Hash碰撞,即当前的桶内已经有节点了


        Node e; K k;
        //这个p已经在前面的if条件进行过赋值,代表要插入的节点
        //如果p的hash值和key都等于i = (n - 1) & hash这个位置的节点,那么说明是同一个节点,先换给e
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //jdk1.8之后引入了红黑树处理碰撞
        //如果p节点是一个树节点,那么就调用插入树的方法
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);;//如果是,则走添加树的方法。
        else {
        //既不是同一节点,也不是树节点,那么就是添加新的节点,进行更新操作
        //还未形成树结构,还是jdk 1.7的链表结构
            for (int binCount = 0; ; ++binCount) {
           //判断p.next是否为空,同时为e赋值,若为空,则p.next指向新添加的节点,这是在链表长度小于7的时候
           //jdk1.8及之后用的是尾插法,即放在链的尾部。jdk1.7 之前用的头插法,新来的放在数组内
                if ((e = p.next) == null) {

                    p.next = newNode(hash, key, value, null);
                    //如果大于等于7,TREEIFY_THRESHOLD默认为8,调用链表建树的函数
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果在循环链表的时候,找到key相同的节点,那么就跳出循环,就走不到链表的尾上了。
                // e已经在上一步已经赋值了,且不为null,也会跳出for循环,会在下面更新value的值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //这个就是p.next也就是e不为空,然后,还没有key相同的情况出现,那就继续循环链表,
                // p指向p.next也就是e,继续循环,继续,e=p.next
                p = e;
                //直到p.next为空,添加新的节点;或者出现key相等,更新旧值的情况才跳出循环。
            }
        }
        //经过上面if else if else之后,e在新建节点的时候,为null;更新的时候,则被赋值。在树里面处理putTreeVal()同样如此,
        //if (e != null) { // existing mapping for key//只有更新的时候,才走这,才会直接return oldValue
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //putd调用此方法时onlyIfAbsent为false,执行。
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            //返回旧的Value,如果没有就返回null
            return oldValue;
        }
    }
    ++modCount;
    //如果size大于DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY,就重写分配空间
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize操作源码解读

当容量超过负载因子时,就会触发resize扩容操作。扩容操作的源码如下:

final Node[] resize() {
        Node[] oldTab = table;
        //如果原有的数组不空,就把oldCap赋值为旧数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //原来的扩容阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果旧数组长度大于0,说明已经有元素
        if (oldCap > 0) {
        //如果原数组的长度已经大于允许的最大容量
            if (oldCap >= MAXIMUM_CAPACITY) {
            //更新一下最大阈值,此时已经饱和,无法扩容了,返回旧的数组
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //否则旧扩容为原来的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //原有阈值也扩大为两倍
                newThr = oldThr << 1; // double threshold
        }
        //如果初始化的时候(见HashMap的构造函数)带了容量参数,那么newCap就是你的initialCapacity参数,threshold就是 (int)(initialCapacity*loadFactor)
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;

        //否则就按默认的算 initialCapacity = 16,threshold = 12 如果已经有元素了,那么直接扩容2倍,如果
        else {               // zero initial threshold signifies using defaults

            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            //如果新容量小于最大容量且扩容阈值不为空,那么阈值就为newCap * loadFactor,反之为最大阈值就是IntegerD最大值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        //如果原有的数组不为空
        if (oldTab != null) {
        //将原来map中非null的元素rehash之后再放到newTab里面去
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 如果这个oldTab[j]就一个元素,那么就直接放到newTab里面
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果原来的节点已经转化为红黑树节点了
                    else if (e instanceof TreeNode)
                        //那么我们去将树上的节点rehash之后根据hash值放到新地方
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        //这里的do While循环用于遍历该桶
                        do {
                            next = e.next;
                            //如果(e.hash & oldCap)为0,表明(e.hash & (newCap - 1))还会和 e.hash & (oldCap - 1)一样。因为oldCap和newCap是2的次幂, 并且newCap是oldCap的两倍,就相当于oldCap的唯一一个二进制的1向高位移动了一位
                            if ((e.hash & oldCap) == 0) {
                            //代表原位置没有发生变化
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //1.8中 旧链表迁移新链表    链表元素相对位置没有变化; 实际是对对象的内存地址进行操作 
                        //在1.7中  旧链表迁移新链表        如果在新表的数组索引位置相同,则链表元素会倒置
                        //拆分链表,把扩容前的原位置的头节点放在桶里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            //当前的位置+原来的长度
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

大致流程图:

image-20200415122049051.png

最后我们再来总结一下之前提到的3个问题,

什么时候进行resize操作?

  • 有两种情况会进行resize:

    1. 初始化table;
    2. 在size超过threshold之后进行扩容
  • 扩容后的新数组容量为多大比较合适?

    1. 扩容后的数组应该为原数组的两倍,并且这里的数组大小必须是2的幂
  • 节点在转移的过程中是一个个节点复制还是一串一串的转移?

    1. 从源码中我们可以看出,扩容时是先找到拆分后处于同一个桶的节点,将这些节点连接好,然后把头节点存入桶中即可

Hash碰撞

HashMap通常会用一个指针数组(假设为table[])来做分散所有的key,当一个key被加入时,会通过Hash算法通过key算出这个数组的下标i,然后就把这个插到table[i]中,如果有两个不同的key被算在了同一个i,那么就叫冲突,又叫碰撞。Java采用的是链地址法,即在原数组存一个链表的头节点,所有相同索引的节点都放在这个链表上(1.8之后引入了红黑树)

除了链地址法外,解决Hash碰撞的方法还有:

1. 开放地址法

开放地址法引入一个增量di,执行一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)。

其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。
如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2),称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。

2. 再Hash

当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止

3. 建立公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

线程安全问题

除以上几点外,还需要注意到HashMap并不是线程安全的,1.7之前,高并发下的put操作引发resize时,容易形成循环链表导致get操作陷入死循环,程序就有可能占据100%的CPU,

而在1.8之后,由于使用了不同的扩容策略,循环链表的情况已经不存在了,但是在高并发下以及某些特殊的单线程情况下依然可能抛出ava.util.ConcurrentModificationException并发修改异常。

针对线程安全的详细分析和解决方法的原理我们留待下一篇博文,这里简单说一下线程安全的解决方法。

对于如何解决线程安全问题,有这么几种方案

1. 使用Collections.synchornizedMap

但它存在以下问题

  • 会同步整个对象
  • 每一次的读写操作都需要加锁
  • 对整个对象加锁会极大降低性能
  • 这相当于只允许同一时间内至多一个线程操作整个Map,而其他线程必须等待
  • 它有可能造成资源冲突(某些线程等待较长时间)
  • SynchronizedHashMap会返回Iterator,当遍历时进行修改会抛出异常
2. 使用HashTable

HashTable所有的方法都加了锁,所以可以保证安全。但是也正因它所有方法都加了锁,所以效率并不高。Hashtable是Java 1.1提供的旧有类,从性能上和使用上都不如其他的替代类,因此已经不推荐使用

3.使用ConcurrentHashMap

ConcurrentHashMap对读读操作没有加锁(也不必要),写操作则使用CAS操作保证原子性。

  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复