HashMap的优化与实践
文章速读
- HashMap通过计算哈希实现数据的索引
- 当碰撞达到8时，将链表转为红黑树(一种对称的二叉查找树)
- HashMap进行rehash时性能较差，因此需要设计一个好的容量，或者使用Redis的渐进式rehash
HashMap的复杂度
如图是ArrayList/LinkedList/HashMap三个数据结构的复杂度对比，可以看出HashMap整体上性能都非常不错，但是不稳定，为O(N/Buckets)，N就是以数组中没有发生碰撞的元素，Buckets是因碰撞产生的链表。
| 获取 | 查找 | 添加/删除 | 空间 | ||
|---|---|---|---|---|---|
| ArrayList | O(1) | O(1) | O(N) | O(N) | |
| LinkedList | O(N) | O(N) | O(1) | O(N) | |
| HashMap | O(N/Bucket_size) | O(N/Bucket_size) | O(N/Bucket_size) | O(N) |
注：发生碰撞实际上是非常稀少的，所以N/Bucket_size约等于1
HashMap是对Array与Link的折衷处理，Array与Link可以说是两个速度方向的极端，Array注重于数据的获取，而处理修改（添加/删除）的效率非常低；Link由于是每个对象都保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。
复杂度是如何考察的？
对于数据结构，在时间上我们需要考察Acessing ,Search, Deletion/Insertion的平均与最差的复杂度。在空间上，我们要考虑维护这个数据结构所占用的内存空间。
常见的数据结构与排序的复杂度都在这里
HashMap的实现
本文以JDK8的API实现进行分析
1. 什么是hash，什么是碰撞？
-
Hash：是一种信息摘要算法，一般用于验证完整性，它还叫做哈希，或者散列，但是它不是加密。我们平时使用的MD5,SHA1,SSL中的公私钥验证都属于Hash算法，通过输入key进行Hash计算，就可以获取key的HashCode()，比如我们通过校验MD5来验证文件的完整性。
-
碰撞：好的Hash算法可以出计算几乎出独一无二的HashCode，如果出现了重复的hashCode，就称作碰撞;
就算是MD5这样优秀的算法也会发生碰撞，即两个不同的key也有可能生成相同的MD5。
2. HashMap中是如何实现写入与读取的？
HashMap实现了Map接口，保存着K-V这样的集合。我们以put操作为例
2.1. 对key进行Hash计算
在JDK8中，由于使用了红黑树来处理大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了
static final int hash(Object key) {
int h;
//计算hashCode，并无符号移动到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
举个例子: 363771819^(363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)
这样做可以实现了高地位更加均匀地混到一起，详见这里
下面给出几个常用的哈希码(hashCode)的算法。
- Object类的hashCode. 返回对象的经过处理后的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
- String类的hashCode. 根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串的内容相同，返回的哈希码也相同。
- Integer等包装类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100),i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。
- int，char这样的基础类，它们不需要hashCode，如果需要存储时，将进行自动装箱操作，计算方法同上。
2.2. 获取到当前的位置
计算了Hash，我们现在要把它插入数组中了
i = (tab.length - 1) & hash；
通过位运算，确定了当前的位置，因为HashMap数组的大小总是2^n，所以实际的运算就是 (0xfff...ff) & hash ，这里的tab.length-1相当于一个mask，滤掉了大于当前长度位的hash，使每个i都能插入到数组中。
2.3. 生成包装类
这个对象是一个包装类，Node<K,V>，内部有key,value,hash还有next，可以看出来它是一个链表。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//getter and setter .etc.
}
2.4. 插入包装类到数组
(1). 如果输入当前的位置是空的，就插进去，如图，左为插入前，右为插入后
0 0
| |
1 -> null 1 - > null
| |
2 -> null 2 - > null
| |
..-> null ..- > null
| |
i -> null i - > new node
| |
n -> null n - > null
(2). 如果当前位置已经有了node，且它们发生了碰撞，则新的放到前面，旧的放到后面，这叫做链地址法处理冲突。
0 0
| |
1 -> null 1 - > null
| |
2 -> null 2 - > null
| |
..-> null ..- > null
| |
i -> old i - > new - > old
| |
n -> null n - > null
我们可以发现，失败的hashCode算法会导致HashMap的性能由数组下降为链表，所以想要避免发生碰撞，就要提高hashCode结果的均匀性。当然，在JDK8中，采用了红黑二叉树进行了处理，这个我们后面详细介绍。
>
什么是Hash攻击?
通过请求大量key不同，但是hashCode相同的数据，让HashMap不断发生碰撞，硬生生的变成了SingleLinkedList
0 | 1 -> a ->b -> c -> d(撞！撞！撞！复杂度由O(1)变成了O(N)) | 2 -> null(本应该均匀分布，这里却是空的) | 3 -> null | 4 -> null这样put/get性能就从O(1)变成了O(N)，CPU负载呈直线上升，形成了放大版DDOS的效果，这种方式就叫做hash攻击。在Java8中通过使用TreeMap，提升了处理性能，可以一定程度的防御Hash攻击。
3. 扩容
如果当表中的75%已经被占用，即视为需要扩容了
(threshold = capacity * load factor ) < size
它主要有两个步骤：
1. 容量加倍
左移1位，就是扩大到两倍，用位运算取代了乘法运算
newCap = oldCap << 1;
newThr = oldThr << 1;
2. 遍历计算Hash
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果发现当前有Bucket
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果这里没有碰撞
if (e.next == null)
//重新计算Hash，分配位置
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;
}
}
}
}
由此可以看出扩容需要遍历并重新赋值，成本非常高，所以选择一个好的初始容量非常重要。
如何提升性能？
-
解决扩容损失：如果知道大致需要的容量，把初始容量设置好以解决扩容损失；
比如我现在有1000个数据，需要 1000/0.75 = 1333 个坑位，又 1024 < 1333 < 2048，所以最好使用2048作为初始容量。 -
解决碰撞损失：使用高效的HashCode与loadFactor，这个...由于JDK8的高性能出现，这儿问题也不大了。
-
解决数据结构选择的错误：在大型的数据与搜索中考虑使用别的结构比如TreeMap，这个就是知识积累了。一般需要key排序时，建议使用TreeMap，本文暂不讨论；
HashMap与HashTable的主要区别
在很多的Java基础书上都已经说过了，他们的主要区别其实就是Table全局加了线程同步保护
- HashTable线程更加安全，代价就是因为它粗暴的添加了this同步锁，所以会有性能损失。
- 其实有更好的concurrentHashMap可以替代HashTable，它采用了CAS实现了数组元素的插入
JDK8中HashMap的新特性
如果某个桶中的链表记录过大的话（当前是TREEIFY_THRESHOLD = 8），就会把这个链动态变成红黑二叉树，使查询最差复杂度由O(N)变成了O(logN)。
//e 为临时变量，p为当前的链
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;
}
JDK8在其他地方也有提升，更多的可以看这里。
HashMap的装箱空间效率
在笔试题中，一般“内存限制”是不考虑装箱的，而在现实中HashMap空间效率之低，你却不一定知道。
比如定义了一个 HashMap<Long,Long>
1. Long的装箱
在对象头中，加入额外的指针8Bype，加入8Bype的MarkWord(hashcode与锁信息)，这里就是16Byte
也就是说，long在装箱后，效率为 8/24 = 1/3
2. Map.Entry的装箱
字段空间: hash(4) + padding(4) ＋ next(8) = 16Byte，这里的padding是字节对齐
对象头: 16Byte，指针+MarkWord
也就是说，维护一个Entry需要32Byte的空间
static class Node<K,V> implements Map.Entry<K,V>
{
final int hash;
final K key;
V value;
Node<K,V> next;
}
3. 总效率
8/(24 + 32) = 1/7
计算结果可能有差异，本文主要在强调装箱过程造成的损失
如果你想挑战OJ的TOP1，必须通过数组等手段实现Map