hashmap从入门到死锁，再到分段式锁

朴灿烈づ我的快乐病毒、 2022-01-22 02:25 228阅读 0赞

本文主要内容如下：在jdk1.7和jdk1.8下

hashmap put和get的原理，和可能造成的问题

concurrentHashMap的原理

# hashmap入门 #

直接NEW出来就可以了，想要获取详细信息的这个直接看源码，源码上说的更仔细；

主要有两个参数，一个是负载因子（需要扩容的比例），一个是初始化的大小。

/**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

综上所述，入门完毕；

## JDK1.7 HashMap的put源码分析 ##

hashmap的put操作的主要步骤：

1.  判断KEY是否为NULL，如果为NULL，就将VALUE放进去
2.  求出KEY的hash值
3.  由hash值求出对应的数组位置
4.  判断此key是否已经存在了，如果存在了就将value进行替换并返回旧值
5.  添加新的值到hashmap中

也就是源码中的如下代码：

/**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

其中相对复杂一点的代码主要在addEntry这个方法中，此方法会去判断是否需要去扩容，如果需要去扩容的话，则需要将hashmap的entry数组的值进行一次转移，由旧的entry数组转移到新的entry数组中，其代码为：

/**
         * Transfers all entries from current table to newTable.
         */
        void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

JDK1.7中HashMap的put方法的主要过程便是上面这样的一个大致过程，整体上来说还算是比较简单的。

## JDK1.7 HashMap死锁 ##

hashmap死锁的死锁问题不是我说的，是网上大家都这么说的，不信的话可以百度一把。在没有看源码前时的我也信以为真了，以为hashmap里的put方法真的会发生死锁，但是在看了源码后我感觉被骗了，put方法在多线程情况下确实会有问题。为此我也特意写了一段代码来验证，代码如下：

import java.util.HashMap;
    import java.util.UUID;
    
    public class HashMapStu {
        public static void main(String[] args) throws Exception {
            final HashMap<String, String> map = new HashMap<String, String>();
            for (int i = 0; i < 10000; i++) {
                new Thread(new Runnable() {
                    @Override
                    public void run() {
                        map.put(UUID.randomUUID().toString(), "");
                    }
                }, "mythread-" + i).start();
            }
    
            System.out.println("ok!");
        }
    
    
    }

然后运行几次，看看会不会出现什么状况；

按照上面的代码可以看出，正常情况下当控制台输出了"ok!"后程序就会停止的，但是我在JDK1.7的环境下运行了几次发现并没有停止运行，并且电脑中的此程序的CPU占有量很大

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70][]

然后用jstack打印出此进程的线程信息发现有一个线程一直处于运行状态：

