HashMap源码解读（中篇）

文章目录

前言
一、进入JDK中的源码（InteliJ IDEA为例）
二、HashMap的结构
三、源码解读
- 3.1 属性解读
- 3.2 put方法解读
- - 3.2.1 HashMap中的hash方法
  - 3.2.2 HashMap中的putVal方法
未完待续

前言

上一篇博主写了一些关于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中源码如下

代码语言：javascript复制

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.首先判断当前哈希表是否为空，若为空，进行默认初始化操作（resize()函数里面包括了扩容、数据搬移和初始化操作）