其他更多java基础文章：
java基础学习(目录)
本文将不讲红黑树相关的内容，因为我自己也还没弄懂，下一步将算法和数据结构看完后，会写一篇源码分析（二）作为后续。
摘要
HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别，深入探讨HashMap的结构实现和功能原理。
简介
Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：
image
下面针对各个实现类的特点做一些说明：
(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。
内部实现
搞清楚HashMap，首先需要知道HashMap是什么，即它的存储结构-字段；其次弄明白它能干什么，即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。
存储结构
从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。
HashMap结构图
字段
我们先了解一下HashMap的基础字段和属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认table容量16
static final int MAXIMUM_CAPACITY = 1 << 30; //容量最大值为2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子
static final int MIN_TREEIFY_CAPACITY = 64; //最小使用红黑树的容量
transient Node<K,V>[] table;//用于存放Node的数组
transient int size; //hashmap实际存储的Node(键值对)个数
transient int modCount; //记录HashMap内部结构发生变化的次数
int threshold; //HashMap所能容纳的最大数据量的Node(键值对)个数
final float loadFactor;//负载因子
HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。
Node[] table的初始化长度length(默认值是16)，loadFactor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
方法细节
定位哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是“数组+链表+红黑树”的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表/红黑树，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。下面是定位哈希桶数组的源码：
// 代码1
static final int hash(Object key) { // 计算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代码2
int n = tab.length;
// 将(tab.length - 1) 与 hash值进行&运算
int index = (n - 1) & hash;
整个过程本质上就是三步：
- 拿到key的hashCode值
- 将hashCode的高位参与运算，重新计算hash值
- 将计算出来的hash值与(table.length - 1)进行&运算
对于任意给定的对象，只要它的hashCode()返回值相同，那么计算得到的hash值总是相同的。为了使元素在数组桶table里分布均匀一点，我们首先想到的就是把hash值对table长度取模运算
但是模运算消耗还是比较大的，我们知道计算机比较快的运算为位运算，因此JDK团队对取模运算进行了优化，使用上面代码2的位与运算来代替模运算。这个方法非常巧妙，它通过 “(table.length -1) & h” 来得到该对象的索引位置，这个优化是基于以下公式：x mod 2^n = x & (2^n - 1)。我们知道HashMap底层数组的长度总是2的n次方，并且取模运算为“h mod table.length”，对应上面的公式，可以得到该运算等同于“h mod table.length = h & (table.length - 1)”。这是HashMap在速度上的优化，因为&比%具有更高的效率。
在JDK1.8的实现中，还优化了高位运算的算法，将hashCode的高16位与hashCode进行异或运算，主要是为了在table的length较小的时候，让高位也参与运算，并且不会有太大的开销。
下图是一个简单的例子，table长度为16：
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table是否为空或者length等于0, 如果是则调用resize方法进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过hash值计算索引位置, 如果table表该索引位置节点为空则新增一个
if ((p = tab[i = (n - 1) & hash]) == null)// 将索引位置的头节点赋值给p
tab[i] = newNode(hash, key, value, null);
else { // table表该索引位置不为空
Node<K,V> e; K k;
if (p.hash == hash && // 判断p节点的hash值和key值是否跟传入的hash值和key值相等
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果相等, 则p节点即为要查找的目标节点，赋值给e
// 判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 走到这代表p节点为普通链表节点
for (int binCount = 0; ; ++binCount) { // 遍历此链表, binCount用于统计节点数
if ((e = p.next) == null) { // p.next为空代表不存在目标节点则新增一个节点插入链表尾部
p.next = newNode(hash, key, value, null);
// 计算节点是否超过8个, 减一是因为循环是从p节点的下一个节点开始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);// 如果超过8个，调用treeifyBin方法将该链表转换为红黑树
break;
}
if (e.hash == hash && // e节点的hash值和key值都与传入的相等, 则e即为目标节点,跳出循环
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一个节点
}
}
// e不为空则代表根据传入的hash值和key值查找到了节点,将该节点的value覆盖,返回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
if (++size > threshold) // 插入节点后超过阈值则进行扩容
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
- 校验table是否为空或者length等于0，如果是则调用resize方法进行初始化
- 通过hash值计算索引位置，将该索引位置的头节点赋值给p节点，如果该索引位置节点为空则使用传入的参数新增一个节点并放在该索引位置
- 判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点
- 如果p节点不是目标节点，则判断p节点是否为TreeNode，如果是则调用红黑树的putTreeVal方法查找目标节点
- 走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，并定义变量binCount来统计该链表的节点数
- 如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部，并校验节点数是否超过8个，如果超过则调用treeifyBin方法将链表节点转为红黑树节点
- 如果遍历的e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环
- 如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue
- 如果插入节点后节点数超过阈值，则调用resize方法进行扩容
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) { // 老table不为空
if (oldCap >= MAXIMUM_CAPACITY) { // 老table的容量超过最大容量值
threshold = Integer.MAX_VALUE; // 设置阈值为Integer.MAX_VALUE
return oldTab;
}
// 如果容量*2<最大容量并且>=16, 则将阈值设置为原来的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 老表的容量为0, 老表的阈值大于0, 是因为初始容量被放入阈值
newCap = oldThr; // 则将新表的容量设置为老表的阈值
else { // 老表的容量为0, 老表的阈值为0, 则为空表，设置默认容量和阈值
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; // 将当前阈值赋值为刚计算出来的新的阈值
@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) { // 将索引值为j的老表头节点赋值给e
oldTab[j] = null; // 将老表的节点设置为空, 以便垃圾收集器回收空间
// 如果e.next为空, 则代表老表的该位置只有1个节点,
// 通过hash值计算新表的索引位置, 直接将该节点放在该位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 调用treeNode的hash分布(跟下面最后一个else的内容几乎相同)
((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; // 存储索引位置为:原索引+oldCap的节点
Node<K,V> next;
do {
next = e.next;
//如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样
if ((e.hash & oldCap) == 0) {
if (loTail == null) // 如果loTail为空, 代表该节点为第一个节点
loHead = e; // 则将loHead赋值为第一个节点
else
loTail.next = e; // 否则将节点添加在loTail后面
loTail = e; // 并将loTail赋值为新增的节点
}
//如果e的hash值与老表的容量进行与运算为1,则扩容后的索引位置为:老表的索引位置＋oldCap
else {
if (hiTail == null) // 如果hiTail为空, 代表该节点为第一个节点
hiHead = e; // 则将hiHead赋值为第一个节点
else
hiTail.next = e; // 否则将节点添加在hiTail后面
hiTail = e; // 并将hiTail赋值为新增的节点
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null; // 最后一个节点的next设为空
newTab[j] = loHead; // 将原索引位置的节点设置为对应的头结点
}
if (hiTail != null) {
hiTail.next = null; // 最后一个节点的next设为空
newTab[j + oldCap] = hiHead; // 将索引位置为原索引+oldCap的节点设置为对应的头结点
}
}
}
}
}
return newTab;
}
- 如果老表的容量大于0，判断老表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX_VALUE，并直接返回老表（此时oldCap * 2比Integer.MAX_VALUE大，因此无法进行重新分布，只是单纯的将阈值扩容到最大）；如果容量 * 2小于最大容量并且不小于16，则将阈值设置为原来的两倍。
- 如果老表的容量为0，老表的阈值大于0，这种情况是传了容量的new方法创建的空表，将新表的容量设置为老表的阈值（这种情况发生在新创建的HashMap第一次put时，该HashMap初始化的时候传了初始容量，由于HashMap并没有capacity变量来存放容量值，因此传进来的初始容量是存放在threshold变量上（查看HashMap(int initialCapacity, float loadFactor)方法），因此此时老表的threshold的值就是我们要新创建的HashMap的capacity，所以将新表的容量设置为老表的阈值。
- 如果老表的容量为0，老表的阈值为0，这种情况是没有传容量的new方法创建的空表，将阈值和容量设置为默认值。
- 如果新表的阈值为空，则通过新的容量 * 负载因子获得阈值（这种情况是初始化的时候传了初始容量，跟第2点相同情况，也只有走到第2点才会走到该情况）。
- 将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将当前的表设置为新定义的表。
- 如果老表不为空，则需遍历所有节点，将节点赋值给新表。
- 将老表上索引为j的头结点赋值给e节点，并将老表上索引为j的节点设置为空。
- 如果e的next节点为空，则代表老表的该位置只有1个节点，通过hash值计算新表的索引位置，直接将该节点放在新表的该位置上。
- 如果e的next节点不为空，并且e为TreeNode，则调用split方法进行hash分布。
- 如果e的next节点不为空，并且e为普通的链表节点，则进行普通的hash分布。
- 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算为0，则说明e节点扩容后的索引位置跟老表的索引位置一样，进行链表拼接操作：如果loTail为空，代表该节点为第一个节点，则将loHead赋值为该节点；否则将节点添加在loTail后面，并将loTail赋值为新增的节点。
- 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16为0000 0000 0001 0000）进行位与运算不为0，则说明e节点扩容后的索引位置为：老表的索引位置＋oldCap，进行链表拼接操作：如果hiTail为空，代表该节点为第一个节点，则将hiHead赋值为该节点；否则将节点添加在hiTail后面，并将hiTail赋值为新增的节点。
- 老表节点重新hash分布在新表结束后，如果loTail不为空（说明老表的数据有分布到新表上原索引位置的节点），则将最后一个节点的next设为空，并将新表上原索引位置的节点设置为对应的头结点；如果hiTail不为空（说明老表的数据有分布到新表上原索引+oldCap位置的节点），则将最后一个节点的next设为空，并将新表上索引位置为原索引+oldCap的节点设置为对应的头结点。
- 返回新表。
看完之后可能有个疑问，为什么扩容后，节点的hash为什么只可能分布在原索引位置与原索引+oldCap位置？
我们来梳理一下，索引位置的计算主要有三步：取key的hashCode值、高位运算、取模运算。当我们Node点不变时，第一第二步得到的结果hashcode是不变的，那么变化就在最后的取模运算h & (table.length - 1)。我们知道数组桶table的扩容是2的倍数。举个例子，假设老表的容量为16，即oldCap=16，此时的table.length-1为01111（其余高位0省略），扩容后新表容量为16*2=32。扩容后的table.length-1为11111（其余高位0省略）。此时的差异就在倒数第五位的数值。如果hashcode在倒数第5位为0（下图b的key1），则扩容后进行取模运算时，位置不变。反之如果hashcode在倒数第5位为1（下图b的key2），则与相比原来，增加了2^5（16），也就是oldCap的数值。
这就是JDK1.8相对于JDK1.7做的优化，顺便提一下在JDK1.7中的逻辑，因为这部分有不少细节改动。
resize（JDK1.7）
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //！！将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话）。
下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。
JDK1.7扩容逻辑
由此可以看出，JDK1.8的扩容并不会导致链表顺序的倒序。而且JDK1.7扩容时导致的倒序还会在并发的多线程使用场景中使用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;
// table不为空 && table长度大于0 && table索引位置(根据hash值计算出)不为空
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; // first的key等于传入的key则返回first对象
if ((e = first.next) != null) { // 向下遍历
if (first instanceof TreeNode) // 判断是否为TreeNode
// 如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 走到这代表节点为链表节点
do { // 向下遍历链表, 直至找到节点的key和传入的key相等时,返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null; // 找不到符合的返回空
}
- 先对table进行校验，校验是否为空，length是否大于0
- 使用table.length - 1和hash值进行位与运算，得出在table上的索引位置，将该索引位置的节点赋值给first节点，校验该索引位置是否为空
- 检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
- 如果first的next节点不为空则继续遍历
- 如果first节点为TreeNode，则调用getTreeNode方法（见下文代码块1）查找目标节点
- 如果first节点不为TreeNode，则调用普通的遍历链表方法查找目标节点
- 如果查找不到目标节点则返回空
安全性
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的，主要有两个方面：
1. put的时候多线程导致的数据不一致
比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的 hash桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
2. resize而引起死循环（JDK1.8已经不会出现该问题）
这种情况发生在JDK1.7 中HashMap自动扩容时，当2个线程同时检测到元素个数超过 数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize()，两个线程同时修改一个链表结构会产生一个循环链表（JDK1.7中，会出现resize前后元素顺序倒置的情况）。接下来再想通过get()获取某一个元素，就会出现死循环。
下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下：
public class HashMapInfiniteLoop {
private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);
public static void main(String[] args) {
map.put(5， "C");
new Thread("Thread1") {
public void run() {
map.put(7, "B");
System.out.println(map);
};
}.start();
new Thread("Thread2") {
public void run() {
map.put(3, "A");
System.out.println(map);
};
}.start();
}
}
其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
1.7和1.8的对比
HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化，总体性能优于JDK1.7。具体我就不在这方面赘述了，可以看下美团大佬的文章，里面有测试Java 8系列之重新认识HashMap
HashMap和HashTable对比
- HashMap允许key和value为null，Hashtable不允许。
- HashMap的默认初始容量为16，Hashtable为11。
- HashMap的扩容为原来的2倍，Hashtable的扩容为原来的2倍加1。
- HashMap是非线程安全的，Hashtable是线程安全的。
- HashMap的hash值重新计算过，Hashtable直接使用hashCode。
- HashMap去掉了Hashtable中的contains方法。
- HashMap继承自AbstractMap类，Hashtable继承自Dictionary类。
总结
- HashMap的底层是个Node数组（Node<K,V>[] table），在数组的具体索引位置，如果存在多个节点，则可能是以链表或红黑树的形式存在。
- 增加、删除、查找键值对时，定位到哈希桶数组的位置是很关键的一步，源码中是通过下面3个操作来完成这一步：1）拿到key的hashCode值；2）将hashCode的高位参与运算，重新计算hash值；3）将计算出来的hash值与(table.length - 1)进行&运算。
- HashMap的默认初始容量（capacity）是16，capacity必须为2的幂次方；默认负载因子（load factor）是0.75；实际能存放的节点个数（threshold，即触发扩容的阈值）= capacity * load factor。
- HashMap在触发扩容后，阈值会变为原来的2倍，并且会进行重hash，重hash后索引位置index的节点的新分布位置最多只有两个：原索引位置或原索引+oldCap位置。例如capacity为16，索引位置5的节点扩容后，只可能分布在新报索引位置5和索引位置21（5+16）。
- 当同一个索引位置的节点在增加后达到9个时，会触发链表节点（Node）转红黑树节点（TreeNode，间接继承Node），转成红黑树节点后，其实链表的结构还存在，通过next属性维持。链表节点转红黑树节点的具体方法为源码中的treeifyBin(Node<K,V>[] tab, int hash)方法。
- 当同一个索引位置的节点在移除后达到6个时，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。红黑树节点转链表节点的具体方法为源码中的untreeify(HashMap<K,V> map)方法。
HashMap在JDK1.8之后不再有死循环的问题，JDK1.8之前存在死循环的根本原因是在扩容后同一索引位置的节点顺序会反掉。 - 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
- 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
- HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
网友评论