一、Hash
将任意长度的输入，通过hash算法变成固定长度的输出。
特点：
- 不能从hash值反推出原始数据
- 输入数据的微小变化可导致hash值的完全不同，相同数据会得到相同的值
- hash算法执行效率要高
- hash算法的冲突概率要小
常见的hash算法：MD4、MD5、SHA-1、SHA-2、SHA-3等，后两种相对安全。
二、HashMap原理
这里讲的是1.8版本的。
2.1 Node
Node是HashMap里的一个元素，结构如下：
static class Node<K,V> implements Map.Entry<K,V> {
// 经过hash之后的key
final int hash;
final K key;
V value;
// 链表指针
Node<K,V> next;
}
Node的equals方法重写过，地址相同或者key和value两者的地址或equals匹配上都返回true。
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
2.2 属性值及构造方法
// 缺省table大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// table最大长度
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;
// 树化的另一个参数，当哈希表中的所有元素个数超过64时，才会允许树化
static final int MIN_TREEIFY_CAPACITY = 64;
// 哈希表，第一次put的时候初始化
transient Node<K,V>[] table;
// 当前哈希表中元素个数
transient int size;
// 当前哈希表结构修改次数, 元素新增或删除次数，修改元素不计数
transient int modCount;
// 扩容阈值，当你的哈希表中的元素超过阈值时，触发扩容，为2的幂，这样
// 在put key路由寻址的时候减少hash碰撞
int threshold;
// 负载因子默认0.75，如果内存大而且对速率要求高的话可以降低负载因子，反之则增大。
final float loadFactor;
HashMap(int initialCapacity, float loadFactor)构造方法做了参数校验，以及将扩容阈值threshold设置为不小于initialCapacity的最小2的幂。
2.3 HashMap的put过程
- 获取key的hash值：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
key的hash值的高16位异或低16位。 - 判断table是否为空，是的话resize初始化table
- 路由寻址 (table.length - 1) & hash算出位置
- 如果该位置为空，直接新建Node丢进去
- 如果该位置不为空：
5.1 如果该位置的key和当前key一致，则替换
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;
5.2 如果当前节点为TreeNode，那么插入到红黑树里
5.3 否则就是链表情况，进行链表的遍历。如果遍历到空元素了，说明遍历完了，新建节点并插入到末尾，然后判断链表长度是否达到树化阈值，是的话进行树化。
如果遍历时碰到key值相同的节点，那就替换。 - 如果没有找到key值相同的node，就修改modCount，++size，如果size大于扩容阈值就执行resize()。
2.4 HashMap的resize过程
- 计算扩容之后table数组的大小newCap和扩容之后下次再次触发扩容的阈值newThr。
- 根据newCap创建newTable,如果oldTable == null那么return newTable
- 遍历oldTable：
3.1 如果节点的next为空，那么直接重新计算位置，然后把节点塞过去。
newTab[e.hash & (newCap - 1)] = e
3.2 如果是树节点，那么进行树的降级或者链化
3.3 否则就是链表了。将链表里的节点按照e.hash & oldCap是否为0分为高位节点和低位节点，分割成2条链表，塞到newTab里。低位节点链表桶位位置不变，高位节点的位置是低位节点的位置 + oldCap。
2.5 HashMap的get过程
- 调用hash方法计算key的hash，然后(table.length - 1) & hash 定位到桶位
- 如果table是空或者该位置的node为null的话，return null
- 如果判断node符合(node的hash相等&&(key地址相等||key.equals(node.key))), 返回该node的value
- 如果next不为空
4.1 是树节点的话，遍历树节点，取数据
4.2 否则就遍历链表一个个判断key - 否则返回null。
2.6 HashMap的remove过程
- 根据参数key，用上面get的方式找到要remove的node，如果没找到就return null
- 如果找到了
2.1 如果node是树节点，那么执行移除树节点方法
2.2 如果节点就是桶位的节点，那么将该桶位设置为node.next，即tab[index] = node.next
2.3 否则就是在链表上了，让node的前节点的next指向node.next，即p.next = node.next
2.4 最后返回被移除的节点node
三、HashMap相关注意点
1. 自定义类型作为key时，要重写hashCode方法和equals方法
HashMap通过
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
的方式判断key相等(节点符合)，而hash是通过key的hashCode方法算出来的，所以我们用自定义类型作为key时，要重写他的hashCode方法和equals方法
2. jdk1.8的HashMap在put时为什么会有并发问题？
假设A和B线程put两个不同的key，但是两个key计算后的位置相同，这时候刚好都运行到了刚好找到桶位这行
if ((p = tab[i = (n - 1) & hash]) == null)
其中一个A线程执行了下面的代码把node放进去，然后B再继续执行那就会把A线程的node覆盖掉，本来两个不同的key应该要形成链表的，这种情况就造成数据的丢失。
3. jdk1.7的头插法为什么会造成链表变成环？
主要是resize方法里的移动链表节点。方法如下，就是遍历链表将他们头插的形式转移到新table
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
假设table[i]槽位上有个链表a -> b -> null，此时有2个线程同时进行resize：
- 线程1进行到Entry<K,V> next = e.next执行完，此时e为a，next为b。
- 这时候线程2跑完了，把链表结构改成了 b -> a -> null。
- 然后线程1继续，跑完这次循环后e为b，newTable[i]为a，继续下次循环。
- next变成a，newTable[i]为b，e为a，继续下次循环。
- next变成null，执行完e.next = newTable[i]后，a.next为b，形成环了。newTable[i]为a，e为null，退出循环。最终结构 b <-> a -> null。
之后执行get的时候就会陷入死循环。
参考资料
B站-小刘讲源码
网友评论