Map 类集合
Java Map 类集合，与 Collections 类集合存在很大不同。它是与 Collection 类平级的一个接口。
在集合框架中，通过部分视图方法这一根 微弱的线联系起来。
（在之后的分享中，我们会讨论到 Collections 框架的内容）
Map 类集合中的存储单位是 K - V 键值对，就是 使用一定的哈希算法形成一组比较均匀的哈希值作为 Key，Value 值挂在 Key 上。
Map 类 的特点：
- 没有重复的 Key，可以具有多个重复的 Value
- Value 可以是 List/Map/Set 对象
- KV 是否允许为 null，以实现类的约束为准
| Map 集合类 | Key | Value | Super | JDK | 说明 |
|---|---|---|---|---|---|
| Hashtable | 不允许为 null | 不允许为 null | Dictionary | 1.0 | （过时）线程安全类 |
| ConcurrentHashMap | 不允许为 null | 不允许为 null | AbstractMap | 1.5 | 锁分段技术或 CAS（JDK8 及以上） |
| TreeMap | 不允许为 null | 允许为 null | AbstractMap | 1.2 | 线程不安全（有序） |
| HashMap | 允许为 null | 允许为 null | AbstractMap | 1.2 | 线程不安全（resize 死链问题） |
从 jdk1.0-1.5，这几个重点 KV 集合类，见证了 Java 语言成为工业级语言的成长历程。
知识点：
- Map 类 特有的三个方法是
keySet()、values()、entrySet()，其中values()方法返回的视图的集合实现类是Values extends AbstractCollection<V>，没有实现 add 操作，实现了 remove/clear 等相关操作，调用 add 方法时会抛出异常。 - 在大多数情况下，直接使用 ConcurrentHashMap 替代 HashMap 没有任何问题，性能上面差别不大，且线程安全。
- 任何 Map 类集合中，都要尽量避免 KV 设置为 null 值。
- Hashtable – HashMap – ConcurrentHashMap 之间的关系 大致相当于 Vector – ArrayList – CopyOnWriteArrayList 之间的关系，当然 HashMap 和 ConcurrentHashMap 之间性能差距更小。
一、hashCode()
哈希算法 哈希值
在 Object 类中，hashCode()方法是一个被 native 修饰的类，JavaDoc 中描述的是返回该对象的哈希值。
那么哈希值这个返回值是有什么作用呢？
主要是保证基于散列的集合，如 HashSet、HashMap 以及 HashTable 等，在插入元素时保证元素不可重复，同时为了提高元素的插入删除便利效率而设计；主要是为了查找的便捷性而存在。
拿 Set 进行举例，
众所周知，Set 集合是不能重复，如果每次添加数据都拿新元素去和集合内部元素进行逐一地 equal()比较，那么插入十万条数据的效率可以说是非常低的。
所以在添加数据的时候就出现了哈希表的应用，哈希算法也称之为散列算法，当添加一个值的时候，先去计算出它的哈希值，根据算出的哈希值将数据插入指定位置。这样的话就避免了一直去使用 equal()比较的效率问题。
具体表现在：
- 如果指定位置为空，则直接添加
- 如果指定位置不为空，调用 equal() 判断两个元素是否相同，如果相同则不存储
上述第二种情况中，如果两个元素不相同，但是 hashCode()相同，那就是发生了我们所谓的哈希碰撞。
哈希碰撞的概率取决于 hashCode()计算方式和空间容量的大小。
这种情况下，会在相同的位置，创建一个链表，把 key 值相同的元素存放到链表中。
在 HashMap 中就是使用拉链法来解决 hashCode 冲突。
总结
hashCode 是一个对象的标识，Java 中对象的 hashCode 是一个 int 类型值。通过 hashCode 来指定数组的索引可以快速定位到要找的对象在数组中的位置，之后再遍历链表找到对应值，理想情况下时间复杂度为 O(1)，并且不同对象可以拥有相同的 hashCode。
HashMap 底层实现
带着问题
- HashMap 的长度为什么默认初始长度是 16，并且每次 resize()的时候，长度必须是 2 的幂次方？
- 你熟悉 HashMap 的扩容机制吗？
- 你熟悉 HashMap 的死链问题吗？
- Java 7 和 Java 8 HashMap 有哪些差别？
- 为什么 Java 8 之后，HashMap、ConcurrentHashMap 要引入红黑树？
0. 简介
- HashMap 基于哈希表的 Map 接口实现的，是以 Key-Value 存储形式存在；
- 非线程安全；
- key value 都可以为 null；
- HashMap 中的映射不是有序的；
- 在 JDK1.8 中，HashMap 是由 数组 + 链表 + 红黑树构成，新增了红黑树作为底层数据结构；
- 当一个哈希桶存储的链表长度大于 8 会将链表转换成红黑树，小于 6 时则从红黑树转换成链表；
- 1.8 之前和 1.8 及以后的源码，差别较大
1. 存储结构
在 JDK1.8 中，HashMap 是由 数组 + 链表 + 红黑树构成，新增了红黑树作为底层数据结构。
通过哈希来确认到数组的位置，如果发生哈希碰撞就以链表的形式存储，但是这样如果链表过长来的话，HashMap 会把这个链表转换成红黑树来存储，阈值为 8。
下面是 HashMap 的结构图：
2. 重要属性
2.1 table
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;在 JDK1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构其中 table 就是 HashMap 中的数组。
2.2 size
/**
* The number of key-value mappings contained in this map.
*/
transient int size;HashMap 中 键值对存储数量。
2.3 loadFactor
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;负载因子。负载因子是权衡资源利用率与分配空间的系数 。当 元素总量 > 数组长度 * 负载因子 时会进行扩容操作。
2.4 threshold
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;扩容阈值。threshold = 数组长度 * 负载因子。超过后执行扩容操作。
2.5 TREEIFY_THRESHOLD/UNTREEIFY_THRESHOLD
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
树形化阈值。当一个哈希桶存储的链表长度大于 8 会将链表转换成红黑树，小于 6 时则从红黑树转换成链表。
3. 增加元素
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}3.1 hash()
可以看到实际执行添加元素的是 putVal()操作，在执行 putVal()之前，先是对 key 执行了 hash()方法，让我们看下里面做了什么
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是 hashcode
// ^：按位异或
// >>>: 无符号右移，忽略符号位，空位都以 0 补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}key==null说明，HashMap 中是支持 key 为 null 的情况的。
同样的方法在 Hashstable 中是直接用 key 来获取 hashCode，没有 key==null 的判断，所以 Hashstable 是不支持 key 为 null 的。
再回来说这个 hash()方法。这个方法用专业术语来称呼就叫做 扰动函数。
使用 hash()也就是扰动函数，是 为了防止一些实现比较差的 hashCode()方法 。换句话来说， 就是为了减少哈希碰撞。
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。我们再看下 JDK1.7 中是怎么做的。
// code in JDK1.7
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
知识延伸外链：JDK 源码中 HashMap 的 hash 方法原理是什么？– 胖君的回答 – 知乎
https://www.zhihu.com/questio…
3.2 putVal()
再来看真正执行增加元素操作的 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;
// 当数组为空或长度为 0，初始化数组容量（resize() 方法是初始化或者扩容用的）if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 计算数组下标 i = (n-1) & hash
// 如果这个位置没有元素，则直接创建 Node 并存值
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))))
// hash 值、key 值相等，用 e 变量获取到当前位置这个元素的引用，后面用于替换已有的值
e = p;
else if (p instanceof TreeNode)
// 当前是以红黑树方式存储，执行其特有的 putVal 方法 -- putTreeVal
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 1st
// 超过阈值，存储方式转化成红黑树
treeifyBin(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 key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// onlyIfAbsent 如果为 true - 不覆盖已存在的值
// 把新值赋值进去
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 记录修改次数
++modCount;
// 判断元素数量是否超过阈值 超过则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}3.3 HashMap 的长度为什么默认初始长度是 16，并且每次 resize()的时候，长度必须是 2 的幂次方？
这是一个常见的面试题。这个问题描述的设计，实际上为了服务于从 Key 映射到数组下标 index 的 Hash 算法。
前面提到了，我们为了让 HashMap 存储高效，应该尽量减少哈希碰撞，也就是说，应该让元素分配得尽可能均匀。
Hash 值的范围值 -2147483648 到2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。
所以才需要一个映射的算法。这个计算方式就是 3.2 中有出现的(n - 1) & hash。
我们来进一步演示一下这个算法：
- 假设有一个
key="book" - 计算
book的 hashCode 值，结果为十进制的 3029737，二进制的 101110001110101110 1001。 - 假定 HashMap 长度是默认的 16，计算 Length- 1 的结果为十进制的 15，二进制的 1111。
- 把以上两个结果做 与运算，101110001110101110 1001 & 1111 = 1001，十进制是 9，所以 index=9。
通过这种 与运算 的方式，能够和取模运算一样的效果hashCode % length，在上述例子中就是3029737 % 16=9。
并且通过位运算的方式大大提高了性能。
可能到这里，你还是不知道为什么长度必须是 2 的幂次方，也是因为这种位运算的方法。
长度 16 或者其他 2 的幂，Length- 1 的值是所有二进制位全为 1，这种情况下，index 的结果等同于 HashCode 后几位的值。只要输入的 HashCode 本身分布均匀，Hash 算法的结果就是均匀的。如果 HashMap 的长度不是 2 的幂次方，会出现某些 index 永远不会出现的情况，这个显然不符合均匀分布的原则和期望。所以在源码里面一直都在强调 power-of-two expansion 和size must be power of two。
另外，HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。
/**
* Returns a power of two size for the given target capacity.
*/
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;
}4. HashMap 扩容
接下来我们来讲讲 HashMap 扩容相关的知识。
4.1 扩容
HashMap 的初始长度是 16，假设 HashMap 中的键值对一直在增加，但是 table 数组容量一直不变，那么就会发生哈希碰撞，查找的效率肯定会越来越低。所以当键值对数量超过某个阈值的时候，HashMap 就会执行扩容操作。
那么扩容的阈值是怎么计算的呢？
阈值 = 数组长度 * 负载因子
threshold = capacity * loadFactor
每次扩容后，threshold 加倍
上述计算就出现在 resize()方法中。下面会详细解析这个方法。我们先继续往下讲。
loadFactor 这个参数，我们之前提到过，负载因子是权衡资源利用率与分配空间的系数。至于为什么是 0.75 呢？这个实际上就是一个作者认为比较好的权衡，当然你也可以通过构造方法手动设置负载因子。public HashMap(int initialCapacity, float loadFactor) {...)。
接下去再来到这里的主角 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;
}
// newCap 变成原来的 两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 执行扩容操作，新阈值 = 旧阈值 * 2
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 引用的数组
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
....
}
}
}
}
return newTab;
} // 链表的处理 这个链表处理实际上非常的巧妙
// 定义了两条链
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;
}
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;
}上述代码红黑树和链表的处理不知道大家看懂了没有，我反正在第一次看的时候有点晕乎。但是理解了之后有感觉非常的巧妙。
拿链表处理打比方，它干的就是把在遍历旧的 table 数组的时候，把该位置的链表分成 high 链表和 low 链表。具体是什么意思呢？看下下面的举例。
- 有一个 size 为 16 的 HashMap。有 A /B/C/D/E/ F 六个元素，其中 A /B/ C 的 Hash 值为 5，D/E/ F 的 Hash 值为 21，我们知道计算数组下标的方法是 与运算（效果相当于取模运算），这样计算出来，A/B/C/D/E/ F 的 index = 5，都会被存在 index= 5 的位置上中。
- 假设它们是依次插入，那么在 index 为 5 的位置上，就会有
A->B->C->D->E->F这样一个链表。 - 当这个 HashMap 要进行扩容的时候，此时我们有旧数组 oldTable[]，容量为 16，新数组 newTable[]，容量为 32（扩容数组容量加倍）。
- 当遍历到旧数组 index= 5 的位置的时候，进入到上面提到的链表处理的代码段中，对链表上的元素进行
Hash & oldCapacity的操作，Hash 值为 5 的 A /B/ C 计算之后为 0，被分到了 low 链表，Hash 为 21 的 D /E/ F 被分到了 high 链表。 - 然后把 low 链表放入新数组的 index= 5 的位置，把 high 链表放入到新数组的 index=5+16=21 的位置。
红黑树相关的操作虽然代码不同，但是实际上要干的事情是一样的。就是把 相同位置的不同 Hash 大小的链表元素在新 table 数组中进行分离。希望讲到这里你能听懂。
4.2 HashMap 死链问题
Java7 的 HashMap 会存在死循环的问题，主要原因就在于，Java7 中，HashMap 扩容转移后，前后链表顺序倒置，在转移过程中其他线程修改了原来链表中节点的引用关系，导致在某 Hash 桶位置形成了环形链表，此时 get(key)，如果 key 不存在于这个 HashMap 且 key 的 Hash 结果等于那个形成了循环链表的 Hash 位置，那么程序就会进入死循环；
Java8 在同样的前提下并不会引起死循环，原因是Java8 扩容转移后前后链表顺序不变，保持之前节点的引用关系。
void resize(int newCapacity) {Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// JDK8 移出了 hashSeed 计算，因为计算时会调用 Random.nextInt()，存在性能问题
// 很重要的 transfer()
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 在此步骤完成之前，旧表上依然可以进行元素的增加操作，这就是对象丢失原因之一
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}// 寥寥几行，却极为重要
void transfer(Entry[] newTable, boolean rehash) {
// newCapacity 是旧表的两倍，这个扩容大小
int newCapacity = newTable.length;
// 使用 foreach 方式遍历整个数组下标
for (Entry<K,V> e : table) {
// 如果在这个 slot 上面存在元素，则开始遍历上面的链表，知道 e ==null，退出循环
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);
// 当前元素总是直接放在数组下标的 slot 上，而不是放在链表的最后
// 倒序插入新表
// 这里是形成死链的关键步骤
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}延伸阅读。
https://www.yuque.com/docs/sh…
5. Java 8 与 Java 7 对比
- 发生 hash 冲突时，Java7 会在链表头部插入，Java8 会在链表尾部插入
- 扩容后转移数据，Java7 转移前后链表顺序会倒置，Java8 还是保持原来的顺序
- 引入红黑树的 Java8 极大程度地优化了 HashMap 的性能‘
- put 操作达到阈值时，Java7 中是先扩容再新增元素，Java8 是先新增元素再扩容；
- Java 8 改进了 hash() 扰动函数，提高了性能
6. 为什么要使用红黑树？
很多人可能都会答上一句，为了提高查找性能，但更确切地来说的话，采用红黑树的方法是为了提高 在极端哈希冲突的情况 下提高 HashMap 的性能。
极端哈希冲突的情况下，去测量 Java7 和 Java8 版本的 HashMap 的查询性能差距。
Java 7 的结果是可以预期的。HashMap.get()的性能损耗与 HashMap 本身的大小成比例增长。由于所有键值对都在一个巨大的链表中的同一个桶中，查找一个条目需要平均遍历一半这样的列表（大小为 n）。因此 O(n)复杂性在图上可视化。
与此相对的是 Java8，性能提高了很多，发生灾难性哈希冲突的情况下，在 JDK 8 上执行的相同基准测试会产生 O（logn）最差情况下的性能。
关于此处的算法优化实际上在 JEP-180 中有描述到，
另外如果 Key 对象如果不是 Comparable 的话，那么发生重大哈希冲突时，插入和删除元素的效率会变很差。（因为底层实现时红黑树，需要通过 compare 方法去确定顺序）
当 HashMap 想要为一个键找到对应的位置时，它会首先检查新键和当前检索到的键之间是否可以比较（也就是实现了 Comparable 接口）。如果不能比较，它就会通过调用 tieBreakOrder(Objecta,Object b) 方法来对它们进行比较。这个方法首先会比较两个键对象的类名，如果相等再调用 System.identityHashCode 方法进行比较。这整个过程对于我们要插入的 500000 个元素来说是很耗时的。另一种情况是，如果键对象是可比较的，整个流程就会简化很多。因为键对象自身定义了如何与其它键对象进行比较，就没有必要再调用其他的方法，所以整个插入或查找的过程就会快很多。值得一提的是，在两个可比的键相等时（compareTo 方法返回 0）的情况下，仍然会调用 tieBreakOrder 方法。
又可能会有人说了，哪有这么极端的哈希冲突？
这个实际上是一个安全性的考虑，虽然在正常情况下很少有可能发生很多冲突。但是想象一下，如果 Key 来自不受信任的来源（例如从客户端收到的 HTTP 头名称），那么就有可能收到伪造 key 值，并且这种做法不难，因为哈希算法是大家都知道的，假设有人有心去伪造相同的哈希值的 key 值，那么你的 HashMap 中就会出现上述这种极端哈希冲突的情况。现在，如果你去对这个 HashMap 执行多次的查询请求，就会发现程序执行查询的效率会变得很慢，cpu 占用率很高，程序甚至会拒绝对外提供服务。
延伸外链：https://www.yuque.com/docs/sh…