Everything About HashMap

1.为什么用HashMap？

HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)映射。
HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改。数组是用来确定桶的位置，利用元素的key的hash值对数组长度取模得到. 链表是用来解决hash冲突问题，当出现hash值一样的情形，就在数组上的对应位置形成一条链表。
用LinkedList代替数组结构可以么?

当然是可以的，稍微说明一下，此题的意思是，源码中是这样的

Entry[] table = new Entry[capacity];

Entry就是一个链表节点。 那下面这样表示，是否可行?

List<Entry> table = new LinkedList<Entry>();

答案很明显，是可以的。

既然是可以的,为什么HashMap不用LinkedList,而选用数组?
因为用数组效率最高！在HashMap中，定位桶的位置是利用元素的key的哈希值对数组长度取模得到。此时，我们已得到桶的位置。显然数组的查找效率比LinkedList大。

那ArrayList，底层也是数组，查找也快啊，为啥不用ArrayList?
因为采用基本数组结构，扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。而ArrayList的扩容机制是1.5倍扩容，那ArrayList为什么是1.5倍扩容这就不在本文说明了。
HashMap是非synchronized，所以HashMap很快。
HashMap可以接受null键和值，而Hashtable则不能（原因就是equlas()方法需要对象，因为HashMap是后出的API经过处理才可以）
当链表转为红黑树后，什么时候退化为链表?
为6的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

2.HashMap的工作原理是什么？

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Node。　　

以下是HashMap初始化，简单模拟数据结构

Node[] table=new Node[16]  散列桶初始化，table

　　 class Node {

　　　　hash;//hash值

     key;//键

　　　　value;//值

　　　　node next;//用于指向链表的下一层（产生冲突，用拉链法）

　　 }

`put`过程（JDK1.8版）

对Key用HashCode()求Hash值，然后再计算下标
如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）
如果碰撞了，以链表的方式链接到后面
如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
如果节点已经存在就替换旧值
如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）

扩容后，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变。

`Get过程`(考虑特殊情况如果两个键的hashcode相同，你如何获取值对象？)

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。

3.有什么方法可以减少碰撞？

扰动函数可以减少碰撞，原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）
使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。为什么String, Interger这样的wrapper类适合作为键？因为String是final的，而且已经重写了equals()和hashCode()方法了。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

4.HashMap中hash函数怎么是是实现的?

　　我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，能不能找一种更快速，消耗更小的方式，我们来看看JDK1.8的源码是怎么做的.

static final int hash(Object key) {
    if (key == null){
        return 0;
    }
     int h;
     h=key.hashCode()；返回散列值也就是hashcode
      // ^ ：按位异或
      // >>>:无符号右移，忽略符号位，空位都以0补齐
      //其中n是数组的长度，即Map的数组部分初始化长度
     return  (n-1)&(h ^ (h >>> 16));
}

高16位异或低16位以后，进行取模运算
1.高16bit不变，低16bit和高16bit做了一个异或(得到的HashCode转化为32位的二进制，前16位和后16位低16bit和高16bit做了一个异或)
2.(n·1)&hash=->得到下标

为什么扩容是2的次幂?

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法
这个算法实际就是取模，hash%length。但是，大家都知道这种运算不如位移运算快。
因此，源码中做了优化hash&(length-1)。也就是说hash%length==hash&(length-1)

5.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

6.对红黑树的见解？

节点是红色或黑色。
根节点是黑色。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

7.解决hash 碰撞还有那些办法？

比较出名的有四种 (1)开放定址法 (2)链地址法 (3)再哈希法 (4)公共溢出区域法

开放定址法
开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
链地址法
将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
再哈希法
当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。
建立公共溢出区
将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

下面给一个线性探查法的例子　

问题：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表

解答：为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。

前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。
当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。
当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。
当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。
类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。

8.如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

　　默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为 <原下标+原容量> 的位置　　

9.重新调整HashMap大小存在什么问题吗？

