我们知道在Java 8中对于HashMap引入了红黑树从而提高操作性能，由于在上一节我们已经通过图解方式分析了红黑树原理，所以在接下来我们将更多精力投入到解析原理而不是算法本身，HashMap在Java中是使用比较频繁的键值对数据类型，所以我们非常有必要详细去分析背后的具体实现原理，无论是C#还是Java原理解析，从不打算一行行代码解释，我认为最重要的是设计思路，重要的地方可能会多啰嗦两句。
HashMap原理分析
我们由浅入深，循序渐进，首先了解下在HashMap中定义的几个属性，稍后会进一步讲解为何要定义这个值，难道是靠拍脑袋吗。
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
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;
}
构造函数分析
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
当实例化HashMap时，我们不指定任何参数，此时定义负载因子为0.75f
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
当实例化HashMap时，我们也可以指定初始化容量，此时默认负载因子仍为0.75f。
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);
}
当实例化HashMap时，我们既指定默认初始化容量，也可指定负载因子，很显然初始化容量不能小于0，否则抛出异常，若初始化容量超过定义的最大容量，则将定义的最大容量赋值与初始化容量，对于负载因子不能小于或等于0，否则抛出异常。接下来根据提供的初始化容量设置阈值，我们接下来看看上述tableSizeFor方法实现。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
这个方法是在做什么处理呢？阈值 = 2的次幂大于初始化容量的最小值。 到学习java目前为止，我们接触到了模运算【%】、按位左移【<<】、按位右移【>>】，这里我们将学习到按位或运算【|】、无符号按位右移【>>>】。按位或运算就是二进制有1，结果就为1，否则为0，而无符号按位右移只是高位无正负之分而已。不要看到上述【n | = n >>> 1】一脸懵，实际上就是【n = n | n >>> 1】，和我们正常进行四则运算一个道理，只不过是逻辑运算和位运算符号不同而已罢了。我们通过如下例子来说明上述结论，假设初始化容量为5，接下来我们进行如上运算。
0000 0000 0000 0000 0000 0000 0000 0101 cap = 5
0000 0000 0000 0000 0000 0000 0000 0100 n = cap - 1
0000 0000 0000 0000 0000 0000 0000 0010 n >>> 1
0000 0000 0000 0000 0000 0000 0000 0110 n |= n >>> 1
0000 0000 0000 0000 0000 0000 0000 0001 n >>> 2
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 2
0000 0000 0000 0000 0000 0000 0000 0000 n >>> 4
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 4
0000 0000 0000 0000 0000 0000 0000 0000 n >>> 8
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 8
0000 0000 0000 0000 0000 0000 0000 0000 n >>> 16
0000 0000 0000 0000 0000 0000 0000 0111 n |= n >>> 16
如上最终算出来结果为7，然后加上最初计算时减去的1，所以对于初始化容量为5的最小2次幂为8，也就是阈值为8，要是初始化容量为8，那么阈值也为8。接下来到了我们的重点插入操作。
插入原理分析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
上述插入操作简短一行代码，只不过是调用了putVal方法，但是我们注意到首先计算了键的哈希值，我们看看该方法实现。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
直接理解方法大意是：若传入的键为空，则哈希值为0，否则直接调用键的本地hashCode方法获取哈希值，然后对其按位向右移16位，最后进行按位异或（只要不同结果就为1）操作。好像还是不懂，我们暂且搁置一下，我们继续看看插入方法具体实现。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 步骤【1】：tab为空扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤【2】：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// 步骤【3】：键存在，直接覆盖值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤【4】：若为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 步骤【5】：若为链表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//若链表长度大于8则转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤【6】：超过最大容量进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
我们首先来看来步骤【2】，我们待会再来看步骤【1】实现，我们首先摘抄上述获取键的索引逻辑
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
上述通过计算出键的哈希值并与数组的长度按位与运算，散列算法直接决定键的存储是否分布均匀，否则会发生冲突或碰撞，严重影响性能，所以上述【 (n - 1) & hash 】是发生碰撞的关键所在，难道我们直接调用键的本地hashCode方法获取哈希值不就可以了吗，肯定是不可以的，我们来看一个例子。假设我们通过调用本地的hashCode方法，获取几个键的哈希值为31、63、95，同时默认初始化容量为16。然后调用（n-1 & hash），计算如下：
0000 0000 0000 0000 0000 0000 0001 1111 hash = 31
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15
0000 0000 0000 0000 0000 0000 0011 1111 hash = 63
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15
0000 0000 0000 0000 0000 0000 0111 1111 hash = 95
0000 0000 0000 0000 0000 0000 0000 1111 n - 1
0000 0000 0000 0000 0000 0000 0000 1111 => 15
因为（2 ^ n-1）的低位始终都是1，再按照按位运算（0-1始终为0）所有最终结果都有1111，这就是为什么返回相同索引的原因，因此，尽管我们具有不同的哈希值，但结果却是存储到哈希桶数组相同索引位置。所以为了解决低位根本就没有参与到运算中的问题：通过调用上述hash方法，按位右移16位并异或，解决因低位没有参与运算导致冲突，提高性能。我们继续回到上述步骤【1】，当数组为空，内部是如何进行扩容的呢？我们来看看resize方法实现。
final Node[] resize() {
Node[] 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;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
......
}
由上可知：当实例化HashMap并无参时，此时默认初始化容量为16，默认阈值为12，负载因子为0.75f，当指定参数（初始化容量比如为5），此时初始化容量为8，阈值为8，负载因子为0.75f。否则也指定了负载因子，则以指定负载因子为准。同时当超过容量时，扩容后的容量为原容量的2倍。到这里我们发现一个问题：hashTable中的容量可为奇或偶数，而HashMap中的容量永远都为2的次幂即偶数，为何要这样设计呢？
int index = (n - 1) & hash;
如上为HashMap计算在哈希桶数组中的索引位置，若HashMap中的容量不为2的次幂，此时通过按与运算，索引只能为16或0，这也就意味着将发生更多冲突，也将导致性能很差，本可通过O(1)进行检索，现在需要O(log n)，因为发生冲突时，给定存储桶中的所有节点都将存储在红黑树中，若容量为2的次幂，此时按与运算符将和hashTable中计算索引存储位置的方式等同，如下：
int index = (hash & 0x7FFFFFFF) % tab.length;
按照HashMap计算索引的方式，当我们从2的次幂中减去1时，得到的是一个二进制末位全为1的数字，例如默认初始化容量为16，如果从中减去1，则得到15，其二进制表示形式是1111，此时如果对1111进行任意数字的按位与运算，我们将得到整数的最后4位，换句话说，等价于对16取模，但是除法运算通常是昂贵的运算，也就是说按位运算比取模运算效率更高。到此我们知道HashMap中容量为2的次幂的原因在于：哈希桶数组索引存储采取按位运算而非取模运算，因其效率比取模运算更高。进行完上述扩容后容量、阈值重新计算后，接下来则需要对哈希桶数组重新哈希(rehash)，请继续往下看。
影响HashMap性能因素分析
在讲解上述重新哈希之前，我们需要重头开始进行叙述，直到这里，我们知道HashMap默认初始化容量为16，假如我们有16个元素放入到HashMap中，如果实现了很好的散列算法，那么在哈希桶数组中将在每个存储桶中放入1个元素，在此种情况下，查找元素仅需要1次，如果是HashMap中有256元素，如果实现了很好的散列算法，那么在哈希桶数组中将在每个存储桶中放入16个元素，同理，在此种情况下，查找任何一个元素，最多也只需要16次，到这里我们可以知道，如果HashMap中的哈希桶数组存储的元素增加一倍或几倍，那么在每个存储桶中查找元素的最大时间成本并不会很大，但是，如果持续维持默认容量即16不变，如果每个存储桶中有大量元素，此时，HashMap的映射性能将开始下降。比如现在HashMap中有一千六百万条数据，如果实现了很好的散列算法，将在每个存储桶中分配一百万个元素，也就是说，查找任意元素，最多需要查找一百万次。很显然，我们将存储的元素放大后，将严重影响HashMap性能，那么对此我们有何解决方案呢？让我们回到最初的话题，因为默认存储桶大小为16且当存储的元素条目少时，HashMap性能并未有什么改变，但是当存储桶的数量持续增加时，将影响HashMap性能，这是由于什么原因导致的呢？主要是我们一直在维持容量固定不变，我们却一直增加HashMap中哈希桶数组中存储元素的大小，这完全影响到了时间复杂度。如果我们增加存储桶大小，则当每个存储桶中的总项开始增加时，我们将能够使得每个存储桶中的元素个数保持恒定，并对于查询和插入操作保持O(1)的时间复杂度。那么增加存储桶大小也就是容量的时机是什么时候呢？存储桶的大小（容量）由负载因子决定，负载因子是一种度量，它决定着何时增加存储桶的大小（容量），以便针对查询和插入操作保持O(1)的时间复杂度，因此，何时增加容量的大小取决于乘积（初始化容量 负载因子），所以容量和负载因子是影响HashMap性能的根本因素。我们知道默认负载因子是0.75，也就是百分之75，所以增加容量大小的值为（16 0.75）= 12，这个值我们称之为阈值，也就意味着，在HashMap中存储直到第12个键值对时，都将保持容量为16，等到第13个键值对插入到HashMap中时，其容量大小将由默认的16变为（ 16 * 2）= 32。通过上述计算增加容量大小即阈值的公式，我们从反向角度思考：负载因子比率 = 哈希桶数组中元素个数 / 哈希桶数组桶大小，举个栗子，若默认桶大小为16，当插入第一个元素时，其负载因子比率 = 1 / 16 = 0.0625 > 0.75 吗？若为否无需增加容量，当插入第13个元素时，其负载因子比率 = 13 / 16 = 0.81 > 0.75吗？若为是则需增加容量。讲完这里，我们再来看看重哈希，在讲解为什么要进行重哈希之前，我们需要了解重哈希的概念：重新计算已存储在哈希桶数组中元素的哈希码的过程，当达到阈值时，将其移动到另外一个更大的哈希桶数组中。当存储到哈希桶数组中的元素超过了负载因子的限制时，此时将容量增加一倍并进行重哈希。那么为何要进行重哈希呢？因为容量增加一倍后，如若不处理已存在于哈希桶数组中键值对，那么将容量增加一倍则没有任何意义，同时呢，也是为了保持每一个存储桶中元素保持均匀分布，因为只有将元素均匀的分布到每一个存储桶中才能实现O(1)时间复杂度。接下来我们继续进行重哈希源码分析
总结
本节我们详细讲解了HashMap实现原理细节，一些比较简单的地方就没有再一一分析，文中若有叙述不当或理解错误之处，还望指正，感谢您的阅读
