HashMap原理&技术知识整理
HashMap涉及的技术点非常多，典型的数据结构和算法有机结合，JDK对HashMap优化变化中不断权衡时间复杂和空间复杂度。
一. 存储结构
1.JDK1.8之前 HashMap = 数组(O(1)）+ 单向链表（O(n)） 2.JDK1.8之后 HashMap = 数组(O(1)）+ 单向链表（O(n)）+ 红黑树(O(log n)
关于结构的几个关键数字： 1.默认初始化数组容量大小是16。 2.数组扩容刚好是2的次幂。 3.默认的加载因子是0.75。 4.链表长度超过8时将链表转化成红黑树结构。 5.红黑树节点数减少到6的时候退化成链表。 以上几个数字关系，又为什么是上边的几个数字接下来一个个分析。
二. 操作原理
1. put储存流程
①计算桶的位置，根据key的hashcode求出hash值，位置index = hash%length。
②判断是否达到扩容条件，threshold=DEFAULT_INITIAL_CAPACITY * loadFactor（16*0.75=12）大于这个阀门值就需要扩容，否则下一步。
③判断桶位置是否为空，如果为空直接在数据插入数据。如果不为空，下一步。
④判断是链表还是红黑树，链表是否到达转化红黑树，当前链表节点数<=8，插入节点；如果是红黑树插入节点，否则下一步。
⑤链表转化成红黑树，插入节点。
⑥插入节点后计算当前size是否需要扩容，如果大于阀门值需要扩容resize。
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
以上是JDK1.8的HashMap的get调用关键方法源码。
2. get获取过程
①计算桶的位置，根据key的hashcode求出hash值，位置index = hash%length。
②无论是数值，链表还是红黑树，for循环判断hash值冲突就比对key是否相等，相等就返回对应的value。
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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) {
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;
}
以上是JDK1.8的HashMap的put调用关键方法源码。
三. 数据结构和算法思考
1.为什么选择数组和链表结构？
①数组内存连续块分配，效率体现查询更快。HashMap中用作查找数组桶的位置，利用元素的key的hash值对数组长度取模得到。
②链表效率体现增加和删除。HashMap中链表是用来解决hash冲突，增删空间消耗平衡。
扩展：为什么不是ArrayList而是使用Node<K,V>[] tab？因为ArrayList的扩容机制是1.5倍扩容，而HashMap扩容是2的次幂。
2.为什么扩容是2次幂，根据key的hashcode再求hash值？
①key的hash值计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
代码意思是hash = hashcode的高16位异化低十六位，而不是直接hashcode。
②计算桶的位置代码
index = (n - 1) & hash
思想： 一是，为了减少hash冲突使用hash%length计算，求模计算保证了得到的结果一定在0-length范围之内。
二是，为了提高运算速度，模运算比不上位运算，当n是2的次幂才满足hash%length == （n-1）&hash。
确定公式中（n-1）符合最优等式，剩下考虑hash值的最优，hash值这个因子考虑影响结果尽可能不冲突。
因为计算速度体现在位运算上，条件n是2的次幂，那么n-1的换算成二进制前边都是连续的0，后边都是连续的1,。比如n=16，则n-1=15，15的二进制1111。hash & 1111 = 只要关注的hash的二进制的最后四位数进行&运算。
如上图，最终会与15的二进制进行1111四位运算，如果与key.hashcode进行与运算的话，只要key的hashcode最后四位为0000前边无论是什么都没关系，这样出现相同值的概率高很多。所以，引入hashcode先高低16位进行异或运算，减少hash冲突。
扩展： hashcode与equals相等判断对比： 两个key的hashcode相等，key不一定equals。 两个key的equals，hashcode一定相等。
3.为什么加载因子为0.75，链表长度大于8转成红黑树？
思想： 上边问题不是两个独立问题而是相互相关，目的尽量减少冲突前提提高空间利用率和减少查询成本的折中。
加载因子决定了HashMap的扩容的阀门值，如果桶是16，那么扩容值16* 0.75=12，也就是12的时候就要考虑扩容，还有4个没有被利用到，牺牲的空间。如果加载因子是1，空间利用率高，但是查询速度变慢。
原理： 权衡依据是以上情况符合泊松分布（一种统计与概率学里常见到的离散概率分布，适合于描述单位时间（或空间）内随机事件发生的次数），用0.75作为加载因子，每个碰撞位置的链表长度超过８个概率非常低，少于千万分之一。
源码说明：
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
扩展： 为什么不一开始选择红黑树？
红黑树近乎于平衡二叉树，结构适合均匀分布节点，减少树的深度像链表长度情况。原因主要是插入效率上，红黑树增加节点很可能需要进行左旋，右旋，着色操作，这些时间效率并没有链表形式高。
4.HashMap的key选择
1）选择不可变的对象，比如字符串或int类型。 2）如果要用一个自定义实体类作为key： ①类添加final修饰符，保证类不被继承。 ②保证所有成员变量必须私有，并且加上final修饰。 ③不提供改变成员变量的方法，包括setter。 ④通过构造器初始化所有成员，进行深拷贝(deep copy)。
5.String类中的hashcode计算
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
哈希计算公式：s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
四. 横向扩展
1.HashMap出现线程问题
①多线程扩容，引起的死循环问题（jdk1.8中，死循环问题已经解决）。 ②多线程put的时候可能导致元素丢失 ③put非null元素后get出来的却是null
2.使用线程安全Map
①HashMap并不是线程安全，要实现线程安全可以用Collections.synchronizedMap(m)获取一个线程安全的HashMap。 ②CurrentHashMap和HashTable是线程安全的。CurrentHashMap使用分段锁技术，要操作节点先获取段锁，在修改节点。
3.Android提倡使用ArrayMap
①ArrayMap数据结构是两个数组，一个存放hash值，另一个存放key和value。 ②根据key的hash值利用二分查找在hash数组中找出index。 ③根据index在key-value数组中对应位置查找，如果不相等认为冲突了，会以key为中心，分别上下展开，逐一查找。 优势，数据量少时（少于1000）相比HashMap更节省内存。劣势，删除和插入时效率要比HashMap要低。