当扩容重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。因为直接插入的效率更高。如果条件竞争发生了，那么就死循环了。(多线程的环境下不使用HashMap）。
为什么多线程会导致死循环，它是怎么发生的？
HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize。1.扩容：创建一个新的Entry空数组，长度是原数组的2倍。2.ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

HashMap 扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。

在HashMap1.7之前是头插法，在扩容的过程中，可能会造成一个resize()的方法，然后调用transfer()方法，把里面的Entry进行了Rehash，在过程中，可能会造成链表的循环，在一下次Get()中出现死循环，或者出现没有加锁，所以数据不安全

10.HashTable

数组 + 链表方式存储
默认容量： 11(质数为宜)

`Put:`

对key的hashCode()做hash运算，计算index; 如果没碰撞直接放到bucket里；如果碰撞了，以链表的形式存在buckets后；如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)；如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity)，就要resize。
索引计算 : （key.hashCode() & 0x7FFFFFFF）% table.length
若在链表中找到了，则替换旧值，若未找到则继续
当总元素个数超过容量*加载因子时，扩容为原来 2 倍并重新散列。
将新元素加到链表头部,对修改 Hashtable 内部共享数据的方法添加了 synchronized，保证线程安全。
Get:
对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回；如果有冲突，则通过key.equals(k)去查找对应的Entry;
• 若为树，则在树中通过key.equals(k)查找，O(logn)；
• 若为链表，则在链表中通过key.equals(k)查找，O(n)。

11.HashMap ，HashTable 区别

默认容量不同。扩容不同
线程安全性，HashTable 安全
效率不同 HashTable 要慢因为加锁

12.可以使用CocurrentHashMap来代替Hashtable吗？

我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

13.CocurrentHashMap（1.8）

其中抛弃了原有的 Segment 分段锁，而采用了CAS + synchronized来保证并发安全性。
其中的 val next 都用了 volatile修饰，保证了可见性
最大特点是引入了 CAS（借助 Unsafe 来实现【native code】）
CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。
CAS 会出现的问题：ABA
解决：对变量增加一个版本号，每次修改，版本号加 1，比较的时候比较版本号。
####Put过程
根据 key 计算出 hashcode 。判断是否需要进行初始化。
通过 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
如果都不满足，则利用 synchronized 锁写入数据。
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

Get过程
根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
如果是红黑树那就按照树的方式获取值。
都不满足那就按照链表的方式遍历获取值。

14.TreeMap

TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和HashMap不同，它的get、put、remove之类操作都是O(logn)的复杂度，具体顺序可以由指定的Comparator来决定，或者根据键的自然顺序来判断

15.hash算法是干嘛的？还知道哪些hash算法？

Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。
比较出名的算法有SHA,MD4、MD5等

说说String中hashcode的实现?

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。

哈希计算公式可以计为

