前言
本文主要讲解HashMap的底层数据结构、存取原理、扩容机制、线程安全性、java 7 和java 8版本的对比等方面。如果你正在学习HashMap，希望对你有帮助。
如果你需要目录，可以查看这篇关于简书生成目录的文章。
.
简介
HashMap 是由数组和链表组合构成的数据机构。JDK1.7 和 JDK 1.8 的HashMap底层略有不同。
HashMap根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，具有很快的访问速度，但遍历顺序是不确定的。
HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
HashMap是非线程安全的。
.
底层数据结构
HashMap 是数组 + 链表 + 红黑树（JDK1.8 新增了红黑树部分）构成的。
结构图如下：
HashMap结构图.png
HashMap是一个存储Key-Value键值对的集合，每一个键值对也称Entry（Java8中叫Node），这些Entry分散存储在一个数组中，这个数组就是HashMap的主干。
HashMap_Node源码.png
数组存放的是Node，通过查看Node的源码，可以发现每个节点都会保存自身的hash、key、value 以及下一个节点的引用next。
之所以JDK1.8加入了红黑树，是为了提高效率，因为在JDK1.7的时候只有链表，存放的数据一多就容易导致链表变长，降低了效率。
只有在链表的长度不小于8，而且数组的长度不小于64的时候才会将链表转化为红黑树
.
存取原理
在JDK1.7的时候，HashMap存放数据采用的是头插法，JDK1.8改为尾插法
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static int indexFor(int hash, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
.
采用头插法（JDK1.7）
HashMap在put数据的时候会根据 index = indexFor(hash, table.length) 计算出index值，如：put("name", ''xiaoming')的时候就通过上面式子计算出 index = 2 ，那么这个键值对就存放到数组下标为2的位置。
我们知道数组的长度是有限的，在有限的长度里面使用哈希就会有概率两个key都hash到一个值上，这个时候新来的key就会取代原位置上的key，原位置的key就顺推到新来的key后面去，形成一个链表。
头插法：新来的值会取代原有的值，原有的值顺推到链表中去。
为什么这么设计？因为作者认为后来的值被查找的可能性更大一些，提升查找的效率。
.
确定key的存放位置（JDK1.7）
从上面我们知道HashMap是如何存储数据的，接下来，我们需要了解HashMap是如何确定key在数组中的存放位置。
我们知道 index 是通过 indexFor(int hash, int length) 得到的，而hash值是通过 hash(Object key) 得到的。那么如何使得得到的下标 index 在数组中均匀分布呢？
可以利用Key的hash值和HashMap的长度做取模运算，但取模运算效率低，在HashMap中是这样子来计算index的：index = hash(Key) & (length - 1)。
当 length 总是 2ⁿ 时，上面式子就等价于对 length 取模。
2ⁿ - 1 用二进制表示，所有位都是 1 ，根据 & 运算的规则，可以知道Hash算法最终得到的index结果，完全取决于Key的HashCode值的最后几位。
这里有个问题：为什么HashMap的长度必须是16或者是2的幂？
答：为了实现均匀分布。因为只要是2的幂，那么
Length - 1的值的所有二进制位都为1，这种情况下index的值就等同于HashCode最后几位的值。只要HashCode是分布均匀的，Hash(Key)的结果就是均匀的。而其他数可能会导致有些index的结果出现几率更大或有些index结果永远不会出现。
.
确定key的存放位置（JDK1.8）
JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位（扰动函数）实现的：
(h = key.hashCode()) ^ (h >>> 16)
使用扰动函数的目的：为了混合原始哈希码的高位和低位，以此来加大低位随机性，降低发生hash冲突的概率。
下面一个例子，n为数组的长度
HashMap_计算下标.png
.
扩容机制
HashMap采用懒加载，构造完HashMap对象后并未初始化数组table，而是在第一调用 put() 时调用resize方法进行初始化。
当向HashMap容器添加元素的时候，会判断当前容器中的元素个数，如果大于或等于阈(yù)值 ——当前数组的长度乘以负载因子（LoadFactor），就需要扩容数组，java里面的数组是无法动态增加长度的，方法就是使用一个新的数组替换旧数组。新数组的长度是原数组长度的2倍。
对于resize的源码，JDK1.7和JDK1.7是不同的，区别在于JDK1.8加入了红黑树，更为复杂，但本质区别不大。
.
扩容过程（JDK1.7）
jdk1.7的扩容做法就是简单的创建一个新的Entry空数组（长度是原数组的2倍），然后遍历原数组，将所有的Entry重新Hash到新的数组中去，最后修改阈值。
转移过程示例：
HashMap_链表转移过程.png
为什么需要重新Hash呢？
答：因为长度扩大后，Hash的规则也随之改变。Hash的公式：
index = HashCode(key) & (length - 1)
.
线程不安全性
为什么JDK1.7使用头插法，JDK1.8使用尾插法？
JDK1.7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
JDK1.8在同样的前提下不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。
在容量为2的容器中用不同的线程插入A、B、C，如果在resize之前打断点，则意味着A、B、C都插入了，但是还未扩容，那么有可能出现一种情况：在同一个index上的链表中是这样子的： A —> B —> C
因为使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。
也就是说在resize的时候，有可能出现这一种情况：在同一个index上， A先放进来，然后B后放进来，就出现了这样子的情况：B —> A —> B
可以看出来形成了一个环形链表了，取值的时候需要遍历链表，这个时候就会出现死循环。
而JDK1.8改用尾插法便可以解决这一个问题。
HashMap 的线程不安全性主要体现在：
-
在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
-
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
虽然JDK1.8不会出现死循环，当是仍然不可以将HashMap用于多线程中，put/get方法都是未加同步锁的，容易出现：上一秒put的值，下一秒get的时候还是原值，所以无法保证线程安全。
多线程环境下应该使用
ConcurrentHashMap
.
扩容过程（JDK1.8）
jdk1.8 引入红黑树，因此扩容过程多了对红黑树的处理，并且对重Hash做了优化，比较复杂。
resize() 的源码如下：
final Node<K,V>[] resize() {
// 把当前底层数组赋值给oldTab，为数据迁移工作做准备 —— 拿到原数组的引用
Node<K,V>[] oldTab = table;
// 获取当前数组的大小，如果未初始化数组，则为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取扩容前的阈值（容量 * 负载因子）
int oldThr = threshold;
// 定义并初始化新数组长度和目标阈值
int newCap, newThr = 0;
// 判断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。
// 若 oldCap > 0 表示需扩容而非初始化
if (oldCap > 0) {
// 判断数组长度是否已经是默认最大，MAXIMUM_CAPACITY = 1 << 30 = 2^30
// 超过默认最大容量则不再进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值设置为最大
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果新数组长度扩大2倍后小于最大容量，并且原数组容量大于等于默认初始化容量（16）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 目标阈值扩展2倍，数组长度扩展2倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
// 说明调用的是HashMap的有参构造函数，因为无参构造函数并没有对threshold进行初始化
newCap = oldThr;
// 表示需要初始化数组而不是扩容，零初始阈值表示使用默认值
else {
// 说明调用的是HashMap的无参构造函数
newCap = DEFAULT_INITIAL_CAPACITY;
// 计算目标阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 当目标阈值为0时需重新计算，公式：容量（newCap）* 负载因子（loadFactor）
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;
// 将数组内此下标中的数据赋值给Node类型的变量e，并判断非空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1 - 普通元素判断：判断数组内此下标中是否只存储了一个元素，
// 是的话表示这是一个普通元素，并开始转移
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 2 - 红黑树判断：判断此下标内是否是一颗红黑树，是的话进行数据迁移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3 - 链表判断：若此下标内包含的数据既不是普通元素又不是红黑树，
// 则它只能是一个链表，进行数据转移
else { // preserve order
// 之所以定义两个头两个尾对象,是由于链表中的元素的下标在扩容后,
// 要么不变，要么是原下标+oldCap
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 判断元素是否需要改变索引，从而分成两个链表
// 一个存放位置不变的元素，一个存放位置需要改变的元素
// 注意：位置需要改变的那个链表中的元素在新数组中的index是一样的
if ((e.hash & oldCap) == 0) {
if (loTail == null)
// 第一个节点
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}
.
JDK1.8 对重Hash的优化
回顾一下jdk1.8的计算key在数组的下标的方式：获取key的hashCode，然后将hashCode的16位异或低16位获得hash，最后将 hash & (n - 1) 得到 index，如果将原数组转移到新数组中都需要这样子重新计算Hash，那对整体的性能肯定有影响。
通过观察转移过程可以发现，每次扩容后数组的长度都是原来的2倍，也就是说，数组的长度是 2ⁿ ，所以，元素的新位置要么是在原位置，要么是在原来的位置上移动原数组长度的位置。
上面的源码是通过 if ((e.hash & oldCap) == 0) 来将原链表分成两个，一个存位置不需要改变的元素，一个存位置需要改变的元素，然后遍历完一个index下的链表后，再将两个链表分别移到新数组当中去。即源码中的 newTab[j] = loHead; 和 newTab[j + oldCap] = hiHead;
看下图，其中 hash1 是 key1 对应的 hashCode 与高位运算的结果：
HashMap_重hash优化计算index.png
图中 n是数组的长度，扩容后 n 会变成原来的2倍，就相当于在原来的 n-1 的二进制表示中的高位多1bit（红色），因此新的index不必要重新计算hash，只需要看 n - 1 新增的那个1bit位对应的 key 的hash的那个位是 0 还是 1，如果是0，那么index不变，如果是1，那么index = 原来的index + 原来数组的长度。
看下图：
HashMap_确定index是否需要改变.png
(e.hash & oldCap) == 0为什么是oldCap 而不是 oldCao - 1 ？假设原数组长度为16，那么 oldCap 的二进制为 1 0000 ， oldCap - 1 的二进制为 0 1111
我们需要判断的是长度扩大后那个新增位是 0 还是 1
而 oldCap 的二进制有一个1并且这个1对应上了那个新增位，此时进行
&运算就可以得知新增位是0还是1
.
重写 equals() 必须重写 hashCode()
在java中，所有类的祖先类都是 Object，Object类中有两个方法 equals 和 hashCode，这两个方法都可以用来比较两个对象是否相等。
对于值类型，== 比较的是两个变量的值，而对于引用类型，== 比较的是两个变量的地址。
Object的equals方法源码：
// 可以看到Object类的equals方法比较的是地址。
public boolean equals(Object obj) {
return (this == obj);
}
hashCode()方法源码中有一段注释：
在 Java 应用程序执行期间，在对同一对象多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
如果根据 equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么对这两个对象中的任一对象上调用 hashCode 方法不要求一定生成不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同整数结果可以提高哈希表的性能。
所以，源码的注释来看，两方法同时重写是很必要的。
前提条件，当我们在使用HashMap、HashSet等集合时：
如果重写了equals方法而不重写hashCode方法，那么就会出现通过equals方法比较相等的两个对象因hashCode不同，而被存到HashMap中数组的不同index下（我们知道key的index是根据hashCode计算而来的），这就会导致HashMap存了2个一样的key，那么在调用HashMap方法的时候就会出现逻辑错误。
.
TODO：
四个构造方法的分析
put/get 方法源码研读
扩容时红黑树的转移过程
.
常见面试题
HashMap的底层数据结构？
hash冲突是什么？解决hash冲突常见的方法有哪些？HashMap是如何解决hash冲突的？
HashMap是如何计算hash的？为什么要用hashCode的高16位异或低16位（扰动函数）？
HashMap的存取原理？
HashMap的默认初始化大小是多少？为什么是这么多？为什么大小都是 2ⁿ ？
HashMap的负载因子是多少？为什么是这么多？
说一下HashMap的扩容机制？什么时候进行扩容？扩容的过程是怎么样的？
HashMap为什么线程不安全？有什么有可替代的集合？
Java 7 和 Java 8 的区别是什么？Java 8 为什么要增加红黑树？链表何时转为红黑树？
Java 7 为什么使用头插法而java8改用尾插法？
Java 8 对重hash的优化是怎么样的？为什么是oldCap 而不是 oldCao - 1 ？
.
鸣谢
在学习HashMap底层原理的时候，拜读了以下文章，收获良多，在此感谢一下作者！
网友评论