关联博文
数据结构之Map基础入门与详解
认真学习Java集合之HashMap的实现原理
认真研究HashMap的读取和存放操作步骤
认真研究HashMap的初始化和扩容机制
认真研究JDK1.7下HashMap的循环链表和数据丢失问题
【1】数据结构
① jdk1.7
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。
也就是说创建一个链表数组，数组中每一格就是一个链表。
② jdk1.8
JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，且tab.length>64时，将链表转化为红黑树，以减少搜索时间。
也就是说创建一个数组，数组中每一格就是一个链表(或者红黑树)。本质上HashMap的数据存储就是Node<K,V>[] table这个成员。
③ 关于哈希桶中结点
可以看出每个哈希桶中每个结点包含了四个字段：hash、key、value、next，其中 next 表示链表的下一个节点。
static class Node<K,V> implements Map.Entry<K,V> {
//哈希值，存放元素到hashmap中时用来与其他元素hash值比较
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;
}
//...
}
④ TreeNode
前面提到了，可能转为红黑树。也就是说结点可能是TreeNode(其是Node的子类)。
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;
//...
}
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
以上的属性都是为了满足红黑树特性而设置。它还继承了别的类，如LinkedHashMap.Entry<K,V>。这个类包括了before属性和after属性，分别代表节点的上一个节点和下一个节点，也就组成了一个双向链表结构。因为TreeNode继承了LinkedHashMap.Entry<K,V>这个类，所以它也是可以使用这两个属性的。
LinkedHashMap.Entry<K,V>又继承了HashMap.Node<K,V>，TreeNode也就可以使用HashMap.Node<K,V>中的成员属性。
TreeNode类其实就通过这些继承关系既实现了红黑树结构，也维持了一个双向链表结构结构。
通过TreeNode自身属性left、right、parent、red四个属性实现了红黑树结构，通过自身属性prev和继承HashMap.Node<K,V>的next属性来实现了双向链表的结构。
【2】Jdk1.8环境下
① 读取数据
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
首先计算key的hash值，然后通过getNode方法获取结点，如果节点不为null则返回节点的value。
(1) 获取key的hash值
如下所示：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
int 是4字节，32位。>>>表示无符号右移16位。^ 表示异或-相同为0 不同为1。总结来说就是保留h的高16位，低16位变为(原高16位与低16位异或结果)。
(2) getNode
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
// (n - 1) & hash 确定下标
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断first节点是不是要找的目标，如果是则返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果first的next不为null
if ((e = first.next) != null) {
// 判断是否为红黑树结点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果不是树则查找链表的下一个
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//返回null
return null;
}
这里的first也就是根据(n - 1) & hash确定在数组中对应位置那个结点(链表或者树的结点)。
运气最好的时候就是first就是目标结点，否则就需要遍历链表或者从树上获取。前置的时间复杂度是O(n)，后者的时间复杂度是O(logn)
(3) getTreeNode
// h 是key的hash k -- key
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
首先获取当前节点root。如果parent为null，则表明this为root，否则递归获取其parent。然后触发find操作。
// h 是key的hash k -- key kc 最初为null
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
// P 表示当前将要判断、返回的
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
//如果ph>h ,p=pl;
if ((ph = p.hash) > h)
p = pl;
//如果ph<h ,p=pr;
else if (ph < h)
p = pr;
//如果ph==h 判断pk是否与k相等
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 如果ph==h 但是pk != k
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
//尝试触发compareTo方法 如果k<pk 则p=ol 否则p=pr
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
comparableClassFor： 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回null。这个方法的作用就是查看对象x是否实现了Comparable接口
compareComparables：如果x的类型是kc，返回k.compareTo(x)的比较结果。如果x为空，或者类型不是kc，返回0
pl 是p的左结点，pr是p的右结点。ph是p的hash，pk是p的k。h是目标key的hash(key)结果。kc是目标key的Class类型。
方法流程梳理如下：
- 如果ph>h，则将pl赋予p;
- 如果ph<h，则将pr赋予p;
- 如果
ph==h,且pk==k, 直接返回p; - 如果pl == null，则p=pr;
- 如果pr == null，则 p = pl;
- 如果kc不为null，尝试调用其compareTo方法进行比较，如果k<pk 则p=pl 否则p=pr;
- 最后手段如果q = pr.find(h, k, kc)!=null，返回q;
- 最终手段，直接 p = pl;
- 如果前面没有return，且p不为null，则进行下次循环。否则返回null
② 存放数据
如下所示，首先计算key的hash值。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
继续往下看，这是实际放入方法。n=table.length也就是数组的长度，tab表示数组，p表示意向目标结点，i 表示索引值((n - 1) & hash)。
TREEIFY_THRESHOLD 表示是否转为红黑树，临界值是8。也就是链表元素个数大于等于8时，将会触发转化为红黑树。
(1) putVal
n=table.length也就是数组的长度，tab表示数组，p表示意向目标结点，i 表示索引值((n - 1) & hash)。
TREEIFY_THRESHOLD 表示是否转为红黑树，临界值是8。也就是链表元素个数大于等于8时，将会触发转化为红黑树。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1.判断是否需要扩容，需要则扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2.判断目标位置是否为null，如果为null直接放入该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 如果目标位置有结点
Node<K,V> e; K k;
//如果结点 hash key都相等 则将p赋予e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果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);
//尝试转换为红黑树
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;
}
}
//如果e不为null，说明目标key原先有value，尝试覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 记录HashMap结构修改次数
++modCount;
//size是HashMap的键值对个数
//threshold记录每一次扩容后HashMap的容量，这里判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
//如果key并没oldValue，则返回null
return null;
}
afterNodeAccess(e);、 afterNodeInsertion(evict);对于HashMap来说其是空方法，子类LinkedHashMap实现了这两个方法。
(2) putTreeVal
这里是向红黑树中放入结点的过程，h表示目标key的hash。map 表示当前Hashmap对象，tab 表示 Hashmap对象中的table数组
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
//用来判断是否检索过左右孩子存在 hash=h key=k的节点
boolean searched = false;
// 找到根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
//从 p=root开始遍历,p 根节点，这个将会一直循环，直到return
for (TreeNode<K,V> p = root;;) {
//dir用来判断放到左孩子还是右孩子
int dir, ph; K pk;
//如果 ph >h ,dir=-1
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
//如果ph < h ,dir=1
dir = 1;
//ph == h 即索引位置 且key也相等 ，直接返回 p
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// ph == h hash冲突，但是key不同
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
//k.compareTo(pk)==0
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//递归查找，先查p.left，后查p.right
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//说明红黑树中没有与之equals相等的 那就必须进行插入操作
//打破平衡 分出大小 结果 只有(-1 1 )
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 根据dir判断p.left p.right是否为null，
//这里会将P重新赋值 left or right,如果不为null则进行下次循环
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//新建treeNode
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x; //左结点
else
xp.right = x;//右节点
//维护双向链表关系
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//将root移到table数组的 (n - 1) & root.hash 位置
//插入操作过红黑树之后 重新调整平衡
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
【3】Jdk1.7环境下
Jdk1.7下是数组+链表的数据结构，获取操作本质就是链表的遍历，存放操作则是链表的插入。与jdk1.8不同的是，jdk1.7在插入数据采取的头插式，jdk1.8链表插入是尾插式。
如下代码截取实例是jdk1.7.0_17环境下。
① 读取数据
如下所示，其原理其实很简单。
- 首先计算hash然后在桶内(数组)定位到索引位置，
- 然后对索引位置的链表进行遍历。
- 时间复杂度是O(N)。
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
// 其实也就是jdk1.8下的 (n - 1) & hash
static int indexFor(int h, int length) {
return h & (length-1);
}
在1.7中有一个很明显的地方是：当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低。在1.8 中对大链表做了优化，当链表转化为红黑树之后查询效率直接提高到了 O(logn)。
获取key的hash
该函数确保在每个位位置仅相差常数倍的哈希代码具有有界的冲突数（在默认负载因子下约为8）。
static int hash(int h) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
hash(int h)方法根据key 的hashCode 重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash 冲突。
相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。我们可以看到在HashMap 中要找到某个元素，需要根据key 的hash 值来求得对应数组中的位置。如何计算这个位置就是hash 算法。
② 存放数据
对于put方法的分析如下：
- ①如果定位到的数组位置没有元素 就直接插入。
- ②如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的key比较，如果key相同就直接覆盖，key不同就采用头插法插入元素。
public V put(K key, V value)
// HashMap 允许存放null 键和null 值。
// 当key 为null 时，调用putForNullKey 方法，将value 放置在数组第一个位置。
if (key == null)
return putForNullKey(value);
//获取key的hash值
int hash = hash(key);
//搜索指定hash 值在对应table 中的索引。
int i = indexFor(hash, table.length);
//如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 从table[i]先遍历
Object k;
//如果hash和key相同，则直接覆盖并返回旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果i 索引处的Entry 为null，表明此处还没有Entry。
//将key、value 添加到i 索引处。
addEntry(hash, key, value, i);
return null;
}
addEntry(hash, key, value, i)方法根据计算出的hash 值，将key-value 对放在数组table的 bucketIndex 索引处。并将该位置的原先结点作为新结点的next，即头插法。
//JDK1.7.0_17中
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果 Map 中的 key-value 对的数量超过了阈值 并且索引位置不为null
if ((size >= threshold) && (null != table[bucketIndex])) {
// 把 table 对象的长度扩充到原来的2 倍。
resize(2 * table.length);
//计算key的hash
hash = (null != key) ? hash(key) : 0;
//重新获取索引位置
bucketIndex = indexFor(hash, table.length);
}
//创建并插入结点-头插法
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 总数量+1
size++;
}
