一、哈希表
1.什么是哈希表
哈希表又叫散列表，是一种根据设定的映射函数f(key)将一组关键字映射到一个有限且连续的地址区间上，并以关键字在地址区间中的“像”作为元素在表中的存储位置的一种数据结构。这个映射过程称为哈希造表或者散列，这个映射函数f(key)即为哈希函数也叫散列函数，通过哈希函数得到的存储位置称为哈希地址或散列地址
简单来说哈希表就是通过一个函数 f(key) 将一组元素散列存储到一个数组中的数据结构
2.什么是哈希冲突
对于不同的关键字，可能得到同一个哈希地址，即key1≠key2,而 f(key1)=f(key2)，对于这种现象我们称之为哈希冲突，也叫哈希碰撞
当要散列存储的元素大于数组的长度时必然会出现哈希冲突 鸽笼
3.如何处理哈希冲突
- 开放定址法，当发生哈希冲突时继续以某种方式再次寻找哈希表中的其他位置直到找到一个空的位置，如线程探测再散列和二次探测再散列
- 再哈希法，选择多个哈希函数，当发生哈希冲突时计算另一个哈希函数直到没有冲突为止
- 建立公共溢出区，维护一个溢出表当发生哈希冲突时把元素放入溢出表
- 链地址法，当发生哈希冲突时将冲突的元素以链表的方式存储 HashMap 就是使用的这种方式
4.链地址法的缺点
极端情况下搜索元素都在一个位置上，哈希表退化成了链表，这种情况可以把链表转话为红黑树（Java 1.8 HashMap 的优化点）
二、equals 与 hashCode 函数的关系
equals 与 hashCode 都是用来比较对象相等，但是重写 equals 的逻辑一般比较复杂效率比较低，而 hashCode 只需要比较一个 hash 值就可以，但是 hashCode 函数并不完全可靠，有时候不同对象的 hash 值也会相同。总结一下就是当两个对象 equals 相等时 hashCode 一定相等 equasl 绝对可靠，当两个对象 hashCode 相等时 equals 不一定相等 hashCode 不一定可靠。所以在一些哈希容器中会先用 hashCode 去对比，如果 hashCode 不相等则两个对象肯定不相等，如果 hashCode 相等再去比较 equals 是否相等 equals 也相等的话才认为是同一个对象，这样既提高了效率又保证了正确性。
三、HashMap
对于 HashMap 源码的分析基于 Java 1.8
1. 负载因子
HashMap 和 HashSet 都具有允许直接传入负载因子的构造器，表示当负载情况达到负载因子的水平时容器将自动增加其容量，实现方式是使容量大致加倍，并重新将现有对象分布到新的数组中（这也称为再散列）。HashMap 的默认负载因子时 0.75 这在时间和空间上达到了平衡，更高的负载因子可以节省空间但是增加了查询时间（查找是我们在大多数时间里所做的动作，包括 get 和 put），如果知道将要在 HashMap 中存储多少元素可以创建一个合适容量的 HashMap 避免再散列的开销
2. 计算 key 应存储在数组中的位置
- 首先调用 key 的 hashCode 函数
- 将第一步计算的值右移 16 位再与自己进行异或运算，结果就是高 16 结果不变低 16 位与高 16 位进行异或运算，其实就是对低 16 位进行再次处理，这一步称为扰动处理（扰动函数）。因为通常情况下一步与运算的时候都只有后面的低位参与运算，扰动处理是为了高位也参与运算。
- 用第二步计算的值与数组长度 -1 进行与运算得到的结果就是 key 在数组中应该存储的位置
所有的处理都是为了尽量保证均匀分布
3. 容量是 2 的幂的作用
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap 传入容量的构造函数里会调用上面的函数保证容器的容量是 2 的幂次方，作用有两个
- 当 x = 2 ^ n（n 为自然数）时，a % x = a & (x - 1) 为了使用位运算代替取模运算提高效率
- 如果容量是奇数那么 - 1 就是偶数转为二进制则最后一位为 0 与其他值进行与运算最后一个也肯定是 0 则所有 key 都会映射到数组的偶数下标上则丢失了一半的存储空间，容量为偶数 -1 为奇数转化为二进制最后一位为 1 则与其他值与运算的结果取决于其他值，尽量保证了均匀分布
与运算说的就是 ‘计算 key 应存储在数组中的位置’ 中的第三步
4. put
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)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
5. resize
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
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;
}
}
}
}
}
return newTab;
}
由于数组扩容是扩充到原数组的 2 倍所以再次计算元素的位置时相当于数组长度的部分高位多一个 1 相应的 hash 值的部分也要在高位多出一位参与计算，因为数组长度部分是 1 所以计算结果取决于 hash 值的即将参与计算的高位，所以如果 hash 值即将参与计算的高位是 0 则计算结果与扩容之前的计算结果相同还在原来的位置，如果 hash 值即将参与计算的高位是 1 则计算结果是扩容之前的计算结果加上扩容前的数组的长度
6. get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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 &&
((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;
}
7. remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
四. 其他
扩容的时机：put
链表转化为红黑树的时机：put
红黑树转化为链表的时机：remove 和扩容再散列
链表转为红黑树的阈值：8
红黑树转为链表的阈值：6
最小树化的容量阈值：32 超出此值才允许链表转化为红黑树否则直接扩容
HashMap 的迭代器是 fail-fast 的，fail-fast 是 Java 集合中的一种机制，在用迭代器遍历一个集合时，如果遍历过程中对集合进行了修改则抛出 ConcurrentModificationException 异常。原理就是在创建迭代器对象的时候记录 HashMap 修改的次数（modCount）并且在遍历的时候比较记录的 modCount 与 HashMap 的 modCount 是否相等，不相等则抛出异常
HashMap 是线程不安全的，多线程场景有三种选择：
- 使用 java.util.Collections#synchronizedMap 创建线程安全的 map
- java.util.Hashtable
- java.util.concurrent.ConcurrentHashMap
参考
这些文章都比本文写得好：
面试官：哈希表都不知道，你是怎么看懂HashMap的？
Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？
《我们一起进大厂》系列-ConcurrentHashMap & Hashtable
|