JDK1.8 HashMap源码解读
写作目的
本文旨在探究HashMap的源码设计思路，仅供学习交流之用.
问题合集
HashMap的继承与实现
1.问：在JDK1.8中，HashMap的继承与实现的关系如何？
答:
源码如下:
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
HashMap继承了AbstractMap,实现了Map，Cloneable, Serializable。
利用IDEA的yFiles得效果图如下:
2.问：接第一问，为何这么设计
答: 首先关于AbstractMap，其实现了Map接口，继承此abstract类可以避免重复造*，提高代码的重用率；其次关于Cloneable，查看它的源码后可以发现其并没有声明任何的方法，实现 Cloneable是来表示该对象能被克隆，能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException；最后关于Serializable，与Cloneable类似，内部也没有方法，实现Serializable也是为了确保HashMap类本身能够实现序列化。
HashMap的关键参数
1.描述 DEFAULT_INITIAL_CAPACITY
答：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap的初始容量，左移4位即是1*2^4 = 16，
那为什么要设置为16，可以初始化是指定么？
其实是可以的，并且是推荐的 [阿里巴巴开发手册]：
具体见 HashMap容量为什么设置初始值为16
2.描述 MAXIMUM_CAPACITY
答：
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap的最大容量，如需指定，必须为2的n次幂，且小于初始的2^30
3.描述 DEFAULT_LOAD_FACTOR
答：默认的负载因子, 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容，扩容为原来的两倍。
至于为什么设置为0.75，是因为负载因子太小了浪费空间并且会发生更多次数的resize，太大了哈希冲突增加会导致性能不好，所以0.75只是一个折中的选择，和泊松分布没有什么关系，本质上就是trade off–(权衡之后的折中方案)。具体见
HashMap defaultLoadFactor = 0.75和泊松分布没有关系.
为什么每次扩容都是原来的两倍？
JDK8因为巧妙的设计，性能有了大大的提升：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：
数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。如下图：
详见HashMap的扩容机制
4.描述 TREEIFY_THRESHOLD
答：
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
TREEIFY，即树形化。TREEIFY_THRESHOLD,表树化域值： 默认值为 8 。表示在一个node（Table）节点下的值的个数大于8(链表的长度大于8)时候，会将链表转换成为红黑树。
那为什么是8呢？
首先需要明确的是treeify不是一个廉价的操作，因此需要避免频繁的树形化，其次，链表太长也会影响查找效率，所以我们需要找到一个合适的值。
TREEIFY_THRESHOLD的寻找过程和泊松分布有关。记住结论：8个键值对同时存在于同一个桶(bin)的概率只有 0.00000006，具体见源码中的如下片段
/* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
* /
因此认为8是一个比较合理的值
5.描述 UNTREEIFY_THRESHOLD
答：
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
6.描述 MIN_TREEIFY_CAPACITY
答：
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
否则，若桶内元素太多时，则直接扩容，而不是树形化
为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
HashMap的构造方法
1.初始化容量和负载因子，原16和0.75
public HashMap(int initialCapacity, float loadFactor)
2.仅初始化容量
public HashMap(int initialCapacity)
3.无参构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
4.指定K,V类型
public HashMap(Map<? extends K, ? extends V> m)
HashMap的常见方法
| 方法名 | 返回值 | 作用 |
|---|---|---|
| put(k,v) | void | 插入一个k,v键值对 |
| get(k) | v | 提供k，计算hash值后获取v或返回空 |
| entrySet() | Set<Map.Entry<K,V>> | 返回entrySet的存储值 |
| containsKey(k) | boolean | 是否含有k |
| keySet() | Set < k > | 返回ket的集合 |
| clear() | void | 清空hashmap |
| containsValue(v) | boolean | 是否含有value |
| isEmpty() | boolean | 是否为空 |
| size() | int | 容量 |
| values() | Collection | 返回v的集合(不会去重！) |
| clone | Object | 浅拷贝 |
| compute(K key, BiFunction remappingFunction) | V | 对 hashMap 中指定 key 的值进行重新计算 |
| computeIfAbsent(K key, BiFunction remappingFunction) | V | 如果k不存在就重新计算，如果存在就当无事发生 |
| computeIfPresent(K key, BiFunction remappingFunction) | k | 对 hashMap 中指定 key 的值进行重新计算，前提是该 key 存在于 hashMap 中。 |
| putAll(Map<? extends K, ? extends V> m) | void | 将所有键/值对添加到 hashMap 中(将一个hashmap中的值填入本map中，重复的key会被忽略而不是覆盖) |
| merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) | V | 1.key不存在，则插入新值。2.key存在，value不存在，则插入指定的value.3.value如果存在，则返回经过计算后的值 |