图解JDK 8 HashMap
HashMap-简介
HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。
HashMap-数据结构
这是 HashMap 类中的一个成员变量，它是一个存储桶数组。table 数组用于存储键值对的实际数据。
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
}
这是 HashMap 内部定义的静态嵌套类 Node，它实现了 Map.Entry 接口。每个 Node 对象表示 HashMap 中的一个键值对，它包含键、值以及指向下一个节点的引用，从结构上来看，HashMap中链表结构与LinkedList相似。
测试示例
public static void main(String[] args) {
HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("KING",100);
}图解HashMap-put方法
根据key获取hash值
Hash是将Key转换为一个短的、定长的值去替代源Key作为索引，以更快的查询。
通过hash方法得到"KING"对应的hash值为2306996。
计算方式：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}通过hash值得到对应的桶的Index
计算方式：
(n - 1) & hash如此，当调用put方法将元素添加到HashMap时，“KING”、100便被放入到Index为4的Node中。
由于index为4的Node节点并无除"KING"其他元素，所以它的下一个节点信息为null。用同样的方法将"CLARK"
，90放入HashMap。
不同的Key得到的Index值相同的情况
接下来我们把Key:“BLAKE”,value:10放入该Map，得到key值的hash为63281940：
根据63281940计算Index结果为4：
由于"KING"对应的Node节点也为4，Key："BLAKE"计算出的Index同样为4，不同的key通过哈希算法(n - 1) & hash计算出的索引位置相同时即为哈希冲突，HashMap在发生哈希冲突时，会将具有相同哈希码的键值对存储在同一个桶（bucket）中，通过链表或者在元素数量较多时转换为红黑树来处理冲突。如此，HashMap的结构将变为：
图解HashMap-get方法
HashMap的get方法用于获取指定键对应的值。
以获取"KING"的值为例：
Integer integer = hashMap.get("KING");
先计算出key的hash值，根据key值和key的hash值去获取Node信息。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}在定位到的桶中查找与给定键相匹配的节点。如果找到了匹配的节点，则返回该节点的值。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 数组元素相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中可能存在不止一个节点
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}先来明确一下各个变量的意义：
- key：要查询的指定key
- table：当前HashMap哈希表实际数据存储，用于存储节点的桶
- first：要查询的指定key匹配到某个桶的第一个节点
- e：临时节点，用于遍历桶中的节点链表或树结构。在这段代码中，e 用于遍历桶中的节点以查找匹配的键值对。
- n：这是一个整数，表示哈希表的长度，即桶的数量。
- k：这是一个键对象，表示 first 节点的键，即指定key计算后hash值对应桶的第一个节点的键。
链表
把上文源码链表部分翻译成一张图片：
图片局部放大：
当同一个Node<Key,Value>中存在多个元素时，开始根据key值和key的hash值在链表中匹配对应的value值。
红黑树
由于在链表中获取对应Value值的过程是通过for循环实现的，其时间复杂度为O(n)，当链表过长时，查询时间变长，JDK使用红黑树解决了该问题，当链表长度大于8时，链表进行树化。
红黑树结构
如果存储桶中的元素是一个红黑树，则通过红黑树的查找算法，在红黑树中查找具有相同哈希码并且键相等的节点。