????????HashMap是我们Java程序员在面试题中被问烂的一个知识点。几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap，但是你真的看过它的源码吗？今天我们就来研究一下HashMap的源码（本人采用JDK1.8）。
一、HashMap简介
????????我们都知道HashMap在JDK1.7的时候采用了数组+链表的数据结构，而在JDK1.8的时候采用了数组+链表+红黑树的数据结构，大概就是以下样子：
????????在添加元素时，会先计算出该元素所在table中的桶，然后再进行put操作，当链表长度大于8并且桶的个数大于64时就会进行树化。
为啥在jdk1.8要树化呢？那一定是为了效率。
????????链表查找一个元素的时间复杂度为O(n)，而红黑树的查找方法的时间复杂度为O(logn)，所以在数据量特别大，并且产生的Hash冲突很多时，转成树查找的效率会更高一些。
为啥不一开始就用树呢？为啥要在8的时候树化呢？
在官方的注释是这个样子的：
?/**
?*?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
*/大致意思就是，TreeNodes的大小大约是常规结点的两倍，数据量太小时投入的空间成本不如回报的时间成本，没啥必要。
为啥是8？本人之前一直以为可能大于8之后的查找效率变得很低，采用树会好很多。但是设计者认为，理想情况下，在随机hashCodes下bin（桶）中的结点服从泊松分布，树型bin用到的概率非常小，因为数据均匀分布在每桶中，几乎不会有bin中链表长度会达到阈值，概率仅仅为0.00000006。但是可能我们的HashCode编写的不是很好导致Hash冲突严重，从而造成了链表长度大于8，所以又加了树化的操作用来提升效率。
为啥是64？可能桶的个数在64之前，扩容效率比树化好一些吧。
二、HashMap的源码
首先，映入眼帘的当然是它注释，大致意思就是：
①HashMap基本和HashTable相同，除了HashMap不同步（所以线程不安全）并且允许null键和null值，不保证映射的顺序
②HashMap提供了常数时间性能的操作（put和get）
③影响HashMap的性能的两个指标：初始容量（哈希表的桶数量）和负载因子（默认0.75，哈希表允许满程度的度量，超过时自动增加容量，扩容至两倍）。
④如果初始容量大于实际存储的数量÷0.75，则不会发生rehash的操作。所以我们加入知道了我们存放元素的大致数量，可以指定其初始容量减少扩容的次数从而提高性能。
大致看完之后就是他的源码部分，开头定义了一些默认的常量，后续的源码会用到他们：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
?
private static final long serialVersionUID = 362498820763181265L;
?
????/**
?????*?默认的初始容量
*/
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;三、HashMap的一些重要方法
看完注释之后我们来看一些在HashMap中的一些重要方法。
①hash方法
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}hash方法，顾名思义，用来计算元素的hash值，看方法必先看注释，巴拉巴拉一大堆，大致意思就是因为我们的table（也就是数组）一般都采用2的指数幂的大小，再寻找桶时寻找桶时，低位的二进制发生Hash冲突概率会变高，高位的二进制码用不到，所以必须将高位向低位移动，让高位也参与到hash计算中，从而减少hash冲突。
假设我们桶的大小为n=16，计算桶的公式为i = (n - 1) & hash，假设一个hashCode =?0010 0100 1011 0011 1101 1111 1110 0001，则
0010 0100 1011 0011 1101 1111 1110 0001
0000 0000 0000 0000 0000 0000 0000 1111
?&??（同时为1，结果为1，否则为0）??
?=??0000 0000 0000 0000 0000 0000 0000 0001所以不管我们高位数据如何变化，实际应用到的只有低几位，具体是几取决于桶的个数，一般认为桶不大于65535，也就是低16位，所以为了用到高16位，先进行右移16位后和自己做一下异或运算，让高16位也参与到hash计算中。
那为啥用异或（^）而不用与运算（&）也不用或运算（|）呢？
因为在二进制中只有0和1，只有00、01、10、11这四种可能，他们的与运算结果为0&0=0、0&1=0、1&0=0、1&1=1，为0的概率为3/4，1的概率为1/4，同样的或运算为0的概率为1/4，1的概率为3/4，而异或则分别为1/2，因此为了0和1的分布更加均匀，采用了异或运算。
②get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
?
/**
* Implements Map.get and related methods.
*
?*?@param?hash?for?key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
????//先判断数组是否为null,不为null再判断长度是否大于0，然后再判断该桶上有
????//没有结点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
????????//先判断hash值是否相等，然后再判断地址是否相等，
????????//最后再调用equals方法判断是否相等
if (first.hash == hash && // always check first node
((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;
}get()方法比较常规，只是有一个细节不知道大家有没有注意，再21行位置有个always check first node，第一个判断条件为判断hash值是否相等，我们有时候可能会被问到hash值相等的对象一定相等吗？答案是不一定，但是hash值不相等的对象一定不相等。
③put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
?
/**
?*?将元素放到HashMap
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
????//判断数组是否为null或长度为0，一般我们调用无参构造时，会走到这儿
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
????//如果当前桶没有结点，则new一个结点返回
??? if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
????//当前桶存在结点
else {
Node<K,V> e; K k;
????????//判断该结点结点的key是否匹配
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 {
????????????//遍历链表查看是否包含该key，使用尾插法,
????????????//1.7的头插法可能导致成环
for (int binCount = 0; ; ++binCount) {
????????????????//若当前结点的下一个结点为空，则直接new一个新结点
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;
}
}
//当前map中存在该key
????????if?(e?!=?null)?{
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
????????????//LinkedHashMap方法 HashMap空实现
afterNodeAccess(e);
return oldValue;
}
}
????//该字段是记录HashMap结构改变（resize或者映射数量改变）的次数
++modCount;
if (++size > threshold)
resize();
????//LinkedHashMap方法 HashMap空实现
afterNodeInsertion(evict);
return null;
}put()方法也比较容易，只不过会涉及resize()和treeifyBin()方法。其中维护了一个modCount字段，这是给Fail-Fast机制维护的字段，当我们使用迭代器时，会将此值赋值给Iterator的expectedModCount字段，当我们再次修改HashMap时，若这个值不匹配则会抛出ConcurrentModificationException的异常。
if (modCount != expectedModCount)
throw new ConcurrentModificationException();④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;
}
??????//扩容为2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
??????????//阈值扩2倍
newThr = oldThr << 1; // double threshold
}
??//将上次的下一次的容量赋值给新的容量，这个threshold是阈值
else if (oldThr > 0)
newCap = oldThr;
??//空参调用时的默认参数
??else?{
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
??//新阈值为0则赋值为newCap?*?loadFactor
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?{?//?preserve?order
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;
}resize()方法简单来说就是将桶扩容为之前的2倍。由于resize()不是synchronized的，因此是线程不安全的，在JDK1.7时，会因为头插法而导致成环问题。
核心的方法就是这么几个，剩下的就不一一罗列了，大家有兴趣自己阅读即可，下次面试官再问你HashMap你了解吗，我们就可以大展身手啦。
今天的分享就到此结束啦，喜欢的小伙伴记得点赞呦。
下期分享：ConcurrentHashMap。
关注公众号JavaGrowUp，下期不迷路，获取更多精彩内容。
?