+ s[1]*31^(n-2) + ... + s[n-1]```


* 那为什么以31为质数呢?
主要是因为31是一个奇质数，所以```31*i=32*i-i=(i<<5)-i```，这种位移与减法结合的计算相比一般的运算快很多。

## 16.健可以为Null值么?

可以，key为null的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。

## 17.一般用什么作为HashMap的key?

一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。
• (1) 因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
• (2) 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。

## Hashcode
* 一、hashCode简介
public int hashCode()：``hashCode``是根类Obeject中的方法。默认情况下，Object中的``hashCode() ``返回对象的32位jvm内存地址。也就是说如果对象不重写该方法，则返回相应对象的32为JVM内存地址。
* 二、hashCode注意点
关于hashCode方法，一致的约定是：
1、重写了``euqls``方法的对象必须同时重写``hashCode()``方法。
2、如果两个对象equals相等，那么这两个对象的HashCode一定也相同
3、如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置
* 三、hashCode作用
从Object角度看，JVM每new一个Object，它都会将这个Object丢到一个Hash表中去，这样的话，下次做Object的比较或者取这个对象的时候（读取过程），它会根据对象的HashCode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。若HashCode相同再去调用equal。
HashCode是用于查找使用的，而equals是用于比较两个对象的是否相等的。
* 四、为什么重写
实际开发的过程中在hashmap或者hashset里如果不重写的hashcode和equals方法的话会导致我们存对象的时候，把对象存进去了，取的时候却取不到想要的对象。
重写了hashcode和equals方法可以迅速的在hashmap中找到键的位置；
#### **重写hashcode是为了保证相同的对象会有相同的hashcode；**
#### **重写equals是为了保证在发生冲突的情况下取得到Entry对象（也可以理解是key或是元素）**；


存在一个table数组，里面每个元素都是一个node链表，当添加一个元素（key-value）时，就首先计算元素key的hash值，通过table的长度和key的hash值进行与运算得到一个index，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就把这个元素添加到同一hash值的node链表的链尾，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度大于等于8时，链表就可能转换为红黑树，这样大大提高了查找的效率。

<p><img src="https://img-blog.csdnimg.cn/20191102133424361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM1ODMzMTE=,size_16,color_FFFFFF,t_70" alt="存储结构" /></p>





```Java
static class Node&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; {
        final int hash;
        final K key;
        V value;
        Node&lt;K,V&gt; next; //可以看得出这是一个链表

