前言
前几天，见过一道面试题。是这样的，HashMap中，数组的默认初始化容量是多少？为什么？当时这道题把我难住了，怎么说我也是写了两年JAVA的人。这种基础问题还把我问住了，不经一阵老脸通红。趁着大家不注意时偷偷看了下源码之后，总算搞明白了。
1 概述
HashMap作为java中常用的类，也常出现在各类面试中，足可见其重要性。今天我们针对JDK1.8来分析一下这个类，揭开它的神秘面纱。
2 HashMap 简介
1.什么是哈希表?
讨论哈希表之前，咱们先来了解一下其他几种常用的数据结构在新增，查找，删除时的基础性能(注：以下时间复杂度为最坏情况下的时间复杂度)
数组：采用一段连续的内存单元来保存数据，对于通过给定的下标进行查询，时间复杂度为O(1)，通过给定元素进行查找时，因为要遍历数组逐一比对；时间复杂度为O(n)。当然，对于有序数组，可采用二分查找，可将效率提高到O(logn)。插入时，在尾部追加，时间复杂度为O(1)。删除操作，因为需要涉及到数组的移动，时间复杂度为O(n)。
线性链表：采用指针形式，保存上一个元素在内存中的位置。新增，删除等操作，只需要在尾部进行插入即可，删除时，只需将下一节点指向改变即可，故时间复杂度都为O(1)。查找时，需要遍历链表，时间复杂度为O(n)。
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：哈希表的构成是一个数组+哈希函数。新增，删除和查询时，通过哈希函数，直接定位到指定的下标，完成操作即可。故时间复杂度为O(1)。如果还不清楚，请看下图：例如，我要将一个john,和一个jemes放入哈希表中。
例如，我要将一个john放入哈希表中，假设通过哈希函数f(john)，计算得到。存储地址为2，将john放入数组下标为2的地址即可。要删除john时，直接将该地址置空即可。查找原理相同。有人不竟会问，既然哈希表如此高效。为啥数据结构中，不全部用哈希表呢？
首先，事无完美，哈希表虽然这么高效。但是如果两个数，通过哈希函数计算出来的地址时如何处理？替换掉原来的值吗？这显然不行。这种现象就是经典的哈希冲突问题。好的哈希函数会尽量的保证计算简单和元素的地址分布均匀。但是，再好的哈希函数，都有可能发生冲突，当然，解决的方案也很多，如：开放定址法（发生冲突，继续寻找下一块未被占用的地址），链地址法（发生冲突时，使用链表的形式存入，常用的有头插法或尾插法）。JAVA中的HashMap采用的是链地址法。
3 HashMap的实现原理及整体结构
这里我先放一张HashMap的结构图。让大家有个印象，接下来再去查看源码验证。
1. 结构分析：
简单来说，HashMap是由数组+链表组成的，数组为HashMap的主体，链表为解决哈希冲突而生。将一个元素放入HashMap中时，通过哈希函数得到具体位置，检查当前位置是否为空，为空时，直接放入即可，不为空，采用头插法，将当前元素插入，原来的元素指向当前元素即可，时间复杂度为O(1)，同理，查找时，通过哈希函数找到位置，若当前位置只有一个元素，则时间复杂度为O(1)，若当前位置为链表，还需遍历一下链表找到该元素。在JDK1.8中，链表的实现方式为二叉树和红黑树的形式，考虑到篇幅有限，就忽略掉红黑树实现了，我们直接把它当做一个普通的链表实现即可
2. 源码分析：
我们先来看看HashMap的几个重要的初始化参数，后面三个参数是与红黑树有关的，这是JDK1.8在以前的基础上进行的优化，即当链表个数大于8的话转换红黑树，就不重点讲解了。
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：初始化时默认的数组大小，这里采用了位运算。也就是2^4=16
MAXIMUM_CAPACITY：最大数组长度2^30=1 073 741 824
DEFAULT_LOAD_FACTOR：加载因子。默认为0.75。指定了何时进行数组扩容
接下来是构造函数
//指定了初始化桶容量及加载因子
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);
}
//无惨构造函数，采用懒加载的方式，put时初始化数组
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//传入一个map。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);//该方法遍历传入的对象，放入该对象中
}复制
可以看到，HashMap有四个构造函数，但是我们常用的为无惨构造函数。JDK很聪明，该方法采用了懒加载的方式。在没有put时，不初始化数组。节省了不必要的内存空间和创建对象花费的时间
3 . 前面说过了，HashMap的主干为数组。
transient Node<K,V>[] table;//Node数组，大小一定为2的n次幂。具体原因下面会分析复制
Node作为HashMap中的一个静态内部类。保存了key-value键值对与下一个节点所在内存位置。为了避免重复计算，使用了final int hash保存了该键值对的hash值，且还重写了hashCode与equals函数，hashCode采用key^value异或的方式。使得计算出来的hash值重复的概率大大减小。对象更能平均分配到数组中去
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; }
//重写了hashCode函数，采用key^value异或的方式。使得hash值重复的概率大大减小
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;
}
}复制
构造函数看完了之后，咱们在看看当我们进行put操作时，HashMap是如何高效的进行插入操作的。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);//调用了putVal操作
}
//真正进行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;//当数组没有初始化时，这里进行初始化。调用的方法为resize()
if ((p = tab[i = (n - 1) & hash]) == null)//这里对key进行hash运算，得到数组下标。第一次放入的时候肯定会走这里
tab[i] = newNode(hash, key, value, null);
else {//调用put操作时，如果该位置不存在数组元素时，即未发生哈希冲突时，不会走该方法。
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;
}复制
我们看源码时，需要有思绪的去看，不要从上往下，每一行都要弄清楚。这样很容易就把自己绕晕了，有些代码，只要大概了解是干嘛的就行了，就像我们最初猜测的，hashMap既然是由数组+链表的方式构成的。那么转换成代码，肯定是先有数组，有了数组之后，再是计算hash。最后是放入对象。那么肯定得有一个初始化的过程，从上面的构造函数来看，当我们调用无参构造函数时，数组是没有进行初始化的，那putVal()这个方法里面肯定有初始化的过程。查看，发现里面有一个resize()。对数组进行扩容的方法。这个方法除了最初进行过初始化之外。在数组容量达到了扩容的时候会调用。稍后会分析详细该方法。
if ((p = tab[i = (n - 1) & hash]) == null)//这里对key进行hash运算，得到数组下标。第一次放入的时候肯定会走这里
tab[i] = newNode(hash, key, value, null);
else {
。。。。
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;复制
我们看该方法，调用put操作时，如果该位置不存在数组元素时，即未发生哈希冲突时，是不会走else部分的。然后是++modCount,++size。改变map的大小，threshold为 加载因子*数组容量的值。进行判断，如果此时的数组容量达到了扩容条件，则对数组进行扩容。
注：扩容
HashMap中，扩容是一个比较耗时的操作，极其影响性能，所以何时进行扩容是一个关键。因为扩容时，数组长度变了，需要重新根据原有元素的hash值对新数组通过哈希函数计算出在新数组的位置。故加载因子是一个很重要的参数，设置的太大，发生碰撞的概率也会随之变大，设置小了，经常扩容，影响性能。hashMap默认的加载因子为0.75。即当元素个数达到数组长度的3/4的时候开始扩容。且是双倍扩容。有人可能会问，为什么是双倍扩容呢？因为我们前面说过，HashMap中数组的长度一定为2次幂。也是数组长度只能为2,4,8,16,32,64,128…等。至于原因，下面会详细讲解
回到刚刚的问题。HashMap中数组的长度为什么一定为2次幂？
要回答这个问题，我们就要知道，HashMap中，哈希函数是怎样的。我们都知道，要往一个已知长度的数组中放入数据，若长度为16，那么下标只能在0~15之间，否则就会发生数组下标越界问题。我们要做的就是根据key生成1 ~ 15这堆数字即可。很多人的第一反应就是求余。即使用任意数对16求余即可。还有一种，按位与，要得到0~15，直接使用任意数对15（length-1）进行位算也能得到。对于计算机来说，位运算的性能明显高于求余运算。所以java自然也就取的是位运算了。既然选择了高效，取了位运算，剩下的问题就是如何将运算结果尽可能的分布到每一个数组下标中。减少哈希碰撞的概率。
举个例子：要将{102,103,104,105,106,107,108}放入一个容量大小为8的数组中。分别对10和7按位运算
{102,103,104,105,106,107,108}对10按位与可得到：{2,2,8,8,10,10,8}
{102,103,104,105,106,107,108}对7按位与可得到：{6,7,0,1,2,3,4}
从这两组数据可以看出，当我们用10按位与时，哈希发生碰撞的次数为三次。而如果是7的话，则碰撞次数为0。也就意味着如果对7按位与的话，一次碰撞都未发生。之所以会之所以会这样，是因为&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=7这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
最后，我们来看看，HashMap中的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;
}复制get()方法就比较简单了。先根据key求得hash取到数组下标，判断当前key与当前元素是否相等，相等的话直接返回Node即可。
总结
HashMap作为jdk中重要的数据结构，有很多设计思想是值得我们学习的，比如说为追求更高效，使用位运算代替了求余运算，1.8之后，针对链表部分还引入了二叉树和红黑树，种种优化使得hashMap越来越高效。当然，本篇幅只是针对HashMap源码做了一个简单的介绍，更详细的希望大家也花点时间自己看一遍源码，比如说扩容时，新老数组是如何进行替换的，为什么从学习JAVA的第一天，就强调重写equals时一定要重写hasCode方法。所有这些问题，去看一遍源码即可得到解惑。
