HashMap查漏补缺

简介: HashMap 是面试的钉子户了,网上分析的文章也有很多,相信大家对于原理已经烂俗于心了。但最近在看源码时,发现其中一些实现细节其实不太好理解,所以决定以问答的形式在这里记录一下,写的时候尽量把原因说明白,希望对大家有帮助容量和 size 分别指什么?容量并不是指 HashMap 所能存储的键值对数量,而是其内部的 table 数组的大小,而 size 是指目前已存储的键值对的数量。

HashMap 是面试的钉子户了,网上分析的文章也有很多,相信大家对于原理已经烂俗于心了。但最近在看源码时,发现其中一些实现细节其实不太好理解,所以决定以问答的形式在这里记录一下,写的时候尽量把原因说明白,希望对大家有帮助

容量和 size 分别指什么?

容量并不是指 HashMap 所能存储的键值对数量,而是其内部的 table 数组的大小,而 size 是指目前已存储的键值对的数量。table 是一个 Entry 数组。 table 的每一个节点都连着一个链表或者红黑树。

初始容量可以随意设置吗?

可以,但是 HashMap 内部会你设置的 initialCapacity 转换为大于等于它的最小的2的n次方。比如 20 转为 32,32 转为 32等。如果不设置,则为默认值16。需要注意的是,在 Java 8的源码中,并没有在构造方法直接新建数组。而是先将处理后的容量值赋给 threshold,在第一次存储键值对时再根据这个值创建数组。

为什么内部要将容量转换为 2 的n次方?

这样可以提高取余的效率。为了防止链表过长,要保证键值对在数组中尽可能均匀分布,所以在计算出 key 的 hash 值之后,需要对数组的容量进行取余,余数即为键值对在 table 中的 index。 对于计算机而言,二进制位运算的效率高于取余(%)操作。而如果容量是 2 的 n 次方的话,hash 值对其取余就等同于 hash 值和容量值减1进行按位与(&)操作:

// capacity 为 2 的 n 次方的话,下面两个操作结果相同
hash & (capacity -1)
等同于
hash % capacity

那为什么两种操作等同呢? 我们以2进制的思维想一下,如果一个数是 2 的 n 次方,那它的二进制就是从右往左 n 位都为0,n+1 位为1。比如2的3次方就是 1000。这个数的倍数也满足从右往左 n 位都为0,取余的时候抛弃倍数,就等同于将 n+1 位及其往左的所有位归0,剩下的 n 位就代表余数。换句话说,一个数对2的 n 次方取余,就是要取这个数二进制的最低 n 位。 2 的 n 次方减1的结果就是 n 位1,进行与操作后就得到了最低 n 位。

如何将一个值转换为大于等于它的最小的2的 n 次方?

我们先假设一个二进制数 cap,cap 的二进制有 a 位(不算前面高位的0),那么,大于它的最小的2的次方就是2的 a 次方。2 的 a 次方减一的结果就是 n 位1,那我们只要将 cap 的全部 2 进制位变为1,再加1就能得到结果。而为了防止 cap 本身就是2的 n 次方,我们在计算之前先将 cap 自减。

如何将二进制位都变成1呢?下面是源码:

