HashMap#
一、基础概念#
在 JDK8 及以后的版本中，HashMap 引入了红黑树结构，其底层的数据结构变成了由
数组+链表变成数组+链表和数组+红黑树
HashMap 整体结构:
JDK1.8 后 HashMap 的红黑树结构
红黑树的转换#
参考: https://juejin.im/entry/5839ad0661ff4b007ec7cc7a
几个参数:
//一个桶的树化阈值, 当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
static final int TREEIFY_THRESHOLD = 8;
//一个树的链表还原阈值, 当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的最小树形化容量, 当哈希表中的容量大于这个值时，表中的桶才能进行树形化,否则桶内元素太多时会扩容，而不是树形化
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
添加元素时，默认如果桶中链表个数超过 7，链表会尝试转换成红黑树：
// 如果HashMap容量小于64，会选择扩容而不是直接将其转变成红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
}
// TREEIFY_THRESHOLD 默认为8
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
当调用 risize 方法 () 扩容时，如果当前桶中元素结构是红黑树，并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD （默认为 6），就会调用 split () 方法把桶中的树形结构缩小或者直接还原（切分）为链表结构:
if (lc <= UNTREEIFY_THRESHOLD) {
tab[index] = loHead.untreeify(map);
}
二、HashMap 的默认参数理解#
为什么 HashMap 的 Entry 数组长度默认为 16 呢？为什么数组长度一定要是 2 的 n 次幂呢？#
首先看 HashMap 计算 hashcode 的方法获取存储的位置方法：
static int indexFor(int h, int length) {
return h & (length-1);
}
长度 16 或者其他 2 的幂，length - 1 的值是所有二进制位全为 1, 这种情况下，index 的结果等同于 hashcode 后几位的值，只要输入的 hashcode 本身分布均匀，hash 算法的结果就是均匀的
所以：HashMap 的默认长度为 16 和规定数组长度为 2 的幂，是为了降低 hash 碰撞的几率
HashMap 扩容限制的负载因子为什么是 0.75？#
HashMap 中扩容方式是通过新建一个长度为之前数组 2 倍的新的数组，然后将当前的 Entry 数组中的元素全部传输过去，扩容后的新数组长度为之前的 2 倍，所以扩容相对来说是个耗资源的操作
扩容的触发条件是: 临界值 = 数组默认的长度 x 负载因子
- 如果负载因子为 0.5 甚至更低的可能的话，最后得到的临时临界值明显会很小，这样的情况就会造成分配的内存的浪费，存在多余的没用的内存空间，也不满足了哈希表均匀分布的情况
- 如果负载因子达到了 1 的情况，也就是 Entry 数组存满了才发生扩容，这样会出现大量的哈希冲突的情况，出现链表过长，影响 get 查询数据的效率
- 因此选择了 0.5~1 的折中数也就是 0.75，均衡解决了上面出现的情况
三、HashMap 的基本操作#
get 操作#
/**
* 通过 hash(key) 方法计算 key 的哈希值
* 通过 getNode() 方法获取 node
* 如果 node 为 null, 返回null, 否则返回 node.value
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* getNode 可以分为以下几步:
* 1. 如果哈希表为空，或 key 对应的桶为空，返回 null
* 2. 不为空的话，如果桶中第一个节点就和指定参数hash和key匹配上了，直接返回这个节点
* 3. 第一个节点没匹配上的话进行后续查找:
* 3.1、如果当前的桶采用红黑树，调用红黑树的 getTreeNode 去获取节点值
* 3.2、 如果为链表结构，直接遍历链表查询查找
* 4. 找到节点返回 value, 否则返回 null
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果哈希表和 key 对应的桶不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 优化点 1: 减少不必要的查询
// 如果桶中第一个节点就和指定参数hash和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);
// 如果为链表结构，直接遍历链表查询查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
put 操作#
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* putVal方法可以分为以下几个步骤
* 1. 如果哈希表为空，调用 resize 方法创建
* 2. 如果指定 key 值不冲突，即不存在哈希冲突的情况直接插入键值对
* 3. 如果有冲突，找到这个冲突节点
* 3.1 如果第一个节点就匹配了，记录起来否则继续查找下去
* 3.2 如果当前为红黑树结构，调用 putTreeVal 方法插入
* 3.3 如果为链表结构，循环遍历链表查找, 找到最后还没有的话利用尾插法插入节点，找到了的话记录这个节点，然后退出循环
* 4. 找到了冲突节点的话，判断 onlyIfAbsent是否为 true, 即代表是否允许修改旧值
* 5. HashMap修改次数modCount 和 容量大小size 自增运算 + 1, 如果 size > threshold, 即达到了 临界值，进行扩容
*
* @param hash 指定 key 的 hash 值
* @param key 指定 key
* @param value 需要插入的 value 值
* @param e, 表示不允许替换旧值
* @param evict 代表 HashMap 是否处于创建模式
* @return 指定 key 存在的情况下，如果替换了旧值，返回这个值，否则返回 null，当然也有可能 value 值就是 null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果哈希表为空，调用 resize 方法创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果指定 key 值不冲突，即不存在哈希冲突的情况直接插入键值对
// (n - 1) & hash 等价于 hash % n，不过位运算更快
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;
// 如果当前为红黑树结构，调用 putTreeVal 方法插入
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;
// 判断 onlyIfAbsent是否为 true, 即代表是否允许修改旧值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 判断 size 是否达到了临界值需要进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容操作#
/**
* 对 table 进行初始化或者扩容，扩容的话每次都是容量翻倍，二进制计算后，原来的节点要么就在原来的位置，要么就被分配到 “原位置 + 旧容量” 这个位置
* resize 的步骤总结:
* 1. 计算扩容后的容量，临界值
* 2. 更新HashMap的临界值
* 3. 根据计算得出的扩容容量，创建新数组，然后将 HashMap 的 table 引用指向新数组
* 4. 将旧数组的元素复制到 table 中
*/
final Node<K,V>[] resize() {
// 新建一个 oldtab 数组保存扩容前的数组 table
Node<K,V>[] oldTab = table;
// 获取旧数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧数组的临界值
int oldThr = threshold;
int newCap, newThr = 0;
// 如果旧数组容量大于0
if (oldCap > 0) {
// 如果旧数组容量超过最大值, 将其临界值设为整型最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果旧数组容量大于默认容量(16)且翻倍后得到的新数组容量小于最大值，将旧数组的临界值也翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果旧容量 <= 0, 而且临界值 > 0
else if (oldThr > 0) // initial capacity was placed in threshold
// 将新数组容量设为旧数组的临界值
newCap = oldThr;
// 如果旧容量 <= 0, 而且临界值 <= 0
else {
// 新容量设为默认值(16)
newCap = DEFAULT_INITIAL_CAPACITY;
// 新临界值设为默认容量 * 默认负载因子 (16 * 0.75) = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 在上面的条件判断中，只有 oldThr > 0 时， newThr == 0
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;
// 用 e 记录下旧节点的值
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果旧 bucket 的存储冲突 hash值的结构为 红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 如果旧 bucket 的存储冲突 hash值的结构为 链表结构
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// java 7 是在 while 循环里面，单个计算好数组索引位置后，单个的插入数组中，在多线程情况下，会有成环问题
// java 8 是等链表整个 while 循环结束后，才给数组赋值，所以多线程情况下，也不会成环
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;
}
四、Java 中 HashMap 的 key 值要是为类对象则该类需要满足什么条件#
一般使用 String、Integer 这样的包装类作为 key 键，原因是:
- 这种包装类型为 final 类型，具有不可更改性，因此保证了 hash 值的不可更改性和计算准确性
- 内部重写了 equals (), hashcode () 方法
因此若 HashMap 中的 key 为类对象的话，需要重写 hashcode 和 equals () 方法
五、HashMap 是怎么解决哈希冲突的？#
解决哈希冲突的方法#
开放定址法#
从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法，需要的表长度要大于等于所需要存放的元素
包括以下几种方法
- 线性探查法
从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止 - 平方探查法
发生冲突时，用发生冲突的单元 d [i], 加上 1²、 2² 等。即 d [i] + 1²，d [i] + 2², d [i] + 3²... 直到找到空闲单元 - 双散列函数探查法
链地址法 (拉链法)#
链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第 i 个单元中，查找、插入和删除主要在同义词链表中进行
再哈希法#
就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 ... k;
当 H1 = RH1 (key) 发生冲突时，再用 H2 = RH2 (key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间
六、HashMap 在 JDK1.7 和 JDK1.8 中有哪些不同#
-
1.8 加入了 红黑树，遍历查询时间复杂度由原来链表的 O (n) 变为 O (logn)
-
在插入数据的时候，1.7 基于头插法，这会产生逆序且环形链表死循环问题，而 1.8 基于尾插法避免了这个问题，详见: jdk1.7HashMap 链表成环的原因和 jdk1.8 的解决方案
-
扩容后数据存储位置的计算方式不一样
- JDK 1.7 使用 hashCode () + 4 次位运算 + 5 次异或运算（9 次扰动）
static final int hash(int h) {
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}```2. JDK 1.8 简化了扰动函数，只做了 2 次扰动 = 1 次位运算 + 1 次异或运算
Java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制 }
七、HashMap 为什么不直接使用 hashCode () 处理后的哈希值直接作为 table 的下标？#
不直接使用 hashCode (), 而选择扰动函数处理, 使得根据 key 生成的哈希码（hash 值）分布更加均匀、更具备随机性，避免出现 hash 值冲突
八、HashMap、LinkHashMap 和 TreeMap 的差别#
- 遍历 HashMap 时，其输出是无序的
- LinkedHashMap 继承自 HashMap，具有高效性，同时在 HashMap 的基础上，又在内部增加了一个链表，用以存放元素的顺序
- TreeMap 实现了 SortedMap 接口，它可以对元素进行排序
- LinkedHashMap 是基于元素进入集合的顺序或者被访问的先后顺序排序，TreeMap 则是基于元素的固有顺序 (由 Comparator 或者 Comparable 确定)