前言

手执烟花以谋生 心怀诗意以谋爱

不论我是否去记录，在往昔与未来的无限岁月中，仍会有人奋起，有人沉沦，有人成为英雄，有人扮演小丑，有人挺身而出，有人迷惘沉沦。但你只需——“在繁华中自律，在落魄中自愈，在谋生的路上不抛弃良知，在谋爱的路上不丢失最严，这次我站在风中，任你大雾四起。”

HashMap的设计原理

1. HashMap设计思路：

1. Map是一种以键值对存储数据的容器，而 HashMap 则是借助了键值 Key 的 hashcode 值来组织存储，使得可以非常快速和高效地地根据键值 key 进行数据的存取。
2. 对于键值对，HashMap 内部会将其封装成一个对应的 Entry 对象，即 Entry 对象是键值对的组织形式；
3. 对于每个对象而言，JVM 都会为其生成一个 hashcode 值。HashMap 在存储键值对 Entry 的时候，会根据 Key 的 hashcode 值，以某种映射关系，决定应当将这对键值对 Entry 存储在 HashMap 中的什么位置上；
4. 当通过 Key 值取数据的时候，然后根据 Key 值的 hashcode 和 内部映射条件，直接定位到 Key 对应的 Value 值存放在什么位置，可以非常高效地将 Value 值取出。

HashMap 的哈希函数设计

hash 函数是先拿到 key 的 hashcode，是一个32位的 int 值，然后让 hashcode 的高16位和低16位进行异或操 作

也叫扰动函数，这么设计有二点原因

1. 一定要尽可能降低 hash 碰撞，越分散越好；
2. 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

什么是Hash？

    Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的 `输入`，通过散列算法变换成固定长度的 `输出`，该输出就是散列值。ok，这样的定义可能比较抽象。咱们结合上面提到的方案二的例子一句一句解释。

• 比如：人的姓名就是一个任意长度的输入。Z-张三 11; L-李四 22；W-王五 33
• 然后，直接去Z分类里边儿找，一发入魂。但是如果出现很多姓名的首字母是Z的人，比如Z-赵六 44、Z-周七 55，当我存的电话多起来，我一样需要找好多次。——我按照姓名的首字母的大写去进行一个分类，这个划分的方式我们可以看成是散列算法。
• 最后，在本子上以姓名的首字母划分，并记录电话号码——固定长度的输出，即我把所有的电话全部存入了26个分类中。那么这26个字母就是散列值。

? HashMap 的数据结构（JDK 1.8）

本文说的是 JDK1.8 版本的，内部使用数组 + 链表红黑树

• 在 Jdk1.8 中 HashMap 的实现方式做了一些改变，但是基本思想还是没有变得，只是在一些地方做了 优化，下面来看一下这些改变的地方：数据结构的存储由数组+链表的方式，变化为 数组+链表+红黑树的存储方式，当链表长度超过 阈值（8） 时，将 链表转换为红黑树。在性能上进一步得到提升。
• 数组：数组存储区间是连续的，占用内存严重，故空间复杂度很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难； 空间复杂度：指的是执行算法所需要的内存空间 时间复杂度：执行算法所需要的计算工作量
• 链表：链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
• 红黑树：

JDK1.8 对 HashMap 主要做了哪些优化呢？

1. 数组 + 链表改成了数组 + 链表或红黑树；
2. 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7 将新元 素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后；
3. 扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻 辑，位置不变或索引 + 旧容量大小；
4. 在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

?为什么要做这几点优化

1. 防止发生 hash 冲突，链表长度过长，将时间复杂度由 O(n) 降为 O(logn) ;
2. 因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环； A 线程在插入节点 B，B 线程也在插入，遇到容量不够开始扩容，重新 hash，放置元素，采用头插法， 后遍历到的 B 节点放入了头部，这样形成了环，如下图所示：

1.7 的扩容调用 transfer 代码，如下所示：

void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	for (Entry<K,V> e : table) {
		while(null != e) {
			Entry<K,V> next = e.next;
			if (rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			} 
			int i = indexFor(e.hash, newCapacity);
			e.next = newTable[i]; //A线程如果执行到这一行挂起，B线程开始进行扩容
			newTable[i] = e;
			e = next;
		}
	}
}  

3. 扩容的时候为什么 1.8 不用重新 hash 就可以直接定位原节点在新数据的位置 这是由于扩容是扩大为原数组大小的 2 倍，用于计算数组位置的掩码仅仅只是高位多了一个 1，怎么理 解呢？ 扩容前长度为 16，用于计算 (n-1) & hash 的二进制 n-1 为 0000 1111，扩容为 32 后的二进制就高位多 了 1，为 0001 1111。 因为是 & 运算，1 和任何数 & 都是它本身，那就分二种情况，如下图：原数据 hashcode 高位第 4 位为 0 和高位为 1 的情况； 第四位高位为 0，重新 hash 数值不变，第四位为 1，重新 hash 数值比原来大 16（旧数组的容量）