static final int tableSizeFor(int cap) {
    int n = cap - 1; //这一步是为了避免 cap 刚好为2的 n 次方
    n |= n >>> 1; //保证前2位是1
    n |= n >>> 2; //保证前4位是1
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

下面的描述中 n 的位数都不包括前面补位的0。

|= 这个符号不常见,a |= b 就是 a = a|b 的意思。代码中先将 n 无符号右移1位,由于n 的第1位肯定是1,移位后第2位是1,| 操作后前2位就保证是1了。第二步右移了2位再进行|操作,保证了前4位是1,后面的计算类似,由于 n 最多有32位,所以一直操作到右移16为止。这样就将 n 的所有2进制位都变成了1,最后自增返回。

hash 值是如何计算的

hash 值并没有直接返回 hashcode 的返回值,而是进行了一些处理。 前面提到过,hash 值算出来后需要进行取余操作,影响取余结果的是 hash 值的低 n 位。如果低 n 位是固定的或者集中在几个值,那么取余的结果容易相同,导致 hash 碰撞的发生。由于 hashcode 函数可以被重写,重写者可能无意识地就写了一个坏的 hash 函数,导致上面这种情况发生。

为了避免这种情况,HashMap 将 hash 值先向右移位,再进行或操作,这样就使高位的值和低位的值融合成一个新的值,保证取余结果受每一个二进制位的影响。Java 7和 Java 8的原理都一样,但源码有细微出入,可能是 因为 Java 经过统计发现移位一次就够了吧。

//Java 7
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//Java 8
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

扩容后元素如何进行移动

为了防止元素增多后,链表越来越长,HashMap 会在元素个数达到阈值后进行扩容,新的容量为旧容量的2倍。 容量变化后,每个元素用 hash 值取余的结果也会随之变化,需要在数组中重新排列。以前同一条链表上的元素,扩容后可能存在不同的链表上。

在 Java 7 中,重新排列实现得简单粗暴,直接用 hash 根据新容量算出下标,然后设置到新数组中,即相当于将元素重新put 了一次。但在 Java 8中,作者发现没必要重新插入,因为重新计算后,新的下标只可能有两种情况,要么是原来的值,要么是原来的值加旧容量。比如容量为16的数组扩容到32,下标为1的元素重新计算后,下标只可能为1或17。

这个怎么理解呢?重提一下之前的一句话,一个数对2的 n 次方取余,就是要取这个数二进制的最低 n 位。当容量为16时,取余是取最后4位的值,而扩容到32后,取余变成取最后5位的值。这里增加的1位如果为0,那么余数就没变,如果为1,那么余数就增加了16。如何取增加的这一位的值呢?直接和16进行与操作即可。16的二进制是10000,与操作后如果结果为0,即表示高位为0,否则为1。

根据这个原理,我们只需要将原来的链表分成两条新链放到对应的位置即可,下面是具体步骤:

  1. 遍历旧数组,如果元素的 next 为空,直接取余后放到新数组;
  2. 如果元素后面连了一个链表,那么新建两条链表,暂且成为 hi 链和 lo 链;
  3. 遍历链表,计算每个元素的 hash 值和旧容量与操作的结果,结果为0则将其放入 lo 链末端,不为0放入 hi 链末端;
  4. 将两条链的 head 放到新数组中,其中 loHead 放到原来的位置,hiHead 放到原来的下标加上旧容量处;
  5. 如果是红黑树,进行和上面类似的操作,只是将两条链表换成两棵树。

理解原理后看代码就很简单了:

if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null) 
            newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof TreeNode) //红黑树类似
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
            //新建两条链表
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do {
                next = e.next;
                if ((e.hash & oldCap) == 0) { //结果为0,表示下标没变,放入 lo 链
                    if (loTail == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                }
                else { //结果为0,表示下标要加上旧容量,放入 hi 链
                    if (hiTail == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                }
            } while ((e = next) != null);
            if (loTail != null) { //lo 链放在原来的下标处
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) { //hi 链放在原来的下标 加旧容量处
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}

最后 需要这份HashMap源码解析进阶学习视频的可以加Android进阶群免费获取;701740775。请备注csdn

相关文章
|
5月前
|
存储 算法 安全
拜托,面试请不要再问我HashMap了
拜托,面试请不要再问我HashMap了
36 0
|
28天前
|
存储 Java Serverless
【面试问题】如何设计一个 HashMap?
【1月更文挑战第27天】【面试问题】如何设计一个 HashMap?
|
2月前
|
存储 安全 Java
【面试知识点】一文带你深入了解HashMap
【面试知识点】一文带你深入了解HashMap
|
2月前
|
存储 算法 安全
认真学习Java集合之HashMap的实现原理
认真学习Java集合之HashMap的实现原理
26 0
认真学习Java集合之HashMap的实现原理
|
2月前
TreeMap踩坑
TreeMap踩坑
14 0
|
7月前
|
存储 算法 Java
大厂面试HashMap,一定要注意这个点,很多人栽在了这儿
Hashmap是Java中最常用的集合类型,使用非常广泛。不过,有些细节问题很多人没有关注过,这也使很多人在面试时栽了跟头!比如,阿里很多团队为了考察候选人的基础,就出了这么一个面试题:为什么HashMap的初始长度和扩容长度是2的N次幂?
|
9月前
|
设计模式 存储 消息中间件
查漏补缺第五期(HashMap & ConcurrentHashMap)
前言 目前正在出一个查漏补缺专题系列教程, 篇幅会较多, 喜欢的话,给个关注❤️ ~ 本专题主要以Java语言为主, 好了, 废话不多说直接开整吧~ HashMap底层有了解过吗? 它的put原理以及扩容机制是什么 HashMap是一种常用的数据结构,用于存储键值对。在理解HashMap的put原理和扩容机制之前,我们先来了解一下HashMap的基本结构。 HashMap的内部是由一个数组和链表(或红黑树)组成的,数组被称为哈希表,用于存储元素。每个数组元素是一个链表的头节点(或红黑树的根节点),该链表(或红黑树)用于解决哈希冲突,即当不同的键映射到相同的数组索引时。
|
10月前
|
存储 程序员
什么啊?面试官还在问HashMap了,老知识点了啊
不就是一个hash加一个map嘛,多简单啊? 答:利用key的hashCode重新hash计算出当前对象的元素在数组中的下标,存储到数组里面就行了,底层就是数组嘛! 然后面试官说了句:好的,我知道了,回去听消息吧!
|
存储 缓存 安全
浅谈面试中HashMap相关问题
浅谈面试中HashMap相关问题
浅谈面试中HashMap相关问题
|
移动开发 Java 索引
【面试:基础篇08:HashMap全总结】
【面试:基础篇08:HashMap全总结】
146 0

相关产品