HashMap 工作原理
2017-05-21 本文已影响6人
忽忽_
1.概述
学习本文你可以了解到：
- HashMap 是什么样的内部结构？有什么特点？
- 他的工作原理是什么样？
- equlas() 和 hashCode() 方法都有什么作用？
- 默认常量的定义有什么意义？
2.重要参数介绍
在构造参数中，一个是桶的容量，一个是加载因子。
/**
* 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;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
阈值常量
/**
* 默认的初始容量 - 必须是2的幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 容量最大值，分配数组最大长度，超过这个长度在保存就只能保存在链表中了。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认加载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表和红黑树转换的阈值
* 该值必须大于2，并且应该至少为8，
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 当执行resize操作时，当桶中bin的数量少于UNTREEIFY_THRESHOLD时使用链表来代替树。默认值是6
* 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个进行创建树的时候，如果当前桶的数量小于64，则进行扩容重新分配 hash 值
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
3.算法介绍
hash 值的计算方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
index 算法
// n = table.length
int index = (n - 1) & hash
为什么要有HashMap的hash()方法，难道不能直接使用KV中K原有的hash值吗？在HashMap的put、get操作时为什么不能直接使用K中原有的hash值。
从上面的代码可以看到key的hash值的计算方法。key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）
为什么要这么干呢？这个与HashMap中table索引的计算有关。因为，table的长度都是2的幂，因此index仅与hash值的低n位有关，hash值的高位都被与操作置为0了。
假设table.length=2^4=16。
hash 计算
0000 0000 0000 0000 0000 0000 00000 1000 = 8
0000 0000 0000 0000 0000 0000 00000 0000 = 0 位移16
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1000 = 8 异或运算结果
0000 0000 0000 0001 0000 0000 00000 1000 = 65544
0000 0000 0000 0000 0000 0000 00000 0001 = 1 位移16
------------------------------------------------------------
0000 0000 0000 0001 0000 0000 00000 1001 = 65545 异或运算结果
index 计算
0000 0000 0000 0000 0000 0000 00000 1000 = 8 hash 值
0000 0000 0000 0000 0000 0000 00000 1111 = 15 (16-1)数组长度-1
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1000 = 8 与运算结果
# 在没有 进行hash 运算的情况下，和上面的8的索引值结果一样，发生了碰撞
0000 0000 0000 0001 0000 0000 00000 1000 = 65544 hash 值
0000 0000 0000 0000 0000 0000 00000 1111 = 15 (16-1)数组长度-1
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1000 = 8 与运算结果
# 有过 hash 运算，因为高16位和低16位异或过产生的 hash 结果发生了变化，这样就避免的高位的 hash 碰撞
0000 0000 0000 0001 0000 0000 00000 1001 = 65545 hash 值
0000 0000 0000 0000 0000 0000 00000 1111 = 15 (16-1)数组长度-1
------------------------------------------------------------
0000 0000 0000 0000 0000 0000 00000 1001 = 9 与运算结果
上面的第一个示例，我们拿 8的 hash 计算的第一个结果来计算索引值，因为 hashCode 和 hash 的结果一致，我们就直接拿来和 length-1 来计算索引值为8。
第二和第三个示例我们分别拿了 65544的hashCode和 hash 值做了索引计算，结果却不一样。
由上可以看到，只有hash值的低4位参与了运算。
这样做很容易产生碰撞。设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
4.方法介绍
数组
transient Node<K,V>[] table;
链表结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // hash 值
final K key; // key 值
V value; // 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;
}
}
红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左边节点
TreeNode<K,V> right; // 右边节点
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 颜色，root 节点为黑色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
TreeNode继承了LinkedHashMap.Entry<K,V>，然而LinkedHashMap.Entry<K,V>又继承了HashMap.Node<K,V>，所以所数组中存储的结构都可以使用HashMap.Node。
红黑树是一种特殊的二叉树，主要用它存储有序的数据，提供高效的数据检索，时间复杂度为O(lgn)，每个节点都有一个标识位表示颜色，红色或黑色，有如下5种特性：
- 每个节点要么红色，要么是黑色；
- 根节点一定是黑色的；
- 每个空叶子节点必须是黑色的；
- 如果一个节点是红色的，那么它的子节点必须是黑色的；
- 从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点；
红黑树
初始化
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 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;
}
put 方法逻辑：
- 对 key 的 hashCode 重新计算 hash，然后计算出 index
- 若 table 为空，调用 resize 初始化
- 如果没有碰撞直接放到桶中，如果有碰撞了key 相等就覆盖 value，不相等就添加到链表尾端
- 如果链表长度大于8时转换为红黑树结构（大于等于TREEIFY_THRESHOLD时）
- 如果bucket满了(超过load factor*current capacity)，就要resize。
public V put(K key, V value) {
// 获取 key 的 hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断 table 是否为 null 或者为空，重置大小
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 获取 hash 的索引和对应的值，如果为 null 创建一个 Node 对象放到对应索引的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 判断当前索引的 key 是否和 put 的 key 相等，如果相等就把值覆盖老的值（这一步可以看出 hashmap 的 key 唯一性）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 后边用于统一设置返回值和覆盖相同 key 的值
e = p;
else if (p instanceof TreeNode)
// 如果当前节点是红黑树，直接调用红黑树的 put 方法（此方法后面会详细讲解）
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 创建 Node 对象放置在链表的尾端
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 添加节点后判断当前链表的长度是否大于等于8了，如果是就转换为红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 当在链表中找到有 key 相等的情况了直接跳出循环，后边用于统一设置返回值和覆盖相同 key 的值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 统一设置返回值和覆盖相同 key 的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 添加完后 size++ 操作，然后判断是否大于最大装载阈值，如果是就调整大小，调增大小为原长度的2倍。
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get 方法相对比较简单，先去匹配索引位置的key 相等就直接返回，然后在去检查是否为数，否则遍历 table 去查找
public V get(Object key) {
Node<K,V> e;
// 获取 key 的 hash
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;
// 如果 table 不为空且索引位置值不为 null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 索引位置的 key 和 key 若相等直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 如果是红黑树结构直接调用 getTreeNode 方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 遍历链表对比 key 是否相等，找到就返回，否则返回 null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
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 = 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
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;
}
}
}
}
}
return newTab;
}
treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
5.问题回答
1.hashmap 是个什么样的结构？
hashmap 内部采用的是 数据+链表/红黑树的方式存在。在 jdk1.8中加入了红黑树很好的解决了 hash 碰撞导致链表查询效率过低。查询效率：O + O(n) / O(logn)
6.运算符介绍
& 与运算：两个操作数中位都为1，结果才为1，否则结果为0
| 或预算：两个位只要有一个为1，那么结果就是1，否则就为0
^ 异或运算：两个操作数的位中，相同则结果为0，不同则结果为1
示例:
0001 0110 22
0000 0101 5
----------------
0001 0011 19
~ 非运算：如果位为0，结果是1，如果位为1，结果是0
<< 向左位移
>> 向右位移
>>> 向右无符号位移