Full thread dump Java HotSpot(TM) 64-Bit Server VM (24.79-b02 mixed mode):
    
    "DestroyJavaVM" prio=5 tid=0x00007fdef60a2800 nid=0x2803 waiting on condition [0x0000000000000000]
       java.lang.Thread.State: RUNNABLE
    
    "mythread-8880" prio=5 tid=0x00007fdef5048800 nid=0x3c27 runnable [0x000070000f1ed000]
       java.lang.Thread.State: RUNNABLE
    	at java.util.HashMap.put(HashMap.java:494)
    	at HashMapStu$1.run(HashMapStu.java:11)
    	at java.lang.Thread.run(Thread.java:745)
    
    "Attach Listener" daemon prio=5 tid=0x00007fdef5847000 nid=0x8e23 waiting on condition [0x0000000000000000]
       java.lang.Thread.State: RUNNABLE
    
    "Service Thread" daemon prio=5 tid=0x00007fdef684a000 nid=0x3603 runnable [0x0000000000000000]
       java.lang.Thread.State: RUNNABLE
    
    "C2 CompilerThread1" daemon prio=5 tid=0x00007fdef5810800 nid=0x3503 waiting on condition [0x0000000000000000]
       java.lang.Thread.State: RUNNABLE
    
    "C2 CompilerThread0" daemon prio=5 tid=0x00007fdef580c800 nid=0x4603 waiting on condition [0x0000000000000000]
       java.lang.Thread.State: RUNNABLE
    
    "Signal Dispatcher" daemon prio=5 tid=0x00007fdef5023000 nid=0x4807 runnable [0x0000000000000000]
       java.lang.Thread.State: RUNNABLE
    
    "Finalizer" daemon prio=5 tid=0x00007fdef6837800 nid=0x2e03 in Object.wait() [0x000070000e952000]
       java.lang.Thread.State: WAITING (on object monitor)
    	at java.lang.Object.wait(Native Method)
    	- waiting on <0x00000007c000a210> (a java.lang.ref.ReferenceQueue$Lock)
    	at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:135)
    	- locked <0x00000007c000a210> (a java.lang.ref.ReferenceQueue$Lock)
    	at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:151)
    	at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:209)
    
    "Reference Handler" daemon prio=5 tid=0x00007fdef6000000 nid=0x5103 in Object.wait() [0x000070000e84f000]
       java.lang.Thread.State: WAITING (on object monitor)
    	at java.lang.Object.wait(Native Method)
    	- waiting on <0x00000007c0008560> (a java.lang.ref.Reference$Lock)
    	at java.lang.Object.wait(Object.java:503)
    	at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:133)
    	- locked <0x00000007c0008560> (a java.lang.ref.Reference$Lock)
    
    "VM Thread" prio=5 tid=0x00007fdef5018800 nid=0x2c03 runnable 
    
    "GC task thread#0 (ParallelGC)" prio=5 tid=0x00007fdef500e000 nid=0x2207 runnable 
    
    "GC task thread#1 (ParallelGC)" prio=5 tid=0x00007fdef500f000 nid=0x1f03 runnable 
    
    "GC task thread#2 (ParallelGC)" prio=5 tid=0x00007fdef6814000 nid=0x2a03 runnable 
    
    "GC task thread#3 (ParallelGC)" prio=5 tid=0x00007fdef6814800 nid=0x5403 runnable 
    
    "VM Periodic Task Thread" prio=5 tid=0x00007fdef5020800 nid=0x4303 waiting on condition 
    
    JNI global references: 142

提示第494行一直在运行，在源码中找到也就是这一行了：

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

这一行是一个for循环，想要让这一行一直运行让e一直都不等于null即可，

而e又等于e.next，e是一个链表。想让e一直不为null，让e这个链表中有环就可以了。

*那么现在程序一直运行在494行，那么也就是e是一个有环的链表了，那么是哪里造成了这样的情况的呢？*

***答案是在多线程情况下对hashmap进行扩容时造成的，也就是上面贴出来的transfer的代码。具体原因可以考虑下面的场景：***

*假设某一个entry节点的值为:1>2>3>null*

*有两个线程分别为：P1、P2*

*按照时间先后顺序有时间T1、T2、T3、T4、T5、T6*

**T1时间点：P1线程运行完Entry<K,V> next = e.next这行后，其值为：**

**e=*1>2>3>null***

**next=*2>3>null***

***newTable\[i\]=1>2>3>null***

*然后P1线程就wait住了*

**T2时间点:P2线程将整个方法运行完毕了，扩容已经完成了，也就是while方法已经执行完毕了，其值为：**

**e=null**

**next=null**

**newTable\[i\]=3>2>1>null**

**T3时间点：P1线程获得CPU的执行权了，P1线程继续执行，当P1线程执行一次while循环的代码后，其值为：**

**e=2>1>null**

**next=2>3>null**

**newTable\[i\]=1>3>2>1>null**

**那么newTable\[i\]这个节点就造成循环链表了！然后再去执行链表的循环时就会一直执行下去**

## JDK1.7 concurrentHashMap的put方法 ##

**空了来写**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70]: /images/20220122/0a2ed07e274340b19e51ac2854b67628.png