Java基础之HashMap底层, HashMap多线程操作导致死循环, ConcurrentHashMap底层, HashTable底层

骑猪看日落 2023-06-22 06:22 6阅读 0赞

# 1. HashMap底层实现原理 #

## 1.1 JDK1.8之前(数组+链表) ##

#### (1) new HashMap ####

*  创建一个空对象, 如果不指定数组长度, 默认数组长度16. 如果指定了数组长度, 会找一个和该数组临近的2的n次方数据作为长度.
 *  数组中存入的是Entry<k, v>的entry对象.
 *  创建的时候还加入了0.75的负载因子. 这个负载因子和扩容rehash()方法有关. 后续详细介绍.

#### (2) map.put(k,v)方法 ####

*  首先,**先判断key存放的位置**, 判断出位置了, 然后将entry对象放到数组对应的位置中.  
    key通过hashcode方法(**hashmap内部的hashcode扰动函数**)算出hash值, 然后通过(数组长度-1)&hash值, 得到一个位于0-15区间的数字, 这就是对应数组中的下标了.
 *  tips: 为什么使用(n-1)&key的hash值呢? (可以不用理解如下解释的这么深, 简单理解就**是为了让hashmap的entry对象在数组中分布更均匀**)
    
    1.  &运算: a&b, a的二进制, b的二进制, 同位进行比较, 当都为1时, 结果才为1, 否则就是0.比较的结果再转为十进制就是十进制结果了.
    2.  保证数组不会越界:  
        首先我们要知道,在HashMap和ConcurrentHashMap中,数组的长度按规定一定是2的幂(2的n次方)因此,数组的长度的二进制形式是:10000…000,1后面有一堆0.那么tab.length - 1 的二进制形式就是01111…111,0后面有一堆1。最高位是0, 和hash值相"与"，结果值一定不会比数组的长度值大,因此也就不会发生数组越界.
    3.  保证元素尽可能的均匀分布  
        在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较.所以,一定要使哈希均匀分布,尽量减少哈希冲突,提高效率.
 *  如果key的hash值相同, 再**通过key的equals()方法去判断**.
    
     *  如果equals()方法为true, 则说明就是同一个key了, value值就会覆盖;
     *  如果equals()方法为false,则不是一个key, 就在数组对应索引位置变为链表存储新Entry<key,value>.
 *  上一步说到的链表是**拉链法**: 将链表和数组相结合.也就是说创建一个链表数组,数组中每一格就是一个链表.若约到哈希冲突,则将冲突的值加到链表中即可.
 *  **插入链表的时候是首插法**, 也就是链表中的新元素排在旧元素前面. 因为都会认为新存入的数据是被应用最多的, 所以新数据排在旧数据前面.  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70]

#### (3) map.get(k)实现原理 ####

*  先调用k的hashCode()方法得出hash值，并通过hash值&(数组长度-1)运算转换成数组的下标。
 *  在通过数组下标快速定位到某个位置上, 这个位置上什么都没有，则返回null.
 *  如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value

## 1.2 JDK1.8之后(数组+链表+红黑树) ##

#### (1) new HashMap ####

*  JDK1.8以后只有在put数据的时候才会创建对象, 而且每个数组中存的是node对象.
 *  如果不指定数组长度, 默认数组长度16. 如果指定了数组长度, 会找一个和该数组临近的2的n次方数据作为长度.
 *  数组中存入的是Node<k, v>的node对象.
 *  创建的时候还加入了0.75的负载因子. 这个负载因子和扩容rehash()方法有关. 后续详细介绍.

#### (1) map.put(k,v)方法 ####

和JDK1.8之前不同的是, 但是这里的链表当达到一定程度后会转为红黑树.

