这次只讲解部分源码，不会全部讲完。并且代码来自API 26 Platfrom。前段时间又重新简单看了一次HashMap的源码，想简单记录一下碰到的问题和在源码中能参考到的代码写法。
我先提出我的几个问题，如果有大佬路过的话麻烦请帮忙解答一下：
为什么获取hash的时候要与自身的右移动16位做异或运算
为什么根据key生成下标的做法是 (n - 1) & hash
为什么扩展数组的时候拆分链表的条件是e.hash & oldCap
接下来进入正题
1.HashMap节点结构体
可以先看看节点的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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;
}
}
用一个静态内部类来定义节点，节点里面有4个属性
（1）hash：这个节点的hashcode
（2）key/value：键值对
（3）next：指向下一个节点的指针
hashmap内部的操作基本都是对节点进行操作。
2.重要参数
hashmap中有几个重要的参数，在源码中也有明显的注释
这样的注释可以让开发者更快的找到相应的功能模块，如果一个类里面代码量多的话我也会这么写注释。
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
（1）table就是节点的数组，java中hashmap基本的形态就是一个链表数组（这是我的理解，不知道这样说对不对，反正就是数组和链表的结合），table就是这个数组。
entrySet本章先不解释
（2）size是长度，不是数组的长度，而是hashmap中包含的键值对的长度。
（3）modCount是操作次数，这个本章也不会细讲。
（4）threshold是数组的扩展容量（我的理解），往下看就知道有什么用了。
（5）loadFactor加载因子，往下看就知道有什么用了。
3.构造方法
构造方法是一个类的入口，所以我们先从构造方法看。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
这里有3个构造方法，两个参数分别是initialCapacity表示数组容量，loadFactor表示加载因子，简单了解下就行，按照最常见的用法，我们一般都是调用无参的构造方法
加载因子默认为DEFAULT_LOAD_FACTOR，也就是0.75（看下面的源码就知道loadFactor有什么用了）
4.put方法
我们一般调用无参构造函数实例化对象之后，就会调用put方法，也就是只设置了loadFactor的值之后就调put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
第一个参数为key的hashcode，我们可以看看hashcode怎么生成的
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到有调用object的hashCode()方法。
public int hashCode() {
return identityHashCode(this);
}
// Android-changed: add a local helper for identityHashCode.
// Package-private to be used by j.l.System. We do the implementation here
// to avoid Object.hashCode doing a clinit check on j.l.System, and also
// to avoid leaking shadow$_monitor_ outside of this class.
/* package-private */ static int identityHashCode(Object obj) {
int lockWord = obj.shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
return identityHashCodeNative(obj);
}
@FastNative
private static native int identityHashCodeNative(Object obj);
简单可以看出，这里是调用原生的方法生成的，那么我这里并没有追去看原生怎么生成的，我只是去网上收看到有人说生成的hashcode是内存地址，32位，如果不是这样的话希望能有大佬在评论指正
那么这里获取hash值就是用内存地址异或内存地址右移16位，至于为什么这样做，我也不知道，这说明即便光看源码，也并非什么都能看懂，我查了下，听被人说大概的意思是这样做能减少碰撞的次数，这个我也没认证过。
回头继续看putVal方法
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
为了方便看，我把没有走的代码先屏蔽掉，第一次put的时候，注意，是第一次调用hashmap.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;
.........
}
我们上面调用构造方法的时候，并没有对table进行初始化，所以它是空，所以肯定进入这个判断，有调一个resize()的方法，这个resize()方法很重要，主要做两个操作，初始化table数组和扩展table数组，第一次调肯定是初始化，我同样先屏蔽部分代码
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) {
......
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
......
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
......
}
return newTab;
}
要注意这里定义了几个参数，
（1）oldTab：变化之前的节点数组
（2）oldCap：变化前的数组的长度
（3）oldThr ：旧的threshold，也就是默认0
（4）newCap：记录改变后的数组长度
（5）newThr ：记录改变后的threshold
数组默认没初始化，所以oldCap是0，oldThr 默认也是0，所以
newCap = DEFAULT_INITIAL_CAPACITY; //(1<< 4 = 16)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // (0.75 * 16 = 12)
可以看出，第一次调用put的时候会先判断数组有没有初始化，如果没有，默认设置长度为16（1向左移动4位），threshold是数组长度的0.75倍（threshold是什么，下面会有说）
然后赋值给全局变量
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
好了，这里调用resize()方法就是为了初始化数组长度，还能从这个源码中看出一种做法，就是你设计某个模块的时候可以不用设计初始化方法，可以在调用的时候再去判断之前有没有初始化，没有就先进行初始化，这样的做法就会显得比较灵活。
继续看putVal方法
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
看到有4个参数，tab是形参，就是节点数组，p就是记录某个节点，n是记录数组的长度，i是记录某个下标。
刚才因为第一次Table为空，所以走进这个判断
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
调用上面resize()方法初始化数组之后，tab得到一个长度为16的数组，n等于16。
说实话，我很不喜欢赋值操作和逻辑操作写在一起，感觉这样写不好看
之后往下看，做判断
if ((p = tab[i = (n - 1) & hash]) == null)
看到&操作，肯定是位运算，n-1就是1111，用1111去和hash，一个32位的二进制做与运算，得出的结果就是下标。简单来说就是用某个方法生成一个0—15之前的一个小标，比如生成5，那结果就是tab[5]的值是不是空
所以第二个问题来了，生成下标为什么要用长度-1和hash做与运算
由于我们这个第一次肯定是空的数组，所以为空
tab[i] = newNode(hash, key, value, null);
为空的话就新建一个节点赋值给这个数组的下标。然后赋值逻辑就走完了，看看后续的逻辑
++modCount; // 操作数+1
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 提供给子类重写来给子类在该步骤下做特定操作
中间的操作，键值对的长度加1，如果键值对的长度超过threshold，则对数组进行扩展
到这里应该就能看出threshold的左右，相当于是一个阀值，如果键值对的数量超过这个阀值，我们就扩展数组，这是java里面HashMap扩展长度的一个思想。
那么第一次put我们讲完了，其实还挺简单的，假如我们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)
....... // 初始化的情况上面讲过了
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
根据这个Key的hash，用i = (n - 1) & hash算出下标，如果这个下标下的值不存在，那就创建这个节点和放到这个下标中，比如tab[6]，我们和上面一样，创建节点放入数组就结束，很简单。但是假如算出是5，tab[5]在第一次put的时候已经赋值了，那我们这里就要走else
if ((p = tab[i = (n - 1) & hash]) == 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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
有两个参数，e表示记录节点，k表示Key。这命名，我得吐槽一下，咋不整个aaa呢
判断
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
如果当前的hash值和之前存的节点的hash值相同并且key也相同，那就e = p;然后
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
把这个节点的value换成传进来的value，没错，这步就做了替换操作。
如果hash不等或者key不等，然后判断p instanceof TreeNode，这个节点是否是红黑树的数据结构。本章不讨论红黑树的情况，你只要知道在某个节点链表长度到一点值的时候，这条链表会转成红黑树就行。
假如当前节点的数据结构不是红黑树，
for (int binCount = 0; ; ++binCount) {
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;
}
死循环，e指向p的下一个节点（怕你乱多啰嗦一句，p就是数组中某个下标的那个节点，也就是链表的头节点）。如果e等于空（说明e处于链表最后一个节点的next的情况），新建一个节点加入链表
p.next = newNode(hash, key, value, null);
然后判断是否需要把链表转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
这里就印证我上面说的，当这条链表长度大于等于7的时候，链表会转成红黑树，因为我说了这篇不讨论红黑树，所以我假设长度没到7
如果没到尾，e!=null，判断e的hash和key与传进来的相不相同，相同的话覆盖（这里的break跳出死循环能走下面的赋值操作）
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
那假如key也不相等，就把指针移到下一位
p = e;
然后循环操作。
总结：put方法中，先判断节点数组初始化没有，没初始化的话会先初始化，然后判断数组某个下标是否为空，为空的话直接创建一个节点给这个下标，不为空的话，循环这个数组下标下的节点的链表，判断是否链表中的某个节点key相同，相同的话覆盖，不相同的话创建一个节点添加到链表的最后，如果长度到达7，将链表转成红黑树。put操作完成之后，最后判断size的长度有没有超过阀值，如果超过阀值，则扩展数组。
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; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
......
}
if (newThr == 0) {
......
}
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;
}
oldCap在第一次扩展的情况下是16，大于0
newCap = oldCap << 1
新的数组长度就是旧的长度向左移动一位，就是32。每次扩展都是左移一位，所以扩展肯定是2的倍数
newThr = oldThr << 1;
这玩意就没这么好算，12左移一位，要把12换成2进制比16换成二进制麻烦，有个更好的方法是拿newCap * 0.75 = 24，你去算也是相等的。那么新的阀值就是24。然后进入循环
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;
}
}
}
}
for循环是循环数组，如果当前下标没有next，那么这个新数组的这个下标的值就等于旧数组当前下标的值。如果这个下标的节点是红黑树（就是之前链表长度达到7），那就对红黑树做操作（这里不讲红黑树，大概了解就行）。如果都不是（说明当前数组下标的节点是个长度小于7 的链表）
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;
}
这个操作是，对链表进行遍历，按照e.hash & oldCap这个条件把一条链表拆分成high和low两条链表，把low链表放到新数组的当前下标，high链表放到新数组当前下标+旧长度的下标。
举个例子，旧的长度16，tab[5]的长度为6，它分成长度为2的low和长度为4的high，新数组tab[5] = low(长度2)，tab[21]=high(长度4)
那么我的第三个问题来了，一分二的意图其实很容易理解，但是为什么要根据这个条件来分？
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 && // 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;
}
根据这个key可以用(n - 1) & hash来拿到下标，put的时候也是这个条件，拿到下标之后判断当前这个下标的节点是否为这个key，是的话直接返回它的value，不是的话判断是不是红黑树，不是的话遍历链表来找相同的key，遍历完还没有的话就返回空。
7.总结
（1）主要讲了put、get和resize这3个方法
（2）hashmap中有两个神奇的操作，第一是扩展数组，第二是把链表转成红黑树
（3）提出几个问题，如果有大佬知道，请帮忙解答
为什么获取hash的时候要与自身的右移动16位做异或运算
为什么根据key生成下标的做法是 (n - 1) & hash
为什么扩展数组的时候拆分链表的条件是e.hash & oldCap
网友评论