《数据解构》HashMap源码解读

👑作者主页：Java冰激凌
📖专栏链接：数据结构  

目录

了解HashMap

HashMap的构造

两个参数的构造方法

一个参数的构造方法  

不带参数的构造方法

哈希表初始化的长度

HashMap源码中的成员

Pt

Get

---

了解HashMap

 首先我们要明确 什么是HashMap？ 

        HashMap 是一个用于存储（Key - Value）键值对的集合 每一个键值对也称为Entry ，这些键值对被均匀的分布在了一个存储的table数组当中 

---

本文讨论的HashMap是基于JDK8 的源码~

面试题

        HashMap底层的数据结构是什么？

        是一个特殊的数组 

        Hash表示什么？

        散列表  一个用于存储（Key - Value）键值对的集合 每一个键值对也称为Entry ，这些键值对被均匀的分布在了一个存储的table数组当中

HashMap的构造

HashMap的构造也是有多种形式的

两个参数的构造方法

//public HashMap （int，float）public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}

这个构造方法 是传入两个参数 第一个参数为初始化哈希表的长度 第二个参数是手动指定负载因子

 我们着重来观察一下这个代码 我们进入方法 是非常有趣的

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}

这个代码是干啥的呢？ 写的花里胡哨的 可其实 这个可是非常有趣的 这个是我们传入的初始化的长度 这个方法会帮我们转换为2的最小次幂 我们来解读一下 举例我们传入cap为10

static final int tableSizeFor(int cap) {//cap = 10int n = cap - 1;// 9 00000000 00000000 00000000 00001001n |= n >>> 1;//n>>>1 00000000 00000000 00000000 00001100//n     00000000 00000000 00000000 00001001//|=    00000000 00000000 00000000 00001101//我们现在看还不是很明显  我们再做一个n |= n >>> 2;// n    00000000 00000000 00000000 00001101//n>>>2 00000000 00000000 00000000 00001111//n     00000000 00000000 00000000 00001111//发现了什么吗？我们可以观察到 其实每次做 都是在复制当前前几位1 //当这个操作都做完之后 我们可以得到我们会变成什么样子//也就是 当前的最前一位的1 后面都变为了1 如此操作我们便可以做到完成//找到2的最小次幂 那么为什么要使用位运算呢？这个问题我们就不讨论了 //计算时cup做位运算效率很高 并且哈希表是本身就是为了快n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

---

一个参数的构造方法  

//public HashMap（int）public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}

这个构造方法是传入一个参数 传入的参数为初始化哈希表的长度  我们也可以发现 在指定长度后 是调用了我们的带有两个参数的构造方法 其中的 initialCapacity 是我们指定的初始化的长度 DEFAULT_LOAD_FACTOR 是默认的负载因子 其中 在源码中 默认的负载因子的大小为0.75f（对的 float类型！）

不带参数的构造方法

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

 这是我们不带参数的构造方法 其中 会默认指定loadFactor（负载系数）为0.75以及其他字段 都为默认值 其中 值得注意到的是 HashMap的默认初始化数组的大小不是10  也不是 20 而是

16 那么为什么会是16呢？

---

哈希表初始化的长度

这是我们刚刚没有提及到的 我们在手动设定哈希表长度的时候 真的会是以我们手动设置的长度来构造哈希表的长度的吗？

        HashMap表的默认初始化长度为16 并且每次拓展 或者手动指定初始化长度的时候 长度         必须是2次幂 

默认初始化长度为何会是16呢？并且为何又要是2次幂呢？

        之所以我们选择16来作为默认的初始化长度 是为了服务Key映射到index的Hash算法

        从Key映射到HashMap数组对应的位置  我们都需要借助到一个Hash函数 

        这个Hash函数就是用来计算能够尽量避免哈希碰撞的长度的

        并且初始化为16 更加符合Hash算法分布均匀的要求

那么我们如何可以实现一个分布比较均匀的Hash函数呢？

        此时 我们就需要利用到另一个函数 HashCode 这个HashCode是利用Key的

        HashCode来确定在哈希表中映射的位置

 那么 是不是把Key的HashCode值和HashMap的长度进行取余运算？

        漏漏漏 大漏特漏 虽然说取余的方式很简单快捷 但是效率是比较低的 显然 我们哈希表出

        现之初就是为了提高效率的 这个操作反而有点背道而行了，所以 HashMap采用了位运

        算的方式

 面试题

        通过new HashMap（10）创建对象 此时HashMap底层的数组长度是多少？

        16   不管你传进去什么数字，返回的一定是大于等于该数字的最小2的幂次,

那么为什么是2次幂？ 我们需要对于这个进行长篇大论了 等我们讲完put之后会讲解的

---

HashMap源码中的成员

我们去源码中寻找HashMap的特殊的 数组 我们发现 在整个HashMap中只有一个数组 就是table

但是我们同时也发现了 在我们的构造方法以及创建的时候 并没有去初始化数组的大小 

 面试题 

        为何没有在初始化或者构造方法中对数组进行初始化

        等到我们看到put中会发现 是在put方法中进行的初始化 那么为何要在put中才进行初始化呢 其实这是一个叫做懒加载的机制 是从技术底层帮我们避免了一些资源浪费 假设我们有以下的代码 如果对于map不进行使用 假设我们没有加入懒加载这个机制 就会造成资源的浪费 其中相同的技术也在List中也使用到了 （懒加载在Spring中也会经常的使用到 一定要了解到这个概念）

---

Put

put是HashMap中的插入方法 将指定值与此映射中的指定键关联 如果映射之前包含键的映射 则替换旧值（如果存在相同的值 会被覆盖）

    public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

我们可以看到 put是有返回值的 这个返回值为V类型  然后我们进入putVal中查看

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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

代码相当的长 我们将代码分割几个部分来进行分析

 这个判断的意思就是为了查看 如果数组为null 或者数组中有效元素个数为0 那么我们进入resize方法

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;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 orderNode<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) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

