Java源码模拟面试解析指南

服务端研究员
南京邮电大学本科,2019年校招中获得华为、中兴、顺丰等offer,先后就职于百度、携程、华为。热衷技术分享,阿里云栖社区认证专家,腾讯云+社区2019年度最佳作者,对Java源码颇有研究。
立即订阅 321学习

第3章 第3节 讨论一种特殊的 K.V 存储方式 HashMap(上)

去手机阅读

只有面对真正的自我,才能获得真正的自由
--《谁的青春不迷茫》

短短的假期又到了尾声,不过小a 这几天因为放假没课,每天在自习室死磕 HashMap 源码,不得不说,这真的是个烫手山芋,源码真的太复杂了,而且细节极多,面试也特别爱深究,不知道小a这次模拟面试命运之轮将向什么方向转动...

好了好了,他们来了,让我们作为第三者继续观察。。。

Q:HashMap 介绍下?

有了类注释,没人比我更懂怎么介绍一个组件了...

基于哈希表的Map接口的实现。此实现提供所有可选的 map 操作,并允许 null 值和 null 键(HashMap类与Hashtable大致等同,不同在于它是非同步的,并且允许为null).此类不保证 map 的顺序。特别是,它不能保证顺序会随着时间的推移保持恒定。

假设 hash 函数将元素正确分散在桶中,则此实现为基本操作(get和put)提供常数时间的性能。集合视图上的迭代所需的时间与HashMap实例的"capacity"(桶数)及其

  • size
    该 map 中包含的键-值对的数量,HashMap 的实际大小,可能不准(因为当你拿到这个值的时候,可能又发生了变化)

成正比。因此,如果迭代性能很重要,则不要将初始容量设置得过高(或负载因子过低),这一点非常重要。

HashMap的实例具有两个影响其性能的参数:初始容量和负载因子。

  • 容量 capacity 是哈希表中桶的数量,初始容量只是创建哈希表时的容量,其实整个阶段,容量都会保持为 2 的幂.

  • 负载因子 load factor 是在其哈希表容量自动增加之前允许哈希表能填多满的度量。当哈希表中的节点数超过负载因子和当前容量的乘积时,哈希表将被rehash(即,内部数据结构将被重建),之后哈希表的桶数大约为之前两倍。

通常,默认负载因子(.75)

  • 在构造函数中未指定时使用的默认负载因子

在时间和空间成本之间提供了一个很好的权衡。较高的值会减少空间开销,但会增加查找成本(在HashMap类的大多数操作中都得到体现,包括get和put)。设置其初始容量时,应考虑 map 中的预期节点数及其负载因子,以最大程度地减少 rehash操作的次数。如果初始容量大于最大节点数量除以负载因子,则不会发生rehash操作。

如果将许多映射都存储在HashMap实例中,则创建具有足够大容量的映射,这将比让其根据需要自动执行rehash而增大表结构,更高效地存储映射。
请注意,使用多个具有相同 hashCode 的键肯定是降低哈希表性能的操作。因此为了优化,当键是 Comparable 时,此类可以使用键之间的比较顺序来帮助打破这种局面。

和 ArrayList,LinkedList 一样,此类非同步.如果被多个线程同时访问,并且至少有一个线程在结构上修改该map,则必须在外部进行同步.通常通过在自然封装了map的某个对象上进行同步来实现.如果不存在这样的对象,则应使用Collections.synchronizedMap 方法“包装”map。当然这最好也是在创建时完成此操作,以防止意外地非同步地访问map:

Map m = Collections.synchronizedMap(new HashMap(...));

由此类的所有“集合视图方法”返回的迭代器都是快速失败的.

此类也是Java Collections Framework的成员。JDK1.2 时提供.

Q:你提到对 HashMap 的结构修改,具体指的是哪些操作呢?

