视频课程
小黑屋思过中,禁止观看!
评论并刷新后可见

您需要在视频最下面评论并刷新后,方可查看完整视频

视频课程
立即观看
付费视频

您支付费用,方可查看完整视频

¥{{user.role.value}}
课程视频
开始学习
会员专享

视频合集

HashMap的实现原理,源码深度剖析!

  • 课程笔记
  • 问答交流

一线资深java工程师招聘需求里明确了需要精通集合容器,尤其是今天我谈到的HashMap以及后续我要讲到的ConcurrentHashMap

HashMap在Java集合的重要性不亚于Volatile在并发编程的重要性(可见性与有序性),所以需要重点来掌握。

为了助大家掌握好HashMap,这节课我会重点讲解以下10点:

1.HashMap的数据结构

2.HashMap核心成员

3.HashMapd的Node数组

4.HashMap的数据存储

5.HashMap的哈希函数

6.哈希冲突:链式哈希表

7.HashMap的get方法:哈希函数

8.HashMap的put方法

9.为什么槽位数必须使用2^n?

10.HashMap必考点总结

HashMap的数据结构

首先我们从数据结构的角度来看:HashMap是:数组+链表+红黑树(JDK1.8增加了红黑树部分)的数据结构,如下所示:

HashMap的实现原理,源码深度剖析!-mikechen

这里需要搞明白两个问题:

  • 数据底层具体存储的是什么?
  • 这样的存储方式有什么优点呢?

1.核心成员

默认初始容量(数组默认大小):16,2的整数次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
装载因子用来衡量HashMap满的程度,表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容
 
链表转红黑树边界
static final int TREEIFY_THRESHOLD = 8;

红黑树转离链表边界
static final int UNTREEIFY_THRESHOLD = 6;

哈希桶数组
transient Node<K,V>[] table;

实际存储的元素个数
transient int size;

当map里面的数据大于这个threshold就会进行扩容
int threshold   阈值 = table.length * loadFactor

 

2.Node数组

从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;//用来定位数组索引位置
    final K key;
    V value;
    Node<K,V> next;//链表的下一个Node节点

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }


    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }


    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }


    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }


    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。

HashMap的数据存储

1.哈希表来存储

HashMap采用哈希表来存储数据。

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构,只要输入待查找的值即key,即可查找到其对应的值。

哈希表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

2.哈希函数

哈希表中元素是由哈希函数确定的,将数据元素的关键字Key作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址。
表示为:Addr = H(key),如下图所示:
HashMap的实现原理,源码深度剖析!-mikechen

哈希表中哈希函数的设计是相当重要的,这也是建哈希表过程中的关键问题之一。

3.核心问题

建立一个哈希表之前需要解决两个主要问题:

1)构造一个合适的哈希函数,均匀性 H(key)的值均匀分布在哈希表中

2)冲突的处理

冲突:在哈希表中,不同的关键字值对应到同一个存储位置的现象。

4.哈希冲突:链式哈希表

哈希表为解决冲突,可以采用地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。

链地址法,简单来说,就是数组加链表的结合,如下图所示:

HashMap的实现原理,源码深度剖析!-mikechen
HashMap的实现原理,源码深度剖析!-mikechen

HashMap的哈希函数

/**
* 重新计算哈希值
*/
static final int hash(Object key) {
    
    int h;

     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16) 为第二步 高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

//计算数组槽位

(n - 1) & hash

对key进行了hashCode运算,得到一个32位的int值h,然后用h 异或 h>>>16位。在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16)。

HashMap的实现原理,源码深度剖析!-mikechen

这样做的好处是,可以将hashcode高位和低位的值进行混合做异或运算,而且混合后,低位的信息中加入了高位的信息,这样高位的信息被变相的保留了下来。

等于说计算下标时把hash的高16位也参与进来了,掺杂的元素多了,那么生成的hash值的随机性会增大,减少了hash碰撞。

备注:

  • ^异或:不同为1,相同为0
  • >>> :无符号右移:右边补0
  • &运算:两位同时为“1”,结果才为“1,否则为0

h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方。

为什么槽位数必须使用2^n?

1.为了让哈希后的结果更加均匀

HashMap的实现原理,源码深度剖析!-mikechen