        Node(int hash, K key, V value, Node&lt;K,V&gt; next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        *
        *
        *
    }

transient Node<K,V>[] table;

HashMap内部包含一个Node类型的数组table，Node由Map.Entry继承而来。

Node存储着键值对。它包含四个字段，从next字段我们可以看出node是一个链表。

table数组中的每个位置都可以当做一个桶，一个桶存放一个链表。

HashMap使用拉链法来解决冲突，同一个存放散列值相同的Node。

数据域

private static final long serialVersionUID = 362498820763181265L;  
// 初始化容量，初始化有16个桶
static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4; // aka 16  
// 最大容量  1 073 741 824, 10亿多
static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;
// 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当put()一个元素到某个桶，其链表长度达到8时有可能将链表转换为红黑树  
static final int TREEIFY_THRESHOLD = 8;  
// 在hashMap扩容时，如果发现链表长度小于等于6，则会由红黑树重新退化为链表。
static final int UNTREEIFY_THRESHOLD = 6;  
// 在转变成红黑树树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换，否者直接扩容。这是为了避免在HashMap建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
static final int MIN_TREEIFY_CAPACITY = 64;  
// 存储元素的数组  
transient Node&lt;k,v&gt;[] table;
// 存放元素的个数
transient int size;
// 被修改的次数fast-fail机制   
transient int modCount;
// 临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容   
int threshold;
// 填充比
final float loadFactor;</code></pre>
<h4 id="构造函数">构造函数</h4>
<pre class="java"><code>public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity &lt; 0)
            throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; +
                                               initialCapacity);
        if (initialCapacity &gt; MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException(&quot;Illegal load factor: &quot; +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // tableSizeFor(initialCapacity)方法计算出接近initialCapacity
        // 参数的2^n来作为初始化容量。
        this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map&lt;? extends K, ? extends V&gt; m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
}

HashMap构造函数允许用户传入容量不是2的n次方，因为它可以自动地将传入的容量转换为2的n次方。

### Put()源码

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
        int h;
        // “扰动函数”。参考 https://www.cnblogs.com/zhengwang/p/8136164.html
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
}    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        HashMap.Node&lt;K,V&gt;[] tab; HashMap.Node&lt;K,V&gt; p; int n, i;
        // 未初始化则初始化table
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 通过table的长度和hash与运算得到一个index，
        // 然后判断table数组下标为index处是否已经存在node。
        if ((p = tab[i = (n - 1) &amp; hash]) == null)
            // 如果table数组下标为index处为空则新创建一个node放在该处
            tab[i] = newNode(hash, key, value, null);
        else {
            // 运行到这代表table数组下标为index处已经存在node，即发生了碰撞
            HashMap.Node&lt;K,V&gt; e; K k;
            // 检查这个node的key是否跟插入的key是否相同。
            if (p.hash == hash &amp;&amp;
                    ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
                e = p;
            // 检查这个node是否已经是一个红黑树
            else if (p instanceof TreeNode)
                // 如果这个node已经是一个红黑树则继续往树种添加节点
                e = ((HashMap.TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 在这里循环遍历node链表

                    // 判断是否到达链表尾
                    if ((e = p.next) == null) {
                        // 到达链表尾，直接把新node插入链表，插入链表尾部，在jdk8之前是头插法
                        p.next = newNode(hash, key, value, null);
                        if (binCount &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 如果node链表的长度大于等于8则可能把这个node转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 检查这个node的key是否跟插入的key是否相同。
                    if (e.hash == hash &amp;&amp;
                            ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 当插入key存在，则更新value值并返回旧value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改次数++
        ++modCount;
        // 如果当前大小大于门限，门限原本是初始容量*0.75
        if (++size &gt; threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

下面简单说下put()流程：
1. 判断键值对数组table[]是否为空或为null，否则以默认大小resize()；
2. 根据键key计算hash值与table的长度进行与运算得到插入的数组索引 index，如果tab[index] == null，直接根据key-value新建node添加，否则转入3
3. 判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

为啥头插法为什么要换成尾插：jdk1.7时候用头插法可能是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到)；找到链表尾部的时间复杂度是 O(n)，或者需要使用额外的内存地址来保存链表尾部的位置，头插法可以节省插入耗时。但是在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。

从putVal()源码可以看出，HashMap并没有对null的键值对做限制（hash值设为0），即HashMap允许插入键尾null的键值对。但在JDK1.8之前HashMap使用第0个node存放键为null的键值对。

确定node下标：通过table的长度和key的hash进行与运算得到一个index。

在转变成红黑树树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换，否者直接扩容。这是为了避免在HashMap建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。

大多数人不知道的：HashMap链表成环的原因和解决方案

get()操作源码解析

public V get(Object key) {
        HashMap.Node&lt;K,V&gt; e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final HashMap.Node&lt;K,V&gt; getNode(int hash, Object key) {
        HashMap.Node&lt;K,V&gt;[] tab; HashMap.Node&lt;K,V&gt; first, e; int n; K k;
        // table不为空
        if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;
                // 通过table的长度和hash与运算得到一个index，table
                // 下标位index处的元素不为空，即元素为node链表
                (first = tab[(n - 1) &amp; hash]) != null) {
            // 首先判断node链表中中第一个节点
            if (first.hash == hash &amp;&amp; // always check first node
                    // 分别判断key为null和key不为null的情况
                    ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))
                // key相等则返回第一个
                return first;
            // 第一个节点key不同且node链表不止包含一个节点
            if ((e = first.next) != null) {
                // 判断node链表是否转为红黑树。
                if (first instanceof HashMap.TreeNode)
                    // 则在红黑树中进行查找。
                    return ((HashMap.TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
                do {
                    // 循环遍历node链表中的节点，判断key是否相等
                    if (e.hash == hash &amp;&amp;
                            ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        // key在table中不存在则返回null。
        return null;
    }

get(key)方法首先获取key的hash值，
计算hash & (table.len - 1)得到在链表数组中的位置，
先判断node链表（桶）中的第一个节点的key是否与参数key相等，
不等则判断是否已经转为红黑树，若转为红黑树则在红黑树中查找，
如没有转为红黑树就遍历后面的链表找到相同的key值返回对应的Value值即可。

resize()操作源码解析

// 初始化或者扩容之后的元素调整
    final HashMap.Node&lt;K,V&gt;[] resize() {
        // 获取旧table
        HashMap.Node&lt;K,V&gt;[] oldTab = table;
        // 旧table容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 旧table扩容临界值
        int oldThr = threshold;
        // 定义新table容量和临界值
        int newCap, newThr = 0;
        // 如果原table不为空
        if (oldCap &gt; 0) {
            // 如果table容量达到最大值，则修改临界值为Integer.MAX_VALUE
            // MAXIMUM_CAPACITY = 1 &lt;&lt; 30;
            // Integer.MAX_VALUE = 1 &lt;&lt; 31 - 1;
            if (oldCap &gt;= MAXIMUM_CAPACITY) {
                // Map达到最大容量，这时还要向map中放数据，则直接设置临界值为整数的最大值
                // 在容量没有达到最大值之前不会再resize。
                threshold = Integer.MAX_VALUE;
                // 结束操作
                return oldTab;
            }
            // 下面就是扩容操作（2倍）
            else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp;
                    oldCap &gt;= DEFAULT_INITIAL_CAPACITY)
                // 临界值也变为两倍
                newThr = oldThr &lt;&lt; 1; // double threshold
        }
        else if (oldThr &gt; 0) // initial capacity was placed in threshold
            /*
             * 进入此if证明创建HashMap时用的带参构造：public HashMap(int initialCapacity)
             * 或 public HashMap(int initialCapacity, float loadFactor)
             * 注：带参的构造中initialCapacity（初始容量值）不管是输入几都会通过
             * tableSizeFor(initialCapacity)方法计算出接近initialCapacity
             * 参数的2^n来作为初始化容量。
             * 所以实际创建的容量并不等于设置的初始容量。
             */
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 进入此if证明创建map时用的无参构造：
            // 然后将参数newCap（新的容量）、newThr(新的扩容阀界值)进行初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 进入这代表有两种可能。
            // 1. 说明old table容量大于0但是小于16.
            // 2. 创建HashMap时用的带参构造，根据loadFactor计算临界值。
            float ft = (float)newCap * loadFactor;
            newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        // 修改临界值
        threshold = newThr;
        @SuppressWarnings({&quot;rawtypes&quot;,&quot;unchecked&quot;})
        // 根据新的容量生成新的 table
        HashMap.Node&lt;K,V&gt;[] newTab = (HashMap.Node&lt;K,V&gt;[])new HashMap.Node[newCap];
        // 替换成新的table
        table = newTab;
        // 如果oldTab不为null说明是扩容，否则直接返回newTab
        if (oldTab != null) {
            /* 遍历原来的table */
            for (int j = 0; j &lt; oldCap; ++j) {
                HashMap.Node&lt;K,V&gt; e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 判断这个桶（链表）中就只有一个节点
                    if (e.next == null)
                        // 根据新的容量重新计算在table中的位置index，并把当前元素赋值给他。
                        newTab[e.hash &amp; (newCap - 1)] = e;
                    // 判断这个链表是否已经转为红黑树
                    else if (e instanceof HashMap.TreeNode)
                        // 在split函数中可能由于红黑树的长度小于等于UNTREEIFY_THRESHOLD（6）
                        // 则把红黑树重新转为链表
                        ((HashMap.TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 运行到这里证明桶中有多个节点。
                        HashMap.Node&lt;K,V&gt; loHead = null, loTail = null;
                        HashMap.Node&lt;K,V&gt; hiHead = null, hiTail = null;
                        HashMap.Node&lt;K,V&gt; next;
                        do {
                            // 对桶进行遍历
                            next = e.next;
                            if ((e.hash &amp; oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

HashMap 的工作原理是什么?

HashMap基于hashing原理，我们通过put()和get()方法存储和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来存储值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会存储在链表的第一个节点，链接原先的对象节点，HashMap在每个链表节点中存储键值对对象。

快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么？

1、快速失败（fail-fast）
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行修改（增加、删除、修改），则会抛出Concurrent Modification Exception.
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到modCount!=expectedmodCount这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。
2、安全失败（fail-safe）
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception,但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的
场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

源码导读

HashMap？ConcurrentHashMap？相信看完这篇没人能难住你