*  如果**链表的长度超过8则转为红黑树**, 也就是该位置存储的是**数组+红黑树**结构.
 *  当**链表长度小于等于6时**又变为链表, 也就是该位置存储的是**数组+链表**结构.
 *  **链表法采用的是尾插法.** 也就是新的元素排在当前元素的后面.
 *  JDK1.8 的时候, 数组中存的是node对象, 而不是entry对象了, node对象包括三部分(如下图所示),  
    ![在这里插入图片描述][2020122517115770.png]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 1]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 2]

#### (3) map.get(k)原理 ####

和JDK1.8之前一样.

## 1.3 HashMap的扩容 ##

*  HashMap的默认数组长度大小是16，负载因子是0.75，当HashMap的元素数量**大于当前数组长度乘以负载因子**就会触发HashMap的扩容机制.也就是当数组中的元素>12时会触发扩容机制.
 *  扩容的大小为2的n次方. 并且对HashMap中的元素进行重新hash,并有部分存到新位置,一部分存到原来的位置,所以说扩容的过程是非常耗费性能的.
 *  首次扩容, 是扩容到原来2倍.
 *  源码上作者给了一张表可以看出当桶中元素达到8个的时候，概率已经非常的小了，也就是说用0.75作为负载因子,每个碰撞位置的连表长度超过8个几乎是不可能的. **HashMap负载因子为0.75是空间可时间成本的一种折中.**

# 2. HashMap线程是否安全? #

HashMap最多只允许**一条**记录的**键**为null,允许**多条**记录的**值**为null.**HashMap非线程安全**,即**任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致**, 并发环境下推荐使用**ConcurrentHashMap**.

# 3. ConcurrentHashMap底层 #

## 3.1 JDK1.7(Segment数组结构和HashEntry数组结构) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 3]  
**JDK 1.7 ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成. 每个Segment都对应一个Hash表, 且都有独立的锁, 所以这样就可以每个线程访问一个Segment, 就可以并行访问了, 从而提高了效率. 这就是锁分段**

*  首先将数据分为一段一段的存储,然后给**每一段数据配一把锁**, 当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问.
 *  Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable{ 
    }

*  一个**ConcurrentHashMap里面包含多个Segment数组**. Segment的结构和HashMap类似, 是一种数组和链表结构. 一个**Segment包含一个HashEntry数组**, 每个HashEntry是一个链表结构的元素. **每个Segment守护一个HashEntry数组里的元素**, 当对HashEntry数组的数据进行修改时,首先获得对应的**Segment的锁**.
 *  **并行度(默认16)**  
    concurrencyLevel：并行级别、并发数、Segment 数，怎么翻译不重要，理解它。 **默认是 16，也就是说 ConcurrentHashMap有16个Segments,最多可以同时支持 16 个线程并发写**.

## 3.2 JDK1.8(数组+链表+红黑树) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 4]

*  **ConcurrentHashMap取消了Segment分段锁**, 采用**CAS和synchronized**来保证并发安全.
 *  数据结构跟HashMap1.8的结构类似,**数组+链表/红黑树**.
 *  jdk1.8在链表长度超过一定阀值(8)时,将链表(寻址时间复杂度为O(N))转换为红黑树(寻址时间复杂度为O(log(N)))
 *  **synchronized**只锁定当前链表或红黑树的首节点, 这样只要hash不冲突, 就不会产生并发, 效率又提升N倍.

# 4. HashTable底层 #

*  **Hashtable 是遗留类**，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的，任一时间只有一个线程能写 Hashtable.
 *  并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁.
 *  Hashtable 不建议在新代码 中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。
 *  HashTable采用全表锁, 也是线程安全的, 底层类似HashMap1.7数组+链表结构.  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 5]  
    **本篇幅过长,下一篇幅续接本篇幅,着重介绍HashMap,ConcurrentHashMap,HashTable的区别~**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191214160242800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ==,size_16,color_FFFFFF,t_70
[2020122517115770.png]: https://img-blog.csdnimg.cn/2020122517115770.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191214163023436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200522161504667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191214173158974.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191214174006230.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191214175007814.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MTkwOQ==,size_16,color_FFFFFF,t_70