简单谈谈HashMap
- 2020 年 3 月 9 日
- 筆記
概述
面试Java基础，HashMap可以说是一个绕不过去的基础容器，哪怕其他容器都不问，HashMap也是不能不问的。
除了HashMap，还有HashTable跟ConcurrentHashMap，两个都是线程安全的哈希容器，但是HashTable是JDK1.0就有的容器，线程安全是通过synchronized关键字来实现的，而且锁住的是整个table对象，虽然线程安全，但是并发性能并不高。因此在JDK1.5里面并发大师Doug Lea操刀写了个ConcurrentHashMap，通过粒度更细的锁来实现更高的性能。
HashMap的历史
在不同版本的JDK中，HashMap是在不停优化的。
- 比如JDK1.6里面new HashMap时，开辟了内存空间，如果不使用，则浪费内存；JDK1.7里面改成了懒加载，new HashMap并没有开辟内存空间，节约了内存空间
- 1.8优化了hashCode算法：高16位异或（XOR）低16位 主要是为了增加扰动，减少碰撞几率
- 1.8里面优化了hash碰撞较多情况下的性能问题（链表长度限制为8，过长时请将链表转换为TreeNode(红黑树)）
配置常量
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; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64;HashMap容器初始化的容量为16，默认负载因子为0.75，树化阈值为8，反树化阈值为6。
put流程
- 对key的hashCode()做hash运算，计算index；
- 如果没碰撞直接放到bucket里；
- 如果碰撞了，以链表的形式存在buckets后；
- 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)；
- 如果节点已经存在就替换old value(保证key的唯一性)
- 如果bucket满了(超过load factor*current capacity)，就要resize。
get流程
- 对key的hashCode()做hash运算，计算index;
- 如果在bucket里的第一个节点里直接命中，则直接返回；
- 如果有冲突，则通过key.equals(k)去查找对应的Entry；
- 若为树，则在树中通过key.equals(k)查找，O(logn)；
- 若为链表，则在链表中通过key.equals(k)查找，O(n)。
Hash算法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }HashMap中可以存放key为null的值，放在首位。
将高16位与低16位异或运算，通过这样一个扰动函数，减小了hash冲突的概率。然后再通过这个hash值与数组的长度进行取模运算，决定这个键值对该放入哪个bin中。
(n – 1) & hash
这个算法是当bin为bull的时候，直接将Node放入table中；当扩容的时候，存在两种情况，要么放在原来的位置，要么往后移动原来的容量大小的位置，这时候使用的是下面这个算法：
e.hash & oldCap
如果得到的结果为零，则在原位置；反之，则将其向高位移动oldCap大小的位置。
拓展
String的Hash算法如下：
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; }String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。
哈希计算公式可以计为s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
那为什么以31为质数呢?
主要是因为31是一个奇质数，所以31*i=32*i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。
