HashMap

常见Map类

简述：HashMap是非线程安全的，如需要线程安全的哈希隐射类，应使用实现了分段锁（1.8）的ConcurrentHashMap，而不建议使用遗留类HashTable（HashTable实现线程安全是依靠用synchronized关键字修饰put/get方法，效率较低）。

如果需要保存记录插入的顺序，可使用LinkHashMap()，其内部实现了一个双向链表，即每个节点本身记录了前后节点的引用。(btw:MessageQueue是单链表)

(1) HashMap：

它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以使用ConcurrentHashMap（synchronizedMap与HashTable都因为其实现的线程安全依靠全表锁导致性能较差，故不建议）。

(2) 不推荐的线程安全Map：

(2.1)HashTable

​ Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，HashTable的get/put方法都被synchronized关键字修饰，说明它们是方法级别阻塞的，它们占用共享资源锁，所以导致同时只能一个线程操作get或者put，而且get/put操作不能同时执行，所以这种同步的集合效率非常低，一般不建议使用这个集合。

(2.2)SynchronizedMap

​ Collections.synchronizedMap类似，如果传入的是 HashMap 对象，其实也是对 HashMap 做的方法做了一层包装，里面使用对象锁来保证多线程场景下操作安全，本质也是对 HashMap 进行全表锁！，性能低下

(3) ConcurrentHashMap:

这个也是最推荐使用的线程安全的Map，也是实现方式最复杂的一个集合，每个版本的实现方式也不一样，在jdk8之前是使用分段加锁的一个方式，分成16个segment，每次只加锁其中一个segment，而在jdk8加入了红黑树和CAS算法后，又改用synchronized锁住哈希数组的头结点作为线程安全来实现。

(4) LinkedHashMap：

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(5) TreeMap：

TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

HashMap原理

通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

(1) 存储结构：

从源码可知，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对象。

(2) 哈希冲突：

HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题
Java中HashMap采用了**链地址法(拉链法)**。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。（1.8之后又加入了红黑树）

(3)位置确定：

hashCode高低16位相异或后跟n-1相与

简述：取Key的32位hashCode值进行低16位与高16位异或运算，并将运算结果取模(n-1)。

这里插一句：由于index是取模(n-1)的，所以JDK1.8后 n -> 2n 扩容时无需重新hash，只需要把多出来的一个bit作为是否移动到新开辟空间的标记即可

分两步：

第一步：hashCode高低16位异或

hash = (hashCode >>> 16) ^ hashcode)。 这一步得出低16位与高16位的异或结果，也就是为了高低16位都能参与到后一步的取模运算。

第二步：与n-1相与

hash & (n - 1)

(4) 扩容

扩容时机：
put插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。每次扩容的容量都是之前容量的2倍。最大(2^30)。

初始值：

• capacity 即容量，默认16。

• loadFactor 加载因子，默认是0.75 threshold 阈值。

• threshhold阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

• 如果某个桶内的元素超过8个，则会将链表转化成红黑树，加快数据查询效率。

• 如果remove的过程中，桶内的元素低于6个，红黑树又会转化成链表

扩容机制：

简述：

JDK1.7：创建一个新的两倍大小的数组，将原数组用头插法的方式将所有节点rehash后插入新数组，故链表顺序会相反。

JDK1.8：创建一个新的两倍大小的数组，每一个元素通过hash转换坐标的方法计算后，最高位是0则坐标不变，最高位是1则坐标变为“原长度+原坐标”。迁移元素时是正序的，不会出现链表转置的发生。，

详解：

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

我们分析下resize的源码，鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用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);//修改阈值
}

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

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冲突的话），这一点和Jdk1.8有区别，下文详解。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的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.8扩容做了优化，不再需要重新全部rehash，而是根据hash值新增的那个bit是1还是0就好了，省下了hash时间， 同时还可以借由新增的1bit是随机的，而均匀地把之前冲突的节点重新打散了
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了

我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

（注意看，蓝色的为新增1bit为0的情况，保持原index不动，绿色的为新增1bit为1，会移动到16(oldCap) + 15(srcIndex)的位置上）

JDK1.8省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了

JDK8的元素迁移

JDK8则因为巧妙的设计，性能有了大大的提升：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：

数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。如下图（扩容16 -> 32）：

因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了。

(5)Get

通过hashCode高低16位相异或后跟n-1相与，得出的数组位置index，如该位置是目标则直接返回，如该位置是链表节点则链表方式索引，如果是红黑树则以红黑树的方式索引。

(6)Put

也是先通过hashCode与当前数组长度n-1计算出index，然后判断该位置是否为空，为空则直接插入元素；如果该位置只有一个元素则转化为链表并插入；如果该位置为链表节点则以尾插法的方式插入新增节点；如果该位置为红黑树，则以红黑树的方式插入新增节点。

插入后，超过阈值则扩容。

ConcurrentHashMap原理

简述：concurrentHashMap在JDK1.7之前是分段锁，也就是在存储方面是一个 Segment 数组，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，相当于是把整个哈希表分割成了ssize个segment数组，增删时通过对对应的segment加锁，达到只锁一段不影响其他segment的效果；同时也为每个节点Node的val和next都使用了volatile关键字保证可见性。

JDK1.8之后保留了Node节点的val和next字段的volatile关键字，不再使用Segment分段锁，而是以table数组对应index的结点作为synchronized的锁。

ConcurrentHashMap保证线程安全主要有三个地方。

• 一、使用volatile保证当Node中的值变化时对于其他线程是可见的
• 二、当对应index结点为null时（未有哈希冲突），使用CAS操作来保证数据能正确的写入
• 三、其他情况（即链表/红黑树）使用table数组的头结点（链表或树的头结点）作为synchronized的锁来保证写操作的安全

put

大体思路：

• 如果table数组还没有初始化，则使用CAS进行初始化
• 如果table数组中i位置处元素为空，则使用CAS将table[i]的值设置为value
• 如果其他线程正在对table数组进行扩容，则当前线程去协助其进行扩容
• 其他情况，则使用synchronized锁住**table[i]这个元素（链表表头或红黑树根节点**），并将元素追加插入到链表或红黑树中；插入后，检查是否需要将该桶的数据结构由链表转化为红黑树。
• 成功设置<key, value>后，检查是否需要进行扩容

要想对链表或红黑树进行put操作，必须拿到表头或根节点，所以，锁住了表头或根节点，就相当于锁住了整个链表或者整棵树。这个设计与分段锁的思想一致，只是其他读取操作需要用cas来保证。

Get

get简单很多，由于get在Node.val值被volatile修饰的情况下不需要考虑加锁，所以只需要正常检索即可。也就是通过hashCode高低16位相异或后跟n-1相与，得出的数组位置index，如该位置是目标则直接返回，如该位置是链表节点则链表方式索引，如果是红黑树则以红黑树的方式索引。

• 扩容中，且当前index位置未完成扩容的，由于扩容过程是形成hn和ln复制链而非剪切的，故原位置仍可正常访问。
• 扩容中，且当前index已完成扩容的，由于迁移过程中每移动完一个hash桶原地会留下新地址的头结点，以该头节点进行索引即可。

Size

至于size()方法在JDK1.8版本中，对于size的计算，在扩容和addCount()方法就已经有处理了，JDK1.7是在调用size()方法才去计算

Transfer扩容

(ConcurrentHashMap1.8 - 扩容详解_ZOKEKAI的博客-CSDN博客_concurrenthashmap 扩容

多线程协同扩容；index的计算依然与JDK1.8一样，是依靠新增的1bit为0则留在原index，为1则迁移到index + 原数组长度。