HashMap JDK1.8
一、数据结构
HashMap是高效的查询容器，底层的数据结构是数组 + 链表 + 红黑树。查询可以计算hash结果基于数组下标快速访问，链表用来解决hash冲突的问题，红黑树用于解决频繁的hash冲突导致查询效率低的问题。
HashMap数据结构.png
数据结构
- 数组：基于下标随机访问，保证了查询速度。
- 链表：高效的插入和删除，但在hashMap中主要是为了解决Hash冲突。
- 红黑树：logn（n指的是链上的数量）级别的查询效率，解决频繁的hash冲突导致链表过长，查询效率低下的问题。
HashMap的缺点
在HashMap中数组的空间的利用率较低，空间利用率和负载因子有关，默认的负载因子是0.75，实际空间利用率要低于0.75。我们都知道数组是一段连续的存储空间，数据量越大浪费的空间就越多。
二、哈希寻址
寻址流程
- 根据key调用hash算法求hash值。
- 根据返回的hash值与表长减一的值进行“与”运算。（hash & (n-1)）
- 把结果当作目标下标进行相应的操作。
hash算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
算法描述
key的哈希值异或哈希值的高16位，因为我们的Map实际上并没有存特别巨大数量的值，可以理解为低16位和高16位做异或操作。
算法目的
正常我们都会重写key的HashCode方法，尽可能的保证key的哈希值是均匀分布的以减少哈希冲突。但是在HashMap中，寻址是基于hash结果和当前的tableSize - 1进行与运算，得到目标位置。tableSize一般为2的幂次，tableSize - 1的结果为连续的0和连续的1，一般我们使用HashMap大小不会很大，低位的1比较少，和这样的结果进行与操作低位特征不够随机的话，冲突几率很大。
问题是，无论我们的hash算法结果再怎么均匀，实际上最后依旧只用后 logn 位的特征去进行与运算，碰撞依旧是比较严重。如果hash不均匀恰好计算得到的hash值的低位呈现规律性的重复，Hash碰撞就会极其严重，此时就体现出了“扰动函数”的价值。
图解
高低位特征提取
Hash值右移16位，正好是32位的一半，高16位和低16位异或，混合了原始hash值的高低位的特征，以此来加大低位的随机性。
三、HashMap的存取操作
1.链表数据结构
哈希表元素的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ... ...
}
描述
每一个结点都有一个hash、key、value和next，结点是构成单链表的数据结构。未满足树化条件前，结点都是上面代码显示的Node数据类型。
2.红黑树数据结构
哈希表树结点的数据结构
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;
// ... ...
}
描述
HashMap在1.8之后引入了红黑树的概念，红黑树是二叉搜索树的一种，常规的二叉搜索树只需要满足结点的值大于做孩子的值小于右孩子的值即可。但是红黑树不仅仅是这样，红黑树需要满足以下的性质。
红黑树的性质：（来自算法导论第三版 p174）
- 每个结点或是红色的，或是黑色的。
- 根结点是黑色的。
- 每个叶结点（NIL）是黑色的。
- 如果一个结点是红色的，则它的两个子结点都是黑色的。
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
传统二叉搜索树的缺点
传统的二叉搜索树最坏的情况下树的高度等于结点的数目，以至于查询数据达到了O(n)，最坏的查询情况和链表没啥区别。
AVL树
平衡二叉树是一种平衡了树高的结构，使得任意一个结点的左右子树高差值不超过1。可以解决上述的二叉搜索树的缺点，AVL树可以弥补传统的二叉搜索树的缺点，但是它又引来了新的问题，当数据量大了的时候维护AVL树性质的自旋操作会很影响插入性能。
数据结构小结
红黑树的是许多“平衡搜索树”中的一种，它是一种似平衡的状态，它可以保证在最坏的情况下基本动态集合的操作时间复杂度为O(logn)。
3.结点存入流程
put方法会先进行hash，然后调用putVal方法进行实际处理。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
putVal描述
- 如果当前表为空或长度为0，重新构建一个默认容量的容器。
- 如果哈希寻址到的下标的元素为空，创建一个Node放入。
- 非以上情况
i. 如果当前key等于待插入元素的key，hash值也相同，替换原值。
ii. 如果当前结点是treeNode，使用红黑树的putTreeVal方法插入结点。
iii. 否则就遍历当前链表依次比较key和hash，如果相同替换原值，不同就继续遍历，直到下一个结点是空的就插入。 插入会判断当前是否是第八个结点，是的话且表长等于64，链表就树化。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// 哈希表为空初始化
n = (tab = resize()).length;
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))))
// 键相同值替换，后面判断替换值
e = 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;
}
}
// 替换原值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// ... ...
4.取值流程
get方法会先hash然后getNode寻找值
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
getNode描述
- 根据hash与运算求得数组下标位置，并判断是否有值。
- 有值的话，则判断查询的key，是否等于first结点的key，等于则返回。
- 头结点不等于的话，判断是否是红黑树的结点，是红黑树的结点就走红黑树的查询逻辑。
- 不是红黑树的结点就遍历单链表查询。
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 &&
// 找hash值对应到数组中的元素下标，判断下标位置是否为空
(first = tab[(n - 1) & hash]) != null) {
// 判断头结点
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
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);
}
}
return null;
}
5.put和putIfAbsent()
put方法onlyIfAbsent传的是false
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
putIfAbsent方法onlyIfAbsent传的是true
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
putVal的onlyIfAbsent参数是干嘛的
// 键相同替换原值的逻辑
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果onlyIfAbsent是false则是替换原值的
// onlyIfAbsent是true则是不会替换原值的
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
onlyIfAbsent参数为false，则新值会替换原值并且返回原值。
onlyIfAbsent参数为true，则原值不变并且返回原值。
测试代码
public static void main(String[] args) {
Map<String,Object> map = new HashMap<>();
map.put("haha",123);
System.out.println(map.put("haha",456));
System.out.println(map.putIfAbsent("haha",789));
}
执行结果
123
456
Process finished with exit code 0
6.澄清HashMap链表的树化条件
条件1:当前待插入的结点是第8个结点。
条件1:putVal方法
当前count值要大于等于 TREEIFY_THRESHOLD(8) - 1，计数器从0开始计数，到7刚好是8个结点。所以和网上的一些博客描述的都一样，链表结点插入后，链表结点满足8个就要进行树化，但树化并非仅仅是这一个条件。
else {
// 遍历单链表，判断相同，直到找到空值
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 待插入结点已插入
p.next = newNode(hash, key, value, null);
// 树化条件1: 当前count值大于等于 8 - 1，当前待插入结点如果是第八个结点就树化。
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
条件2:表的长度大于或等于64
treeifyBin(tab, hash)方法
表的长度小于MIN_TREEIFY_CAPACITY(64)，就不进行树化操作，resize扩容即可。反之，表的长度大于或等于64，才可以进行链表树化的操作。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 表长度小于 MIN_TREEIFY_CAPACITY 64，此时扩容即可不需要进行树化操作。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 表长大于等于64，才需要进行树化操作
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);
}
}
7.为什么要重写hashCode和equals方法？
equals方法是比较两个对象是否相同的方法，Object基础实现是比较hashCode，也就是对象的地址。
我们自定义类型如果想当作HashMap的键是需要重写equals方法的，否则两个对象的属性值相同，但是却不是同一个对象，地址不相同导致最终结果不相等。如果作为键的对象没有重写equals，这肯定是有问题的。
hashCode方法，是唯一标识一个对象的方法，Object默认实现时返回对象的地址。
HashCode重写时需要注意以下几点：
- hashCode方法中不能包含equals方法中没有的字段。
- String和其它包装类型已有的hashCode可以直接调用。
- hash = 31 * hash + (field != null ? field.hashCode : 0)；可以应用于hashCode方法当中。因为任何数 n * 31都可以被JVM优化为 (n<<5)-n 这个表达式，移位和减法要比其它的操作快速的多。
《Effective Java》中提出了一种简单通用的hashCode算法：
- 初始化一个整型的变量，并为此变量富裕一个非零的常数值，如 int code = 13;
- 如果对象中有String或其它包装类型，则递归调用该属性的hashCode，如果属性为空则处理为0。
案例
@Override
public int hashCode() {
int hash = 13;
hash = hash * 31 + (name != null ? name.hashCode() : 0);
hash = hash * 31 + (location != null ? location.hashCode() : 0);
return hash;
}
四、HashMap小结
HashMap在1.8有了一些变化，多是查找相关的优化。这种数据结构在日常开发过程中太常用了，原理是一定要摸清楚的。懂得HashMap原理并没有让我在开发技能上有显著的提高，但是在数据结构转换使用上扩展了自身的一些想法。