又是超级长的代码 不过没瓜系 我们还是分开来解读

 首先 进入方法 oldTab = table = null（因为我们的table当前为空）

所以 oldCap = 0 然后我们进入判断 判断中  oldCap为0 我们将newCap与newThr都赋值为默认值

之后我们对于table进行了初始化 

可以啦

 

 以上这个代码 都不用看 因为我们现在在进行初始化 为何不需要看这些代码呢 因为这些代码都是在考虑扩容的代码 我们此时不会涉及到扩容 所以这些代码暂时不用理会 （ps：看了一天的源码 我总结出一个道理 看源码不能一行一行去读 而要去寻找重点 如果一行一行代码去读 ）

好的我们又回到了put方法中 我们看当前红框中的代码 这是一个如果当前位置为空 我们便将key以及value插入 但是我们的注意力 要放到hash方法中 

 也就是当初put传入的这个hash值 这个值是如何计算出来的呢？

---

 面试题

        HashMap中的Key能不能为null？如果为null 则下标为多少？

        我们以上的源码可以解释这个问题 是可以为null的 且只能有一个为nill的Key 下标为0

        如果Key == null 那么直接返回hash = 0

---

我们还是将注意力 放到这里

假设不为空的话 它的下标是如何计算的？

 首先要通过我们的HashCode来计算一个哈希值 然后我们还要异或h>>>16位

---

面试题

        HashMap中秋hash值的时候用到了扰动函数 为什么要这么做呢？

        先说结论 为了减少Hash冲突发生的可能性

        我们来具体举例一下

        return (h = gril.hashCode() ^ (h >>> 16)
//假设girl的hash值是
//00101101 00101101 10100111 00101101
那么我们假设HashMap的长度为16 也就是下标为0-15
计算这个的hashMap值也很简单 我们计算下标
//00101101 00101101 10100111 00101101
//00000000 00000000 00000000 00001111
其实也就是取出最后四位嘛 直接后四位进行计算就好啦
//00000000 00000000 00000000 00000010
我们再假设 woman的hash值是这样的
//00111111 11101101 11100111 10111101
计算下标的话
//00000000 00000000 00000000 00001111
//00000000 00000000 00000000 00000010
我们可以发现  最后计算出的下标是相同的 这就是为何要加入扰动函数 扰动函数是干啥的呢？也就是说 全球60亿人 有很多人的眼睛可能是一样的 但是如果加上这些人的其他特征 那么就变得不一样了 因为世界人相同的人只有一个

---

下面我们便到了 插入重复元素

 这个代码也是比较复杂的 直接一句话 如果当前下标没有元素 直接插入 如果有元素 我们进行尾插（在JDK1.7之前 是头插）

那么我们如何插入 是怎么放的  此处我们不得不提到一个哈希冲突

---

面试题

        Hash冲突发生之后怎么解决？

        线性探测法：for循环找一下旁边有没有空位 

        链式地址法：实际上就是在同一个节点下面加 

链地址法怎么理解 假设你在坐火车 你拿着的票的位置已经坐了一个小姐姐 你该怎么办  总不能直接坐到人家小姐姐身上把（滑稽）此时我们可以加入一个上下铺的方式往后依次走

---

我们来看一下这个 这个红框中的是 计算负载因子 如果超过负载因子 进行扩容 并且 当一定的要求满足的时候 会转变为链表加红黑树

---

面试题

        HashMap链表转红黑树的条件

        链表的深度必须大于等于8

        数组的长度必须大于等于64

---

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;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 orderNode<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) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

扩容的细节还是在于 扩容会进行扩容为2的次幂  

---

面试题

        HashMap为什么线程不安全？

        JDK1.7之前 

        ·put的时候会造成数据丢失

        ·扩容的时候 头插法会造成死循环

        JDK1.8

        ·put的时候会造成数据丢失

        ·扩容的时候 头插改成了尾插 不会出现循环

（这也可能是一部分为何要在JDK1.8之后将HashMap改为尾插法的原因之一）

Get

使用Get方法根据Key来查找Value的时候，发生了什么呢？ 

首先会把输入的Key做一次Hash映射，得到对应的index 之后会去当前index下标去寻找节点是否存在 如果存在即返回V即可 get的原理是比较简单的 没有put如此的繁琐

用了10+小时来分析源码 已经吐了~知识点很多 融入文章才能看懂 有不足之处也希望多多指出 😢