本人从事开发工作8年有余，从事的行业从移动社交、framework、电商到现在从事的物联网。积累了这么多年，发现了一个道理：不管行业如何变化、技术如何变化，都离不开计算机基础，也离不开计算机奠基者优秀的设计，所谓万变不离其宗，在研发层面也得到了最好的证明。本系列文章将围绕前人的源代码进行精细分析(主要是Java语言)，本系列不会动辄贴出一大段代码，更不会跨过任何一行代码，而是会一行行解读，先做到知其然，后面才有机会知其所以然。从现在开始，我将从JDK1.8的HashMap开始按行精读源代码，确保分享的每行代码都知其然。
话不多说，马上开始。我们直接从一个空的HashMap的put函数讲起，至于初始化的过程和非空HashMap的put过程，咱们放到下一篇再讲。注意，是一个空HashMap的put过程，重点在于“空”这个字。
先来看第一段代码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这段代码很简单，意思就是直接调用了另外一个叫做putVal的函数，其中传进来的key需要另外调用一次hash(key)，得到的结果作为putVal函数的第一个参数。那么我们就来看看hash函数是怎么实现的。代码如下
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这段代码其实是计算根据一个对象来计算hash值，咱们来按字符分析，从左到右来看，如果key == null就return 0，这就证明HashMap是可以以null为key的，只不过计算出来的hashCode是0而已，是不是有面试官曾问过你这个问题呢？如果key不为null，则首先取key的hashCode()函数的返回值赋值给h，再把h无符号右移16位，最后把h和h右移16位之后的值进行按位异或的操作。这个就是我们常说的HashMap的hashcode计算公式。还是老规矩，我们一点点进行分析。首先就是h=key.hashCode()这个运算，我们都知道，这个key可以是任何数据类型的，那么key的hashCode函数的返回值就是根据这个数据类型的hashCode函数的实现来计算的。例如，Integer类型的key的hashCode为Integer类重写的hashCode函数。代码如下
@Override
public int hashCode() {
return Integer.hashCode(value);
}
public static int hashCode(int value) {
return value;
}
可以看到，Integer类型数据的hashCode就是它包装的int值。
在这里，我向大家提一个问题，String类型的hashCode是如何计算的呢？欢迎大家在留言区告诉我。
那咱们继续，如果key是一个开发者的自定义对象，那这个h=hashCode()是多少呢?例如，我们定义一个类
public class User {
private String name;
public User(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
可以看到，我定义的User类并没有重写Object的hashCode()函数，那么key.hashCode会报错吗？如果不会，会发生什么呢？这里我先把答案写出来，其实是不会报错并且key.hashCode()是有值的。
实践出真章，我们来实际跑一个demo试试。
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
User user = new User("wang");
Map<User, String> map = new HashMap<>();
map.put(user, "1");
System.out.println(map.get(user));
}
}
代码运行完毕，会正常输出1。
我们跟着IDE，debug进入到key.hashCode()这里看看
image.png
有没有觉得很奇怪呢，这里竟然有值。这里key.hashCode()有值，是因为Object的hashCode()函数在c++层根据算法做了默认实现。
具体实现方法我直接贴出源码地址，c++代码不在本文讨论范围内，有兴趣的同学可以私下研究研究。
http://hg.openjdk.java.net/jdk8u/jdk8u/hotspot/file/87ee5ee27509/src/share/vm/runtime/synchronizer.cpp
hashcode默认实现算法参见get_next_hash函数。
看到这里，你有没有被面试官问过类似于自定义类的hashCode()问题呢？这下你就知道了，自定义类，即使不复写hashCode函数，也会有值，所以自定义类的对象是可以作为HashMap的key的。
到此为止关于h=hashCode()的分析就完成了，接下去我们要分析的是h>>>16这行代码。我们都知道，无符号右移n位意思就是除以2的n次方，所以这里的意思也就很清晰了，就是计算出来的h需要除以2的16次方。最后，再与h进行按位异或运算，得到最终的hash值。说到这里，相信很多同学已经忘了按位异或是什么意思了，我来带大家复习一下。按位异或的意思就是当前位的两个二进制表示不同则为1相同则为0。计算公式如下：
0^0 = 0
1^0 = 1
0^1 = 1
1^1 = 0
可以总结出两句话，0异或任何数＝任何数，1异或任何数=任何数取反。结合上述，我们知道2的16次方等于65536，所以当key的hashCode()小于65536时，HashMap的key对应的hash就是这个key本身调用hashCode()计算出来的hash，当key的hashCode()大于等于65536时，HashMap的key对应的hash就是这个key调用hashCode()计算出来的hash右移16位，然后与h按位异或计算出来的结果。
好，我们终于完成了对hash(Object key)这个函数的分析。
下面继续往下查看源码
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;
这里就是put的过程，首先，我们在第一行看到了一个数组tab，一个链表p的定义，另外还有两个int参数n和i。看下一行，是一个判空的过程。首先把table赋值给tab，然后判断tab为null或者数组长度为0。table指的是
HashMap定义的一个成员变量，是一个数组。定义如下
transient Node<K,V>[] table;
它就是用来存放key/value的卡槽，当tab为null或者长度为0，则表示这个数组还没有初始化或者数组中还没有元素，那这时候就没有空间存放我们的key/value，所以有了下一行代码
n = (tab = resize()).length;
从resize这个英文可以看出，这行代码是在对tab进行调整大小。调整完毕之后，把长度赋值给n，所以这里的n表示的就是数组的长度。
接下去我们继续看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
}
为了便于分析，我截取了第一段初始化参数的过程和第一个if。oldTab就是调整数组大小之前的成员变量table的值，这里还是做了一下null的判断，如果oldTab为null，则把oldTab的容量也就是oldCap参数置为0，否则取之前的oldTab的长度。oldThr取成员变量threshold，表示容量阈值，这个threshold默认是0。从上面的分析可以知道oldCap 为0，所以第一个if不会进，所以我们直接看第二个if。
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);
}
这里就是设置newCap和newThr的过程了，newCap表示新容量，newThr表示新的阈值，之前的容量和阈值均为0。这里赋值完成之后，newCap为16，newThr为12(DEFAULT_LOAD_FACTOR为0.75，DEFAULT_INITIAL_CAPACITY为16)。那这个阈值指的是什么呢？这里留下一个问题，后面会进行分析。
继续看代码
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
我们已知newThr为12，所以这个if不会进
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
这里把12赋给了成员变量threshold，表示当前hashMap对象的阈值为12。另外新建了一个容量为16的数组并且把这个数组赋值给了成员变量table。再往下看
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)
.
.
.
根据前面的分析，这个oldTab为null，所以这个if不会进。会直接return newTab，也就是把我们新建的容量为16的数组return了。至此，putVal过程调用resize函数的执行过程暂时先分析完毕了。下面回归putVal函数继续分析
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
这段代码是先根据hash来计算数组的索引，然后把这个索引对应的数组的值赋值给到p，然后判断这个p是不是null。计算索引的算法是(n-1)&hash，n是数组的容量，刚才计算出来是16，然后减1，与hash进行按位与操作，其实这就是高效的hash对n的取模运算。打个比方，设n-1=15，hash=10，我们分别把n-1和hash都转为二进制，那么15=1111，10=1010，进行按位与的操作后得到1010，换算成十进制之后是10，也就是10对16进行取模运算得到的结果，如果不信的话，大家还可以用其他数据进行试验，你会发现其实结果都一样。那这是为什么呢？我们来分析一下。其实按位与的操作如下：
1&1=1
1&0=0
0&1=0
0&0=0
我们可以得到一个结论，任何数与0进行按位与的操作得到的结果都是0，任何数与1进行按位与的操作得到的结果都是它本身。得益与n值一定是2的x次方（后面会详细解释），这里才能通过(n-1)&hash这样的方式高效的进行取模运算。为什么一定n是2的x次方才可以这样取模呢？因为只有2的n次方减1之后才能得到全是1是二进制数据，例如16是2的4次方，减1之后转为二进制就是00001111，当hash比n这个数小，例如15的二进制是00001111与00001111按位与之后，得到的结果是00001111，也就是hash本身，相当于15对16取模；当hash比n这个数大，例如17的二进制是00010001与00001111按位与之后，高位一定全是0，后四位就是hash本身的后四位，得到的结果是00000001，也就是1，相当于17对16取模。再强调一遍，n必须是2的x次方才可以这样计算。之所以位运算很高效，是因为位运算不需要涉及到进制转换，直接在内存中进行运算，而取模操作需要先做进制转换，在内存中算完之后再做进制转换。
当这个索引对应的p值为null则表示当前索引位置的值对应的节点为null，需要把初始化或者实例化这个节点。下面我们看一下newNode函数
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
就是调用一个Node类的构造函数。也就是对链表进行实例化。
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;
}
这就是个简单的单向链表的数据结构。next这时候传的是null，表示当前Node为链表的头节点。
回到putVal函数，再往后有个else ，这时候不会进，我们直接跳到最后
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
有个成员变量叫modeCount，表示hashMap被结构修改的次数，每次执行put函数会加1，默认值是0。还有个参数叫size，每次执行put函数会加1，默认值是0。当size大于阈值12，会引发一次resize扩容。我们等会接着分析这种情况下的resize函数。最后是一个函数，会在元素插入hashMap完毕之后调用。HashMap的afterNodeInsertion是一个空实现，HashMap的子类LinkedHashMap是做了相关实现的，在这里不做扩展。
那么至此为止，一个空的HashMap的put过程就简单分析完毕了。咱们采取一行行代码分析的方法，把这个过程弄的很透彻了。下篇预告：非空HashMap的put过程和发生Hash冲突的情况下的put过程分析。在下一篇文章中，我们能看到数组、链表以及红黑树这三种数据结构在HashMap中的应用，敬请期待。
网友评论