一、HashMap解析
HashMap类继承体系
1.1 HashMap的数据结构
image.png
可以看出HashMap是数组+链表+红黑树构成。我们把数组中的每一个节点叫做桶。向哈希表中插入元素时，首先会根据key建算出对应的hash值，将hash值和桶的个数进行取余操作（hash&（n-1））确定元素在桶中的位置。当不同的元素计算的相同的hash值就认为发生了碰撞。这时，就是比较key是否一致，相同替换value，不同就在这个元素的后面挂上去，形成了链表。当链表长度超过8就会自动转成红黑树。
1.2 JDK8中的HashMap
在 HashMap 中定义了几个常量:
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;
依次解释以上常量:
- DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默认会创建 16 个桶，桶的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
- MAXIMUM_CAPACITY: 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。
- DEFAULT_LOAD_FACTOR: 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
- TREEIFY_THRESHOLD: 如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。
- UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
- MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
成员属性：
image.png
其中Node是HashMap的节点类型。既是HashMap底层数组的组成元素，又是每个单向链表的组成元素
static class Node<K,V> implements Map.Entry<K,V> {
//key的哈希值
final int hash;
final K key;
V value;
//指向下个节点的引用
Node<K,V> next;
构造方法：
image.png
image.png
image.png
判断大小是否合理，如果超过，赋最大值，调用tableSizeFor（initialCapacity),返回一个最小的大于输入参数的2的整数次幂的数
threshold这个成员变量是阈值，决定了是否要将散列表再散列。它的值应该是：capacity * load factor才对的。
其实这里仅仅是一个初始化，当创建哈希表的时候，它会重新赋值的
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
根据key计算出hash值，调用putVal方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
扰动函数：根据键计算出hashCode，将hashCode由于16位与自己做异或操作。目的是将高位和低位结合后，使hashCode上1分布更均匀，增加了随机性，减少了碰撞发生的可能。（默认的初始容量是16，要放到散列表中，就是0-15的位置上。也就是tab[i = (n - 1) & hash]。可以发现的是：在做&运算的时候，仅仅是后4位有效~那如果我们key的哈希值高位变化很大，低位变化很小。直接拿过去做&运算，这就会导致计算出来的Hash值相同的很多）
/**
* Map.put和其他相关方法的实现需要的方法
*
* @param hash 指定参数key的哈希值
* @param key 指定参数key
* @param value 指定参数value
* @param onlyIfAbsent 如果为true，即使指定参数key在map中已经存在，也不会替换value
* @param evict 如果为false，数组table在创建模式中
* @return 如果value被替换，则返回旧的value，否则返回null。当然，可能key对应的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()创建一个哈希表，并用变量n记录哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//调用resize方法，每次扩容都是翻倍，与原来计算（n-1）&hash的结果相比，节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置
//如果指定参数hash在表中没有对应的桶，即为没有碰撞
if ((p = tab[i = (n - 1) & hash]) == null)
//直接将键值对插入到map中即可
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);
//如果链的长度大于TREEIFY_THRESHOLD这个临界值，则把链变为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//跳出循环
break;
}
//如果找到了重复的key，判断链表中结点的key值与插入的元素的key值是否相等，如果相等，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
//如果key映射的节点不为null
if (e != null) { // existing mapping for key
//记录节点的vlaue
V oldValue = e.value;
//如果onlyIfAbsent为false，或者oldValue为null
if (!onlyIfAbsent || oldValue == null)
//替换value
e.value = value;
//访问后回调
afterNodeAccess(e);
//返回节点的旧值
return oldValue;
}
}
//结构型修改次数+1
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
//插入后回调
afterNodeInsertion(evict);
return null;
}
putVal方法可以分为下面的几个步骤：
- 如果哈希表为空（当我们放入第一个元素时，如果底层数组还是null），调用resize()创建一初始容量为16的Node数组，但逻辑长度size还是0，类似于ArrayList的初始化。
- 如果指定参数hash在表中没有对应的桶，即为没有碰撞，直接将键值对插入到哈希表中即可。
- 如果有碰撞，遍历桶，找到key映射的节点
- 桶中的第一个节点就匹配了，将桶中的第一个节点记录起来。
- 如果桶中的第一个节点没有匹配，且桶中结构为红黑树，则调用红黑树对应的方法插入键值对。
- 如果不是红黑树，那么就肯定是链表。遍历链表，如果找到了key映射的节点，就记录这个节点，退出循环。如果没有找到，在链表尾部插入节点。插入后，如果链的长度大于TREEIFY_THRESHOLD这个临界值，则使用treeifyBin方法把链表转为红黑树。
如果找到了key映射的节点，且节点不为null
记录节点的vlaue。
- 如果参数onlyIfAbsent为false，或者oldValue为null，替换value，否则不替换。
返回记录下来的节点的value。 - 如果没有找到key映射的节点（2、3步中讲了，这种情况会插入到hashMap中），插入节点后size会加1，这时要检查size是否大于临界值threshold，如果大于会使用resize方法进行扩容。
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
从源码中可以看到，get(E e)可以分为三个步骤：
通过hash(Object key)方法计算key的哈希值hash。
通过getNode( int hash, Object key)方法获取node。
如果node为null，返回null，否则返回node.value。
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) {
//如果桶中的第一个节点就和指定参数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) {
//如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果当前的桶不采用红黑树，即桶中节点结构为链式结构
do {
//遍历链表，直到key匹配
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//如果哈希表为空，或者没有找到节点，返回null
return null;
}
getNode方法可分为以下几个步骤：
- 如果哈希表为空，或key对应的桶为空，返回null
- 如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点。
- 如果桶中的第一个节点没有匹配上，而且有后续节点
- 如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
- 如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配
- 找到节点返回节点，否则返回null。
remove（Object key）
/**
* 删除hashMap中key映射的node
*
* @param key 参数key
* @return 如果没有映射到node，返回null，否则返回对应的value。
*/
public V remove(Object key) {
Node<K,V> e;
//根据key来删除node。removeNode方法的具体实现在下面
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
![]()
image.png
image.png
二、HashMap与Hashtable
从存储结构和实现来讲基本上都是相同的。它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。Hashtable是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换
![]()
image.png
image.png
三、小结
- 在JDK8中，HashMap是数组+链表+红黑树实现的
- 在散列表中有装载因子这么一个属性，当装载因子*初始容量小于散列表元素时，该散列表会再散列，扩容2倍！
- HashMap并不是直接拿key的哈希值来用的，它会将key的哈希值的高16位进行异或操作，使得我们将元素放入哈希表的时候增加了一定的随机性
- 值得注意的是：并不是桶子上有8位元素的时候它就能变成红黑树，它得同时满足我们的散列表容量大于64才行的
