HashMap实现原理、源码解析（jdk1.8）
- 下面参考博文，感谢！
-
Java 8系列之重新认识HashMap
- 全方面（主要是jdk1.8的源码分析）
-
HashMap源码分析（jdk1.8，保证你能看懂）
- 全方面（主要讲解put过程、扩容过程等）
-
用漫画告诉你—什么是HashMap？
- 主要讲解 HashMap 的数据结构、哈希桶数组索引、hash算法以及各常量设计的巧妙之处等
- 一幅漫画告诉你，什么是红黑树
- 正文
基本概念
- HashMap 是最常用的集合类框架之一，它实现了 Map 接口，所以存储的元素也是键值对映射的结构，并允许使用 null值 和 null键，其内元素是无序的，如果要保证有序，可以使用 LinkedHashMap（插入顺序）。
- HashMap是线程不安全的，所以才有了 ConcurrentHashMap。也可以通过
Collections.synchronizedMap()这个方法来使 HashMap 变为线程安全的。 - HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
- 它是根据键的
hashCode值来存储数据的，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 - 继承关系如下:
- HashMap是线程不安全的，所以才有了 ConcurrentHashMap。也可以通过
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {···}
数据结构
- HashMap 的数据结构是 数组 + 链表 + 红黑树（jdk1.8增加了红黑树部分）
-
数组
- 连续的内存，通过下标可以快速进行寻址。
- 插入结点困难
- 当在数组中插入一个元素时，后面的元素都得往后移动，然后才能进行操作，比较麻烦。
-
单链表
- 插入、删除数据方便（直接修改节点指针）
- 查询效率低（遍历结点、时间复杂度O(n)）
-
红黑树
- 一种自平衡的二叉查找树，除了符合二叉查找树的基本特性外，还具有以下特性：
- 二叉查找树，左子树元素大于右子树，最大的查找次数为树高。
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 红黑树的这些规则，保证了红黑树的自平衡。
- 但是，当插入、删除节点时，这些规则可能会被打破，导致红黑树不再是一个红黑树了。这时就需要做出一些调整，调整方法有：变色、旋转（左旋、右旋）。
- 变色就是将红色变为黑色，黑色变为红色，为了满足上面的条件
- 注意：变色会发生连锁反应，所以要经过多次变色。
- 左旋转
- 逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
- 右旋转
- 顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
- 变色就是将红色变为黑色，黑色变为红色，为了满足上面的条件
- 一种自平衡的二叉查找树，除了符合二叉查找树的基本特性外，还具有以下特性：
源码分析
- 下文的源码是基于
jdk1.8版本来进行分析的- 之前
jdk1.7的存储结构是数组+链表 ( 拉链式 )，到了jdk1.8变成了数组+链表+红黑树。- 不是说变成了红黑树效率就一定提高了，只有在链表的长度不小于8，而且数组的长度不小于64的时候才会将链表转化为红黑树。
-
jdk1.7版本增删效率高，jdk1.8版本增删、查找效率都高。 -
jdk1.8版本的优化在扩容机制的数组元素转移的地方有很巧妙设计的体现。
- 另外，HashMap 是非线程安全的，也就是说在多个线程同时对 HashMap 中的某个元素进行增删改操作的时候，是不能保证数据的一致性的。
- 之前
数据结构表示
- 最终的数据结构整体是数组，然后每个数组元素是一个链表的节点。当发生冲突时，在节点处使用尾插法插入节点。当链表长度大于8之后（在数组长度大于64的前提下），链表就会转换为红黑树了。
- 链表节点的表示：
- 存储了 hash 码，Key、Value、链表的指针域（指向下一个节点）。
//HashMap的静态内部类 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) {···}
public final K getKey() {···}
public final V getValue() {···}
public final String toString() {···}
public final int hashCode() {···}
public final V setValue(V newValue) {···}
public final boolean equals(Object o) {···}
}
- 红黑树的表示：
- 存储了 双亲结点、左子树、右子树、前一个元素的节点、是否为红色（布尔值）。
- 另外由于它继承自 LinkedHashMap.Entry ，而 LinkedHashMap.Entry 继承自 HashMap.Node ，因此还有额外的 6 个属性。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
···
}
//继承 LinkedHashMap.Entry 的
Entry<K,V> before, after;
//HashMap.Node 的
final int hash;
final K key;
V value;
Node<K,V> next;
几个常量、变量
- 其中，阈值:
threshold=capacity*loadFactory。 - 注意这三个变量的区别：
threshold、size、length。 -
modCount记录的HashMap结构的改变是指 HashMap中的 映射数 或以 其他方式修改其 内部结构。- 注意：某个key对应的value值被覆盖不属于结构变化的。
//默认数组容量大小：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//数组最大容量大小：2 的 30 次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//使用树而不是链表的计数阈值，将元素添加到至少这么多的节点的链表中时，链表将转换为树
static final int TREEIFY_THRESHOLD = 8;
//可以进行树化的最小数组容量
static final int MIN_TREEIFY_CAPACITY = 64;
//存储键值对元素的数组，分配后，长度始终是 2 的幂（哈希桶数组）
transient Node<K,V>[] table;
//此映射中包含的键-值映射数，即当前数组中的元素数量
transient int size;
//主要用于记录HashMap内部结构发生变化的次数。
transient int modCount;
//哈希表所能容纳的最大键值对个数，下次扩容的临界值，size>=threshold 数组就会扩容
int threshold;
//负载因子
final float loadFactor;
构造方法
-
HashMap有四个构造方法，如下：
/**
* 使用默认的初始容量（16）和默认的加载因子（0.75）构造一个空的 HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造一个新的 HashMap ，其映射与指定的 Map 相同。
* HashMap 是使用默认负载因子（0.75）和足以将映射保存在指定的 Map 中的初始容量创建的
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 构造一个带指定初始容量和加载因子的空 HashMap。
*/
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);
}
这里简单的说一下构造方法中的两个东西
-
initialCapacity初始容量- 官方要求我们要输入一个2的N次幂的值，比如说2、4、8、16等等这些，但是我们忽然一个不小心，输入了一个20怎么办？没关系，虚拟机会根据你输入的值，找一个离20最近的2的N次幂的值，比如说16离他最近，就取16为初始容量。
-
loadFactor负载因子- 默认值是0.75。负载因子表示一个散列表的空间的使用程度，有这样一个公式：
initailCapacity*loadFactor = HashMap的容量。 - 所以负载因子越大则散列表的装填程度越高，也就是能容纳更多的元素，元素多了，链表大了，所以此时索引效率就会降低。反之，负载因子越小则链表中的数据量就越稀疏，此时会对空间造成烂费，但是此时索引效率高。
- 默认值是0.75。负载因子表示一个散列表的空间的使用程度，有这样一个公式：
确定哈希桶数组索引位置
- 主要是hash算法（均匀的）。
-
jdk1.8版本将这个过程的一部分融入到了put()过程中。 - 首先我们知道 HashMap 是根据 Key 的 hashCode来确定键值对在哈希桶数组的位置的。得到了hash值之后又该怎么做呢？首先想到的是取模，当然，肯定不是这样的，不然人人都能当大牛了_。其实是通过巧妙的位运算来操作的（更高效）。
- 下面就是 HashMap 中的
hash()方法的实现。
- 下面就是 HashMap 中的
//经过两步操作最后得到的才是我们用来确定位置的hash值
static final int hash(Object key) {
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//确定hash值之后的操作就是确定在哈希桶中的位置了
//下面是 put() 方法中的一行代码，n为哈希桶数组长度，hash为前一步确定的hash值
p = tab[i = (n - 1) & hash]
- 可以看到，哈希桶数组索引位置是由位运算来操作。下面是一个例子
- 图片来自美团技术团队在知乎上的文章：Java 8系列之重新认识HashMap
HashMap确定哈希桶数组索引位置的位移运算举例
- 仔细想一下，数组长度减一得到的值的二进制数，前面大部分都是0，所以，可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。
- 那么这样的过程是不是会出现不同的key得到同一个索引位置的情况呢？
- 当计算的hash值出现了重复，就出现了地址冲突了（严格来收叫做碰撞）
- 这时候就需要解决冲突了。详情请见后面小标题——解决冲突。
put 插入过程
- 具体的流程就如下图所示（在put过程中是解决了地址冲突的），get操作自己下去看，也是类似的。
- 下面的图片来自美团技术团队在知乎上的文章：Java 8系列之重新认识HashMap
HashMap的put过程图解
public V put(K key, V value) {
//这里调用了hash()方法，拿到了Key的hash值
return putVal(hash(key), key, value, false, true);
}
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;
//第二部分：拿到index对应的数组元素（节点），判断是否为空，为空则直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//第三部分：节点存在，发生哈希碰撞，解决哈希碰撞
else {
Node<K,V> e; K k;
//第三部分第一小节：Key存在，则直接覆盖Value
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);
//这个时候计数阈值大于了8则转换为红黑树进行操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//第三小节第二段：Key存在则直接覆盖
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;
}
resize 扩容机制
- 不断的向 HashMap 中添加元素，当哈希桶数组的元素数目超过阈值，就要扩容了。
- 扩容后的 HashMap 容量是之前容量的两倍。
- 扩容操作十分耗时，所以在使用的时候要适当的给定容量值。
- 对数组进行扩容，数组大小是不能改变的，所以这里使用了构建新数组，然后转移旧数组元素的方式来实现的。
- 这一点在 ArrayList 中也有体现。
- 所以，具体的流程如下：
- 排除异常情况
- 扩容2倍新建数组
- 转移数据
- 新数组引用到table上
- 重新设置阈值
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 threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = 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 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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//链表1存于原索引
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//链表2存于原索引加上原hash桶长度的偏移量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
- 经上分析之后，可以得出：在扩容后，原数组元素被分为了两部分：
- 索引位置要么不变
- 要么动旧容量个位置
- 链表转移数据的部分，分为了两个链表，通过下面的语句来判断
if ((e.hash & oldCap) == 0) {···}
- 扩容后，若hash值新增参与运算的位=0，那么元素在扩容后的位置=原始位置
- 扩容后，若hash值新增参与运算的位=1，那么元素在扩容后的位置=原始位置+扩容后的旧位置。
- hash值新增参与运算的位是什么呢？我们把hash值转变成二进制数字，新增参与运算的位就是倒数第五位。
- 这里面有一个非常好的设计理念，扩容后长度为原hash表的2倍，于是把hash表分为两半，分为低位和高位，如果能把原链表的键值对， 一半放在低位，一半放在高位，而且是通过e.hash & oldCap == 0来判断，这个判断有什么优点呢？
举个例子：n = 16，二进制为10000，第5位为1，e.hash & oldCap 是否等于0就取决于e.hash第5 位是0还是1，这就相当于有50%的概率放在新hash表低位，50%的概率放在新hash表高位。
线程安全性
- 不安全！
- 所以才会有了
ConcurrentHashMap，它的功能和HashMap是一样的，但它支持并发访问。
解决冲突
- java 中 HashMap 采用的是 链地址法 来解决冲突的。
- 哈希碰撞： 在插入数据时，通过hash算法计算出来的index这个位置，在哈希桶数组上已经存在元素，则会出现哈希冲突（哈希碰撞更官方）。
- 发生冲突之后会解决冲突：将数据挂在初始化位置（有点问题）的链表后（尾插法），然后当某个结点出现过多的链表结点之后，就会转换为红黑树以提高效率
学完 HashMap 原理之后，我们应该解决的问题
HashMap的底层数据结构是什么？
jdk1.7 及之前的版本是：数组 + 链表
jdk1.8 版本是：数组 + 链表 + 红黑树
为什么是红黑树呢？
红黑树是一个自平衡的二叉查找树，也就是说红黑树的查找效率是非常的高，查找效率会从链表的o(n)降低为o(logn)。
为什么不一下子把整个链表变为红黑树呢？
1. 构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。
2. HashMap 频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率。
HashMap中增删改查操作的底部实现原理是什么？
太多了，自己想想put过程、数据结构等
为什么HashMap容量一定要为16或者2的幂呢？
HashMap 采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少hash碰撞，HashMap 定位哈希桶索引位置时，也加入了高位参与运算的过程。
长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
如果不为16或者2的幂，那么，经过hash算法之后，有些index结果出现的概率会更大，而有些index则永远步会出现。即不符合hash算法的j均匀分布的原则。
为什么负载因子默认值会是0.75呢？
在HashMap的源码中有这样一段注解：
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*
大概意思就是：在理想情况下，使用随机哈希吗，节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素的个数和概率的对照表。
从上表可以看出当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为负载因子，每个碰撞位置的链表长度超过8个是几乎不可能的。
hash容器指定初始容量尽量为2的幂次方。
HashMap负载因子为0.75是空间和时间成本的一种折中。
HashMap是如何实现扩容的？
结合resize扩容过程思考，注意转移数据的时候是两个链表（hash表高低位）。
HashMap是如何解决hash冲突的？
链地址法！！！
哈希桶数组元素发生哈希碰撞，产生链表，链表长度不小于8（数组大小不小于64），转换为链表。
HashMap为什么是非线程安全的？
- HashMap不是线程安全的，在多线程并发的环境下，可能会产生死锁等问题。
- 补充一点 Hashtable 是线程安全的。还有并发的 HashMap ：ConcurrentHashMap（java5引入的）。
因为源码里面方法全部都是非线程安全的呀。
可以将 HashMap 转变为线程安全的：
HashMap<Integer, String> hashMap1 = (HashMap<Integer, String>) Collections.synchronizedMap(hashMap);
HashMap 与 Hashtable 的区别？
- Hashtable 是java的遗留类，java4的时候被重写了，加入了集合类。
1. HashMap线程不安全，是非synchronized的，Hashtable是线程安全的。
2. HashMap可以接受null(HashMap可以接受为null的键值(key)和值(value))，而Hashtable则不行。
3. 是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
4. 由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
5. HashMap不能保证随着时间的推移Map中的元素次序是不变的。
6. 继承的父类不同、作者不同，产生时间不同。HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。不过它们都实现了同时实现了Map、Cloneable（可复制）、Serializable（可序列化）这三个接口
7. 初始容量大小和每次扩充容量大小的不同。Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
8. 计算hash值的方法不同。为了得到元素的位置，首先需要根据元素的Key计算出一个hash值，然后再用这个hash值来计算得到最终的位置。Hashtable直接使用对象的hashCode。然后再使用取余来获得最终的位置，比较耗时。HashMap是通过位运算来进行操作的，效率高。
下面是 Hashtable 的确定索引方法：
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
该怎么设置HashMap的阈值和负载因子呢？
个人认为，不需要设置。只需要设置好数组容量大小就好了。