结构修改是添加或删除一个或多个映射的操作;仅更改实例中已经包含的和 key 相关联的 value 值并不是结构修改.

  • 记录迭代过程中 HashMap 结构是否发生变化,如果有变化,迭代时会 fail-fast.对该HashMap进行结构修改的次数结构修改是指更改HashMap中的映射次数或以其他方式修改其内部结构(例如重哈希)的修改。此字段用于使HashMap的Collection-view上的迭代器快速失败

Q:说下 HashMap 底层的数据结构?

老面试题了,注意讲清结构之间差异

数组

  • 该 table 在首次使用时初始化,并根据需要调整大小。分配后,长度始终是2的幂。(在某些操作中,还允许长度为零,以允许使用当前不需要的引导机制。)

链表

红黑树

树节点。 继承 LinkedHashMap.Entry(这相当于扩展了Node的功能).

各结构之间的转换条件

链表 => 红黑树 : 桶节点上的链表长度大于等于8,且桶数组的大小 > 64

Q:为什么红黑树与链表的转化阈值为8呢?

使用树而不是 list 列出容器的容器计数阈值。将元素添加到至少具有这么多节点的bin中时,bin会转换为树。该值必须大于2,并且至少应为8才能与树删除中的假设(收缩时转换回普通的桶)相啮合。

泊松分布概率函数计算链表为各个长度的命中率:

可见,长度为 8 的链表命中率已太低!

  • 当数组容量大于 64 时,链表才会转化成红黑树.可将其分类为树化的最小table容量。 (否则,如果bin中的节点过多,将调整表的大小。)应至少为4 * TREEIFY_THRESHOLD,以避免resize扩容和树化的两个阈值之间的冲突。
  • 当红黑树节点数≤6时,红黑树转化成链表。在resize期间用于取消红黑树(拆分)bin的bin计数阈值。 应小于TREEIFY_THRESHOLD 并且最大为6以与删除节点时的容量收缩检测相协作

中间夹了个 7 不作处理,就是防止互转过于频繁!值得品味。

红黑树查询的时间复杂度为 O(log(n)),最坏的查询次数不过红黑树的最大深度。

Q:HashMap 如何确定元素放在哪个位置呢?

看来是想问我 hash 算法没错了,这些面试官怎么都喜欢问地这么拐弯抹角呢!

对于 HashMap 这种 map 结构,我们希望将元素都均匀分布在数组中,因此使用专门的 hash 算法。

hash

  • 先计算出 key 的 hashcode,再计算 h ^ (h >>> 16)

Q: 为什么要把 key 的哈希码右移 16 位呢?

因为h为 int 类型,正好 32 位,为了使计算出的 hash 值更加的分散,所以选择先将 h 无符号右移 16 位,然后再与 h 异或时,就能达到 h 的高 16 位和低 16 位都能参与计算,尽最大努力减少哈希冲突.

Q:你开始时提到数组容量必须是 2 的次幂,这是为什么呢?

啊嘞?我说过吗,这可给自己挖坑了呀,看来面试官对面试者所说的话都会即兴提问,大家面试注意说不清楚的东西一定不要说,祸从口出!

因为当容量是 2 的幂时,h& (length-1)运算才等价于对length取模,也就是h%length,而&比%具有更高的效率,也就是计算机会计算的更快!

而且这样能尽量均匀分布减少哈希冲突:
2的n次方实际就是1后面n个0,2的n次方-1 实际就是n个1.这样按位"与"时,每一位都能 &1,真正的参与到了运算.

Q:那问题又来了, HashMap 又是如何保证容量一直都是 2 的次幂呢?

小a有点慌了,好像没见过这个面试题呀,不过好歹我也是认真看过源码的,让我仔细想想好好作答.

  • 创建一个新的 HashMap 时的默认初始化容量 - 16 已经保证是 2 的次幂了

  • 如果创建时指定了容量值

注意到上图中的tableSizeFor方法

tableSizeFor

  • 对于给定的目标容量,返回两倍大小的幂。