假如槽位数不是16,而是17,则槽位计算公式变成:(17 – 1) & hash
HashMap的实现原理,源码深度剖析!-mikechen
从上文可以看出,计算结果将会大大趋同,hashcode参加&运算后被更多位的0屏蔽,计算结果只剩下两种0和16,这对于hashmap来说是一种灾难。2.等价于length取模

当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

位运算的运算效率高于算术运算,原因是算术运算还是会被转化为位运算。

最终目的还是为了让哈希后的结果更均匀的分部,减少哈希碰撞,提升hashmap的运行效率。

https://www.javacodegeeks.com/2015/09/an-introduction-to-optimising-a-hashing-strategy.html

分析HashMap的put方法:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 当前对象的数组是null 或者数组长度时0时,则需要初始化数组
    if ((tab = table) == null || (n = tab.length) == 0) {
        n = (tab = resize()).length;
    }
    
    // 使用hash与数组长度减一的值进行异或得到分散的数组下标,预示着按照计算现在的
    // key会存放到这个位置上,如果这个位置上没有值,那么直接新建k-v节点存放
    // 其中长度n是一个2的幂次数
    if ((p = tab[i = (n - 1) & hash]) == null) {
        tab[i] = newNode(hash, key, value, null);
    }
    
    // 如果走到else这一步,说明key索引到的数组位置上已经存在内容,即出现了碰撞
    // 这个时候需要更为复杂处理碰撞的方式来处理,如链表和树
    else {
        Node<K,V> e; K k;
       
        //节点key存在,直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))) {
            e = p;
        }
        // 判断该链为红黑树
        else if (p instanceof TreeNode) {
            // 其中this表示当前HashMap, tab为map中的数组
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        }
        else {  // 判断该链为链表
            for (int binCount = 0; ; ++binCount) {
                // 如果当前碰撞到的节点没有后续节点,则直接新建节点并追加
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD = 8
                    // 从0开始的,如果到了7则说明满8了,这个时候就需要转
                    // 重新确定是否是扩容还是转用红黑树了
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到了碰撞节点中,key完全相等的节点,则用新节点替换老节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 此时的e是保存的被碰撞的那个节点,即老节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent是方法的调用参数,表示是否替换已存在的值,
            // 在默认的put方法中这个值是false,所以这里会用新值替换旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // Callbacks to allow LinkedHashMap post-actions
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // map变更性操作计数器
    // 比如map结构化的变更像内容增减或者rehash,这将直接导致外部map的并发
    // 迭代引起fail-fast问题,该值就是比较的基础
    ++modCount;
   
     // size即map中包括k-v数量的多少
   // 超过最大容量 就扩容
    if (++size > threshold)
        resize();
    // Callbacks to allow LinkedHashMap post-actions
    afterNodeInsertion(evict);
    return null;
}

HashMap的put方法执行过程整体如下:

①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;

②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加

③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value

④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对

⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;

⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。

HashMap必考点总结

 

评论交流
  1. 路正银

    1、HashMap是用数据+链表+红黑树(JDK1.8版本之后增加)的数据结构来实现的,
    通过哈希函数确定在桶(数组)中的位置,当发生哈希冲突的时候,往后挂链表(JDK1.8版本会有链表转红黑树的逻辑)
    2、(1)底层数据结构不一样,1.7是数组+链表,1.8是数组+链表+红黑树
    (2)计算哈希值时,jdk1.8版本相比jdk1.7版本多了对hasCode做无符号右移16位,与原hasCode做异或的操作
    (3)扩容策略不一样
    3、哈希函数的目的是尽量让计算出的哈希值分布均匀,减少哈希碰撞
    JDK1.8版本的优化是,将hascode的高16位做移位操作,可以让hascode高位的值也参与运算,掺杂的元素多了,生成的hash的值的随机性会增大,减少了hash碰撞

    • mikechen

      核心点都谈到了 ,基本都掌握了,再补充一个点:就是HashMap 1.7版本在多线程的情况下会出现死循环,形成一个链表的死循环这个点,还可以线下有时间再做了解和补充,基本就没问题了。

      基本学习快一个月了,依然还在坚持输出作业,这个必须给赞 ,线下就坚持锻炼(keep见)+坚持作业输出,我就搬个小板凳在旁边给你呐喊加油了 ,继续加油 ✗咧嘴笑✗ ✗拳头✗