【源码学习】 深入剖析核心源码之 HashMap
HashMap作为面试常考的集合框架除了知道基本知识外也应该去学着剖析源码，只有清楚的学习了底层实现才能在面试中清楚的讲解出来，今天就来看看我的学习总结。
源码学习之 HashMap
- 一、HushMap 入门须知
- 二、那些重要的成员属性
- 1.初始容量
- 负载因子
- 数组长度
- 扩容阈值
- 5.树和链表进行转换
- 三、那些重要的成员方法
- 1.HashMap()
- 2.hash(Object key)
- 3.put(K key, V value)
- resize()
- get(Object key)
- 6.remove(Object key)
一、HushMap 入门须知
哈希表基础知识总结
首先来看看源码前的注释：
- 允许
null作为键和值 - 线程不安全
- HashMap的一个实例有两个影响其性能的参数： 初始容量和负载因子。 初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表得到满足的度量。
- 元素总数大于初始容量和负载因子的乘积就进行扩容，大小是原来的两倍
- 初始负载因子是0.75
- 使用
Collections.synchronizedMap方法来包装出一个线程安全的Map
二、那些重要的成员属性
1.初始容量
默认的初始容量DEFAULT_INITIAL_CAPACITY的值是：16 。 而初始容量的大小后标注了必须是2的次幂。
在源码中我们会经常发现位运算的身影，这是因为位运算的效率相对于其它运算效率较高，使用位运算可提高程序的效率。
最大初始容量MAXIMUM_CAPACITY的值是：1<<30
这里就有两个问题值得思考：
- 为什么初始容量必须是2的次幂呢？
- 如果我们传入一个初始容量还怎么保证它是一定是2 的次幂呢？
这两个问题随着后面的讲解我们慢慢解答。
2. 负载因子
就如同上面讲的，默认负载因子的值是0.75，不过我们也可以在构造方法中指定负载因子的大小。
3. 数组长度
整个hashMap中的元素的个数就用成员变量size来表示
4. 扩容阈值
扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）
5.树和链表进行转换
我们都知道HashMap的底层时通过数组+链表/红黑树 来构成的，那么对于每一个hash桶而言，什么情况下是链表什么情况下又是树呢？
重点就是取决于这三个属性的值：TREEIFY_THRESHOLD、UNTREEIFY_THRESHOLD、MIN_TREEIFY_CAPACITY
如果每一个下标处的链表中的元素过多也就是哈希冲突过多会导致链表中的元素过多，而在链表中找元素的时间复杂度是O(n)这样效率就会很低。于是就会有将链表转化成红黑树的操作，而转化的条件就是当整个Map的元素个数 > 64而且是某一个链表的节点数 > 8，转化成红黑树可以有效地将桶中搜索效率优化为O(logn)，也算是使用空间换时间的一种策略。当然当链表中的节点数目较少时，树型结构也会转化为链表结构，二者是可以相互之间转换的。TREEIFY_THRESHOLD：桶的树化阈值，桶中元素过多时会树化
UNTREEIFY_THRESHOLD：桶的链表还原阈值，当扩容后，对应得每个树中的节点数目就会减小，小于该值就转化为链表
MIN_TREEIFY_CAPACITY：最小树化容量阈值，当哈希表中的容量大于该值时，才允许树化链表，否则如果容量过多时进行扩容。
上面我们已经知道了，HashMap存储的元素有两种形式，分别是链表结构和树型结构，而这两种结构都以静态内部类的形式实现出来：
Node类就是以链表的形式保存的元素，其中覆写了hashCode、equals方法，jdk1.8以前为Entry结构，不过与Node只是名字不同。
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey() {return key; }public final V getValue() {return value; }public final String toString() {return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}}
TreeNode类是使用红黑树的原理实现的，这里就不过多叙述了。
三、那些重要的成员方法
1.HashMap()
关于HashMap的构造方法总共有四种，其中常见的就是前三种，是可以指定初始容量和负载因子。
HashMap(int initialCapacity, float loadFactor)
这就是第一种可以指定初始容量和负载因子的构造方法。
threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor。这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的。
这里的第五个标记中，调用了另一个方法tableSizeFor(int cup)，让我们来看看，这个方法实现的功能：
实际上，这个方法就是用来解决我们上面的第二个问题，如果是自己指定的初始容量，就要通过这个方法来使得初始化的容量变成离自己指定的容量最近的2的次幂值。例如输入6，那么在执行方法后，就会返回大于6且是2的次幂的最小值8。这样就保证了无论指定什么初始的容量，最终都会变成2的次幂。
HashMap(int initialCapacity)
这个方法是可以只是指定初始容量的构造函数，这样，负载因子就会使用默认的0.75
HashMap()
无参的构造方法会使用默认的初始化参数
2.hash(Object key)
该方法是重要的哈希函数，用于计算每一个元素对应的哈希值以便找到其对应的下标。而得到hash值的方法就是使用元素的hashCode的高16位与低16位的异或。那么为什么要这样设计呢？
这是因为hashMap中使用hash值找到对象下标是使用元素的hash值和Map的数组长度-1进行按位与，通常Map的长度不会特别特别大，这样如果直接使用hashCode来求得下标时，与数组长度-1进行按位与时，元素的下标大小就是由其hash值的低位来决定，这就导致如果插入的元素高位变化较大而低位几乎没变化时，将会使得这些元素求得的下标值相同，导致哈希冲突严重。而这种将高位与低位进行异或的方式可以使得高位也对最后的下标值有影响，使得高位信息也用另一种方式保存下来，也减少了哈希冲突。
这里我们已经知道了元素所存放的下标值是由元素的hash值和Map的数组长度-1进行按位与来得到的。这就可以解释我们前面的问题：为什么容量都要是2的幂次。 我们想想，容量是2的幂次，那么容量减1呢就是最高位为0，其余位为一。这样在按位与时就可以在不破坏整个元素的hash值的情况下，将hash折射到固定的长度的数组中进而找到下标。
这里可能有点懵，举个例子来演示下一个元素得到自己的下标值的过程：假设Map数组长度是16。
通过这样一个过程 ： hashCode ——> hash ——> index 来得到元素的下标为13。
3.put(K key, V value)
在hashMap中，存取数据也是一个重要的操作，那么它们的源码又是怎样实现的呢？
可以看到put(K key, V value)是对使用者封装的一个方法，而具体的函数实现是在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;}
接下来，逐步来看看每一部分的意义：
如果在插入时，没有发生哈希冲突：
发生冲突后：
插入执行结束后，对已经存在key的情况进行处理：
最后就是如果插入元素后，导致所有元素的数量大于负载因子和容量的乘积，执行扩容再散列的操作。
这里有个小小的改变：在jdk1.8之前对于链表形式插入时，使用的是头插的形式，也即每次来的值都作为数组中的节点。而到了jdk1.8版本时，就由头插变成了尾插。是为了防止扩容再散列后节点的指向发生混乱。
4. resize()
接下来，我们来看另一个重要的方法，扩容的方法。当Map中的已使用的容量>负载因子*总容量时，就进行扩容，每次扩容都是之前的2倍。
到这里也就完成了扩容工作。
5. get(Object key)
get方法用来获取一个键为Key的元素的val值。可以看出，内部实现也是调用的其它方法来实现的。
接着我们来看看getNode方法的实现。
6.remove(Object key)
同样是调用内部私有的方法，我们重点看底层的removeNode方法
要删除节点首先需要找到该节点：
找到节点后就分情况对其进行删除，删除后返回该节点。
到这里，基本的重要的知识点以及方法都介绍了，HashMap作为最常用也最容易考的集合类里面的很多方法都是设计的很精妙的，只有自己细细品一点点的深如了解才能体会到。自己学的还远远不够，以后会慢慢探索分享。希望自己的总结可以帮到你，文章有任何问题欢迎指正，也期待和更多小伙伴一起进步。
推荐自己的其它文章给大家读：
【源码学习】 深入剖析核心源码之 ArrayList
【源码学习】深入剖析核心源码之 LinkedList
缺乏、安全感
╰+哭是因爲堅強的太久メ
柔情只为你懂
怼烎@
骑猪看日落
还没有评论，来说两句吧...