微信公众号：程序猿小奕
前言
之前讲过一篇关于ArraList文章，ArrayList几大问题，看完还不懂来打我。 今天我们来分析另一个容器HashMap。原因很简单，面试的时候相信99%读者都有被面过HashMap，我也相信大家都知道会用，但是里面蕴含的知识点远远不止put和get那么简单。这里面涉及到Java内存模型问题、线程可见不可见问题、Hash计算问题、链表结构、二进制 &，|，<<,>> 等一系列问题，所以面试常问能考察一个人的技术扎不扎实。
文章较长，请耐心看完，必有收获。
HashMap的数据结构和原理
HashMap由数组和链表组合构成的数据结构。
数组里面每个地方都存了Key-Value这样的实例，在Java 7叫Entry在Java 8中叫Node。因为他本身所有的位置都为null，在put插入的时候会进行hash计算出index值。
比如我put（"orange"，"橘子"），我插入了orange元素，这个时候我们会通过哈希函数计算出插入的位置，假设通过计算出来index是1，则插入结果如下：
HashMap为什么需要链表，链表是什么样子
数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是orange和orang我们都去hash有一定的概率会一样（hash 碰撞），这个时候就需要链表，可以将同一数据放在同一index中。
如上Node源码所示，每个节点保存自身的Hash、key、value、以及下个节点。
新的Entry节点怎么插入链表的
Java 8之前都是头插法。新来的值会取代原有的值，原来在数组中的值，就顺推至链表中了 。
Java 8之后就是尾部插入了。新来的值会直接顺着链表来到链表的尾部。
为什么改为尾部插入？
可能就有人就觉得并没有什么用，真的是这样的嘛？
当然不是了。
因为在HashMap中有扩容机制。HashMap中数组的数量是有限的，数据如果多次插入，到达了其上限就需要扩容了，也就是resize。
那么问题又来了，什么时候resize呢？不急，我们先看一下HashMap的源码。
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}
复制代码由上可知，决定resize的因素有两个：
initialCapacity：HashMap的初始化容量，从源码中可知map的最大容量是1<<30,也就是1左移30位，每左移一位乘以2，所以就是1*2^30=1073741824。loadFactor：负载因子，要大于0，且是非无穷大的数字，默认值为0.75f。就比如当前的容量大小为100，当你存第76个的时候，判断 发现需要进行resize了。
如何进行扩容？
扩容：创建一个新的Entry空数组，长度原数组的2倍。
ReHash：遍历Entry数组，将之前的所有的Entry重新通过hash算法放入到新的数组中。
第二步中需要重新hash，hash公式如下：
Hash的公式---> index = HashCode（Key） & （Length - 1）
由此可知，原来的长度（Length）假设为8，那么新的长度为16进行位运算，结果显而易见是不一样的。
回到之前的问题，java 8为什么改为尾部插入？
假设我们继续使用头插法来使用resize的赋值方式，单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上，但是我们的链表还没有断开，这就导致下面这种情况 ：
如果我们这个时候去取值，就出现了一个问题--无限循环（Infinite Loop）
而在Java 8之后链表有红黑树部分，代码中多了很多【if else】的判断，将原本O(n)降到了O(logn)。
头插法会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
本质：
Java 7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。
HashMap的默认初始化长度是多少？
废话不多说，直接上代码：
static final int EDFAULT_INITIAL_CAPACITY = 1 << 4;
复制代码由上可知，HashMap的初始化长度为16，使用的是位运算，因为位运算比算数计算效率高（在我们初始化的时候在我们初始化的时候，尽量指定初始值大小）。而HashMap的初始化长度为16，是为了服务将key映射到index的算法。
前面提到过先拿到key然后通过hash算法得到的index值。我们先来看看index的计算公式：
index = HashCode(key) & (length - 1)
HashMap的大小为16，则length-1为15，二进制就是1111，不难看出其二进制为全为1，这样index的结果等同于HashCode后几位的值，也就意味着，只要输入的HashCode本身分布均匀，hash算法的结果就是均匀的，实现了均匀分布。比如在Java中，所有的对象都是继承于Object类。Object类中有两个方法equals();、hashCode();，这两个方法都是用来比较两个对象是否相等的。在未重写equals();方法我们是继承了Object的equals();方法，其equals();是比较两个对象的内存地址,而我们new的2个对象内存地址不一样。
- 值对象，
==比较的是两个对象的值， - 引用对象，比较的是两个对象的地址。
之前提到过HashMap是通过key的HashCode去寻找index的，那index一样就形成链表了，也就是说orange和orang的index都可能是2，在一个链表上的。
当get的时候，都是根据key去hash然后计算出index，找到了2，那我怎么找到具体的orange和orang呢？是的，这里使用了equals();方法，如果我们对equals()方法进行重写，一定要对hashCode();方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。不然一个链表的对象发现hashCode都一样。
hashmap为什么是线程不安全的
之前提过HashMap从java 7到java 8中的做了很多优化，对于多线程的情况，我们分开分析，这里先给出结论，然后我们在一步一步进行分析：
在java 7多线程环境下，扩容时可能会造成环形链或数据丢失。
在java 8多线程环境下，可能会发生数据覆盖的情况。
我们先分析java 7多线程的环境。因为在多线程的环境中，HashMap是在扩容时会造成环形链或者导致数据丢失，那么可能是在扩容函数中，在扩容函数中的transfer方法，具体代码如下：
void transfer(Entry[] newTable, boolean rehash) {
//新table的容量
int newCapacity = newTable.length;
//遍历原table
for (Entry<K,V> e : table) {
while(null != e) {
//保存下一次循环的 Entry<K,V>
Entry<K,V> next = e.next;
if (rehash) {
//通过e的key值计算e的hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
//得到e在新table中的插入位置
int i = indexFor(e.hash, newCapacity);
//采用链头插入法将e插入i位置，最后得到的链表相对于原table正好是头尾相反的
e.next = newTable[i];
newTable[i] = e;
//下一次循环
e = next;
}
}
}
复制代码我们先分析一下上面的代码，在对table进行扩容到newTable后，需要将原来的数据转移到newTable中，其中代码中的第10-12行代码中元素进行转移，使用的是头插法（之前我们提到过），链表顺序就会发生翻转。
扩容之前已经具体分析过单线程环境中执行过程如下图：
当 单线程变成多线程环境 时，可能发生如下情景：
- 线程
Thread1在第17行【newTable[i] = e;】（数组中的指针正好要指向链表）挂起，如下图：
- 此时线程
Thread2开始执行了，Thread2能正常执行，并完成resize操作，如下图：
- 由于线程
B已经执行完毕，根据Java内存模型，现在newTable和table中的Entry都是主存中最新值【 Ora1.next=Ora5，Ora4.next=Ora2，Ora2.next=null】，此时再切换到线程Thread1继续执行，就会出现数据【Ora1】和【Ora5】丢失了（环形情况类似），如下图：
在java 8中对HashMap进行了优化 ，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全 。这是为什么呢？
同理，我们依然从代码看起，这里我们就先看一下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;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
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;
}
复制代码注意第6行代码，如果没有hash碰撞则会直接插入元素，我们进行如下操作：
线程Thread1和线程Thread2同时进行put操作，但是当这两条不同的数据hash值相同，且插入位置的数据为null，所以这个时候线程Thread1和Thread2都会进入到第6行代码中。在这种情况下，假如Treand1进入后还未进行数据插入时就挂起了，而Thread2正常运行，也正常插入了数据，然后Thread1获取到了CPU的时间片，此时Thread1不用进行hash判断，而是直接把Thread2插入的数据进行覆盖，这样就导致了Thread2的数据被修改了，也就是线程不安全。
综上所述，HashMap在java 7和java 8中多线程下都是不安全的。
对于HashMap在多线程下不安全的问题，我们改如何解决呢？
有以下三种解决方式：
Collection.SynchronizedMap(Map)
Hashtable
ConcurrentHashMap
Collections.synchronizedMap是如何实现线程安全？
在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex，代码如下：
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
}
复制代码从上方代码可以看出，SynchronizedMap有两种构造器，两种构造器中，Map是必传的，如果在构造器种传入了mutex参数，则将对象 排斥锁赋值并传入。若不传入，默认使用SynchronizedMap的对象，创建出SynchronizedMap之后，对于操作map的方法都使用synchronized修饰，当有线程对其进行操作时，就会进行上锁。这样，其他线程就无法对其进行操作了。
HashTable如何实现线程安全？
相对于HashMap，HashTable是线程安全的，所以HashTable在多线程的环境下也是可以正常使用的，但是效率并不是很好。这是为什么呢？
首先，我们先来看看源码（此处是对数据的操作源码）：
public synchronized V get(Object key) {
Entry<?, ?> tab[] = table;
int hash = key.hasCode();
}
复制代码我们可以看出，因为HashTable在操作数据时，使用的是synchronized修饰符进行修饰的，所以某个线程在操作数据的时候会进行上锁，导致效率比较低下。
HashTable和HashMap的区别
- 实现方式不同：
Hashtable继承了Dictionary类，而HashMap继承的是AbstractMap类 - 初始化容量不同：HashMap的初始容量是16，Hashtable初始化容量为11，但两者的负载因子一致，默认都为0.75。
- 扩容机制不同：当（现有的容量>总容量 * 负载因子），
HashMap直接扩容为（当前容量 * 2），Hashtable则扩容为（当前容量 * 2 + 1）。 - 迭代器不同：
HashMap的Iterator迭代器是使用的快速失败机制(fail-fast)，Hashtable的Enumerator是安全失败机制(fail-safe)。
在Hashtable中使用了安全失败机制(fail-safe)，这种机制使得我们每次在读取数据时不一定为最新数据。这样我tain(key)来对key是否存在进行判断。
Hashtable是不允许键值为null，而在HashMap中键值都可以为空。我们在Hashtable使用put();方法时，当参数为空值会直接抛空指针异常，但是在HashMap中做了特殊处理，如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码fail-fast是什么
fail-fast即快速失败机制，在用迭代器遍历一个集合对象是，如果遍历过程中对集合对象的内容进行了修改（增、删、改）操作，则抛出Concurrent Modification Exception。
因为迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果集合的内容发生改变，就会修改modCount的值。而每次迭代器使用hashNext();或者next();遍历下一个元素之前，都会检测modCount==expectedmodeCount值。若是其结果则返回遍历；否则抛出异常，终止遍历。
注意：因为异常的检测条件是
modCount != expectedmodCount，如果在这个时候发生了修改，使得modCount值和设置的expectedmodCount值相等，就不会抛出异常。
ConcurrentHashMap如何实现线程安全
在ConcurrentHashMap中，Java 7和Java 8版本区别还是挺大的，首先我们先看看Java 7环境。
ConcurrentHashMap是由Segment数组、HashEntry组成的，其实是和HashMap一样，也是【数组+链表】的数据结构。其中Segment是ConcurrentHashMap的一个内部类，具体代码如下：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
// 记得快速失败（fail—fast）么？
transient int modCount;
// 大小
transient int threshold;
// 负载因子
final float loadFactor;
}
复制代码HashEntry和HashMap差不多，只是HashEntry使用了volatile修饰了它的Value和下一个结点next。因为我们都知道volatile有以下三个特性：
- 可见性：保证不同线程对这个变量的操作时的可见性，即一个线程修改了某个变量的值，这个新值对其它的线程是立即可见的。
- 有序性：禁止指令重排（指令重排可能导致代码执行顺秀修改 ）。
- 原子性：保证了 对单次读/写的原子性（
i++这种操作）。
这样就使得ConcurrentHashMap能在多线程的环境下运行。
在java 8中，如果数组+链表的方式，我们在查询的时候，需要遍历链表，这样做的话导致效率低下，
就抛弃了原有的恶Segment分段锁，采用了CAS+sychronized来保证并发的安全性。其中和HashMap类似 ，把之前的HashEntry改成了Node，但是作用不变，通过volatile修饰值和next，保证了其可见性。除此之外，还使用了红黑树，在链表大于一定值（默认为8）的时候会发生转换。因为采用了红黑树可以保证查询的效率，也将ReentrantLock改为了synchronized。
ConcurrentHashMap为什么并发度高
在Java 7环境中，我们从前面看到的Segment源码可以看出，它其实继承于ReentrantLock，即采用了分段锁的技术。这样不会像Hashtable一样，不管是put还是get操作都需要进行同步操作 。每当一个线程占用锁访问一个Segment时，不会影响其他的Segment。所以理论上来说ConcurrentHashMap支持CurrentLevel即Segment数组数量的线程并发，如果Segment的数量为16，其并发度就是16，可以同时允许16个线程操作16个Segment。
ConcurrentHashMap如何存取元素？
在Java 7环境中，我们先看看put操作。先看源码：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
// 遍历该 HashEntry
// 如果不为空则判断传入的 key 和当前遍历的 key 是否相等，
// 相等则覆盖旧的 value。
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}else {
// 不为空则需要新建一个 HashEntry 并加入到 Segment 中，
// 同时会先判断是否需要扩容。
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//释放锁
unlock();
}
return oldValue;
}
复制代码从源码可以看出，put操作有以下两个步骤：
- 尝试获取锁，如果获取锁操作失败说明存在多线程的竞争，这时通过
scanAndLockForPut()自旋来获取锁； - 如果尝试获取锁的次数达到了
MAX_SCAN_RETRIES则改为阻塞锁获取，保证其能成功获取锁（要不然这里一直获取不到，数据也就写不进去了）。
下面我们再分析get操作
- 将
key值通过hash定位到对应的Segment； - 再通过一次
hash定位到对应的元素。
前面我们已经了解到HashEntry中的value属性时用volatile修饰的，因其具有内存可见性的特性，这样就保证了我们每次获取到的都是最新值。
在java 8环境中，同样先分析put操作。put操作主要可以分为以下几个步骤：
- 根据key计算出其
hashcode； - 判断是否需要初始化；
- 为当前的
key定位出对应的Node，如果 为空则写入数据，利用CAS尝试写入，失败则通过自旋保证成功； - 如果 当前位置的
hashcode == MOVE，其中MOVE为-1，则 需要扩容； - 如果都不满足，则利用
synchronized锁写入数据。 - 如果数量大于
TREEFY_THRESHOLD则需要转换为红黑树。
get操作主要有以下三个步骤：
- 根据计算出来的
hashcode找到对应的地址，如果在桶上就直接返回值； - 如果计算出来是红黑树，就按照树的方式获取值；
- 如果不满足，按照链表的方式遍历获取值。
前面我们在分析ConcurrentHashMap的时候提到过CAS，下面我们就来简单分析一下。
CAS是一种乐观锁，也是一种轻量级锁。
CAS主要的流程是线程在读取数据时不用进行加锁，在往回写数据的时候，比较原值和现值是否一致，若一致数据可能（注意，此处是可能会修改，具体原因后面分析）未被修改，则可以将数据写回，若数据不一致数据已经被修改过，则重新执行读取操作。具体流程如下：
前面我们在判断数据一致时，对数据是否被修改抱有疑问。因为其中有一个经典的ABA问题。具体情况是这样的：
有一个线程将数据A改成了B;
这时又来了一个线程将数据改成了A;
这个时候的线程在判断的时候发现它的值时没有发生改变的，但是它的数据已经修改过了。
对于这个ABA的问题，我们有什么方法解决呢？
其实只要加一个修改的标志，比如说版本号，每次修改一次数据，版本号就进行修改，又或者加一个时间戳，每次修改的时间戳都是不一样的，所以我们只需要先对比数据，在数据一致的情况下，在比较一下标志位是否一致，只有两个都一致才说明数据未发生改变。
学习了HashMap数据结构及其这样设计的原因，那么基于HashMap衍生出哪些其他容器呢？它们在使用上有哪些不同点呢？什么场景用什么可能会有什么坑呢？
关注Java核心&面试专栏。后续将会继续分享。
最后
- 文章均原创，原创不易，感谢掘金平台，觉得有收获，帮忙三连，笔芯
- 文章涉及的所有代码、时序图、架构图均共享，可通过公众号留言获取
- 文章若有错误，欢迎评论留言指出，也欢迎转载，麻烦标注下出处就好
近期评论