下面开始逐行分析:

  • int n = cap - 1
    给定的 cap 减 1,为了避免参数 cap 本来就是2的幂次方,这样一来,经过后续操作,cap将会变成2 * cap,是不符合我们预期的!

  • n |= n >>> 1
    n >>> 1 : n无符号右移1位,即n二进制最高位的1右移一位
    n | (n >>> 1) 导致 n二进制的高2位值为1
    目前n的高1~2位均为1

  • n |= n >>> 2
    n继续无符号右移2位
    n | (n >>> 2) 导致n二进制表示的高3 ~ 4位经过运算值均为1
    至此,目前n的高1~4位均为1

  • n |= n >>> 4
    n继续无符号右移4位
    n | (n >>> 4) 导致n二进制表示的高 5 ~ 8 位经过运算值均为1
    目前n的高1~8位均为1

  • n |= n >>> 8
    n继续无符号右移8位
    n | (n >>> 8) 导致n二进制表示的高9 ~ 16位经过运算值均为1
    目前n的高1 ~ 16位均为1

  • n |= n >>> 16
    n继续无符号右移16位
    n | (n >>> 16) 导致n二进制表示的高17 ~ 32位经过运算值均为1
    目前n的高1 ~ 32位均为1

下面给出具体实例,加入入参cap 20,我们预期会返回 32.

int n = cap - 1; => n = 19(0001 0011)


n |= n >>> 1;
    n            => 0001 0011
    n >>> 1      => 0000 1001
    n |= n >>> 1 => 0001 1011

n |= n >>> 2;
    n            => 0001 1011
    n >>> 1      => 0000 1101
    n |= n >>> 1 => 0001 1111

至此,n 的所有位均为 1,后续的位操作均不再改变 n 的值了.

n + 1; => 0010 0000(32)

因此,tableSizeFor(20) 最终返回 32

可以看出,无论给定cap(cap < MAXIMUM_CAPACITY )的值是多少,经过以上运算,其值的二进制所有位都会是1.再将其加1,这时候这个值一定是2的幂次方.
当然如果经过运算值大于MAXIMUM_CAPACITY,直接选用MAXIMUM_CAPACITY.

Q:说的不错,那你知道 HashMap 是怎么添加元素的吗?

这个必问面试题,我肯定也仔细看了源码总结了,哼,没什么能问倒我的~

putVal

首先看到实现 Map 接口的 put 方法,里面就调用了 HashMap 自己实现的 putVal 方法.
图片说明

    /**
     * 实现 Map.put 和相关方法
     * 注意此类 final 修饰,不要再妄图继承 HashMap,重写 putVal.
     *
     * @param hash - hash(key)
     * @param key the key
     * @param value 要 put 的 value 值
     * @param onlyIfAbsent 如果为 true,  不会覆盖已有值,而默认传的是 false,即key 相同时,默认会覆盖原有的 value值
     * @param evict 如果为 false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // table 数组为空,创建之
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 等同于取模运算,得到要插入的数组索引
        if ((p = tab[i = (n - 1) & hash]) == null)
            // table[i] 为 null,直接插入新的节点
            tab[i] = newNode(hash, key, value, null);
        else {
            // table[i] 非空
            Node<K,V> e; K k;
            // 若 key 已存在,则直接覆盖value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 若 key 不存在,判断该是否为红黑树
            else if (p instanceof TreeNode)
                // 直接插入树节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 这是链表
            else {   
                // 开始遍历链表
                for (int binCount = 0; ; ++binCount) {
                    // 当后继节点为 null 时
                    if ((e = p.next) == null) {
                        // 创建新节点,赋值给 next
                        p.next = newNode(hash, key, value, null);
                        //  判断链表长度是否达到阈值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 达到阈值,则转化为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // key 已经存在,直接覆盖 value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改计数器加一
        ++modCount;
        // 超过阈值 => 扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

图解插入元素流程

qrcode
下载牛客APP随时随地学习