HashMap源码解读（中篇）

文章目录

前言
一、进入JDK中的源码（InteliJ IDEA为例）
二、HashMap的结构
三、源码解读
未完待续

前言

上一篇博主写了一些关于HashMap的前置知识，简单易懂：

HashMap源码解读（上篇）

下面将深入HashMap源码，进行解读。

看源码不是盲目看书，要有的放矢，带着疑问去看。

本文章将围绕这几个疑问展开：

HashMap的哈希函数是如何设计的？
put方法的逻辑是什么？到底是如何存储元素的？
当发生冲突时，是如何解决的？
哈希表冲突比较严重时，如何扩容resize？

一、进入JDK中的源码（InteliJ IDEA为例）

有两种快捷方式：

双击shift，输入HashMap类名即可。
直接在使用的类上，ctrl+鼠标左键点进去即可

二、HashMap的结构

JDK8之后HashMap的结构图如下：（可先看下面再回来看这个结构图）
在这里插入图片描述

JDK8之前的HashMap就是数组+链表，JDK8之后采用数组+链表+红黑树

冲突严重的链表会被“树化”，将链表转为红黑树，提高冲突严重的链表的查询效率。

三、源码解读

3.1 属性解读

如图所示：

在这里插入图片描述

图中有六条属性，下面逐一解释：

1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认初始化的数组大小 (默认的哈希桶数量) ： 16

注：哈希桶就是哈希表中一个个的数组元素，不包括链表元素

2.static final int MAXIMUM_CAPACITY = 1 << 30;
最大的数组容量： $2^{30}$

3.static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认负载因子，默认时开始保存的元素个数最多为 16 * loadFactor = 12 个

4.static final int TREEIFY_THRESHOLD = 8;
树化阈值。某个哈希桶中的链表长度超过8才会触发“树化”操作

5.static final int UNTREEIFY_THRESHOLD = 6;
“解树化” 当某个哈希桶中的红黑树结点个数过小，< = 6时，就会将红黑树还原为链表。

6.static final int MIN_TREEIFY_CAPACITY = 64;

树化有两个条件：

此时哈希表的哈希桶个数 >= 64
单个链表的结点个数 >= 8

若某个链表长度 >= 8 ,但此时哈希桶的数量不足64，则只是简单的哈希表扩容而已。

3.2 put方法解读

如图所示：
在这里插入图片描述
内部存储调用的是putVal方法，方法里面参数主要是hash值和key，value值。

3.2.1 HashMap中的hash方法

源码如下：
在这里插入图片描述

1.首先判断传入的Key值是否为null？如果为null，直接放入数组索引为0的哈希桶中。

2.如果传入的Key值不为null，则将key的hashCode 无符号右移16位，保留高16位然后和 原hashCode作 异或运算，求得数组索引。

注意：Key对象所在类的hashCode方法若没有覆写，则默认调用Object提供的hashCode方法。

在这里插入图片描述

高低16位都参与哈希函数的运算，尽可能保证不同key映射到比较均衡的状态。
原32位的hashCode和只保留高16的数字做异或运算
高低位树都参与hash运算得到的值更加平均
哈希函数设计理念：经过hash运算得到的值尽可能地平均

此时求出地hash值还不是当前数组的索引，只是经过hash运算得到的一个比较均衡的值,hash值还要经过如下红框的位运算，得到数组索引值：

在这里插入图片描述

上一步得到的key的hash值和当前哈希表的长度-1 进行 & 运算就可以得到索引值。（位运算的效率是最高的）

相当于hash % 数组长度取模(n)
前提是n必须为 2^n （初始化的哈希桶数量必须为2 ^ n）。
将任意的正整数转为哈希桶数量之内的小整数 => i 就是当前key求的哈希桶的编号

3.2.2 HashMap中的putVal方法

JDK中源码如下

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42