HashMap 详解

迷南。 2022-05-21 09:41 158阅读 0赞

*  简介
    
     *  版本介绍
     *  重点
 *  构造简介
    
     *  默认构造
     *  初始容量构造
     *  初始容量+加载因子构造
     *  构造总结
        
         *  容量
         *  加载因子
         *  阈值
            
             *  阈值-例1
             *  阈值-例2
             *  阈值-例3
 *  前景提要
    
     *  hash碰撞实体
 *  put
    
     *  核心分析
        
         *  获取key的hash
         *  putVal
         *  put流程图
     *  普通加入
     *  链表加入
        
         *  首节点覆盖
         *  链表节点覆盖
         *  加入链表末尾
     *  树化加入
 *  get
    
     *  核心分析
     *  普通获取
     *  链表获取
     *  树化获取
 *  remove
    
     *  核心分析
     *  普通删除
     *  链表删除
     *  树化删除
 *  线程安全
 *  总结
    
     *  节点模型
        
         *  无hash碰撞模型
         *  链表模型
         *  树化模型
 *  拓展
    
     *  旧值替换
        
         *  替换旧值成功
         *  替换旧值失败
     *  重置大小
        
         *  核心解析
         *  第一次put
         *  扩容
            
             *  单节点移动

# 简介 #

空气中充满了消毒水的味道,四周都是白墙,墙上有一些泼墨山水画,明媚的阳光透过窗户晒进来,照在他的脸上

他躺在床上,马上就要做手术了,心情十分平静,也不记得是第多少次手术了.

她冲了进去,紧紧握着他的手:这次可不可以不要?

说着泪如雨下,头摇的跟拨浪鼓似的

他的指尖拂过她的脸颊, “傻瓜, 小手术而已. 不用担心”.

她只是不停的摇头,声音哽咽,好像这个手术之后会再也看不到他了.

作者: 行了行了,不就一个深度剖析吗,搞的跟生离死别似的.

HashMap先生做好深度剖析的准备了,你们准备好了吗?

## 版本介绍 ##

<table> 
 <tbody> 
  <tr> 
   <td>JDK版本</td> 
  </tr> 
  <tr> 
   <td>1.8.0_102</td> 
  </tr> 
 </tbody> 
</table>

## 重点 ##

本文主要解决下面这几个疑问  
1. HashMap 如何实现自动扩容?  
2. 如何解决hash碰撞?  
3. 是否线程安全?  
4. HashMap的节点有几种形式?

# 构造简介 #

在构造这里,要搞清楚下面的三个概念  
1. 容量是什么?  
2. 加载因子是什么?  
3. 阈值是什么?

## 默认构造 ##

/** * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

默认加载因子 0.75f

## 初始容量构造 ##

public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

将指定容量 和默认加载因子 给 初始容量 + 加载因子去加载

## 初始容量+加载因子构造 ##

/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
        static final int MAXIMUM_CAPACITY = 1 << 30;
        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);
        }

1.  验证初始容量不能小于0
2.  初始容量如果大于设置的最大值,就改为最大值
3.  验证加载因子
4.  设置 阈值

MAXIMUM\_CAPACITY 上面的注释说明: 这是最大的容量,如果指定更大的值,就使用当前值,容量必须是2的次方,所以最大值是 2的30次方. 2的31次方会溢出

错误的值: NaN != NaN,NaN 可以是: 0.0f / 0.0f

## 构造总结 ##

### 容量 ###

容量是内部数组 table 的长度 table.length

容量的值一定是2的n次方,如果不是2的次方,在resize时会修改.

### 加载因子 ###

加载因子是一个容量的阈值比例,根据加载因子修改阈值

### 阈值 ###

阈值 = 容量 \* 加载因子.

在进行以下操作时,会修改阈值  
1. 重置集合大小时修改  
2. 初始容量构造时修改  
3. 初始容量+加载因子构造时修改  
4. 复制目标集合构造时修改  
5. 反序列化时修改  
6. putAll 时修改  
7. put 之后判断实际容量大于阈值时,重置集合大小,修改阈值

#### 阈值-例1 ####

默认容量为16,默认加载因子为0.75

<table> 
 <tbody> 
  <tr> 
   <td>状态</td> 
   <td>集合数量</td> 
   <td>实际容量</td> 
   <td>阈值</td> 
   <td>调用说明</td> 
  </tr> 
  <tr> 
   <td>初始状态</td> 
   <td>0</td> 
   <td>0</td> 
   <td>16</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>增加一个(初次调用resize)</td> 
   <td>1</td> 
   <td>16</td> 
   <td>12 = 16 * 0.75 </td> 
   <td>第一次put,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到13个</td> 
   <td>13</td> 
   <td>32</td> 
   <td>24 = 32 * 0.75 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到25个</td> 
   <td>25</td> 
   <td>64</td> 
   <td>48 = 64 * 0.75 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到49个</td> 
   <td>49</td> 
   <td>128</td> 
   <td>96 = 128 * 0.75 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
 </tbody> 
</table>

#### 阈值-例2 ####

指定容量为 5,默认加载因子为0.3 (虽然容量被指定为5,但是会进行 tableSizeFor,往上增加到最接近2的次方的值为：8)

<table> 
 <tbody> 
  <tr> 
   <td>状态</td> 
   <td>集合数量</td> 
   <td>实际容量</td> 
   <td>阈值</td> 
   <td>调用说明</td> 
  </tr> 
  <tr> 
   <td>初始状态</td> 
   <td>0</td> 
   <td>0</td> 
   <td>8</td> 
   <td>初始容量+加载因子 构造</td> 
  </tr> 
  <tr> 
   <td>增加1个(</td> 
   <td>1</td> 
   <td>8</td> 
   <td>2 = 8 * 0.3 </td> 
   <td>第一次put,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到3个(到达阈值调用resize)</td> 
   <td>3</td> 
   <td>16</td> 
   <td>4 = 16 * 0.3 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到5个</td> 
   <td>5</td> 
   <td>32</td> 
   <td>9 = 32 * 0.3 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到10个</td> 
   <td>10</td> 
   <td>64</td> 
   <td>19 = 64 * 0.3 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
 </tbody> 
</table>

#### 阈值-例3 ####

指定容量为 13,默认加载因子为0.90 (虽然容量被指定为13,但是会进行 tableSizeFor,往上增加到最接近2的次方的值为：16)

<table> 
 <tbody> 
  <tr> 
   <td>状态</td> 
   <td>集合数量</td> 
   <td>实际容量</td> 
   <td>阈值</td> 
   <td>调用说明</td> 
  </tr> 
  <tr> 
   <td>初始状态</td> 
   <td>0</td> 
   <td>0</td> 
   <td>16</td> 
   <td>初始容量+加载因子 构造</td> 
  </tr> 
  <tr> 
   <td>增加1个(初次调用resize)</td> 
   <td>1</td> 
   <td>16</td> 
   <td>14 = 16 * 0.9 </td> 
   <td>第一次put,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到15个</td> 
   <td>15</td> 
   <td>32</td> 
   <td>28 = 32 * 0.9 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到29个</td> 
   <td>29</td> 
   <td>64</td> 
   <td>57 = 64 * 0.9 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
  <tr> 
   <td>增加到58个</td> 
   <td>58</td> 
   <td>64</td> 
   <td>115 = 128 * 0.9 </td> 
   <td>到达阈值,调用resize时</td> 
  </tr> 
 </tbody> 
</table>

# 前景提要 #

下文分析中的实体类: HashCollisionModel

## hash碰撞实体 ##

public class HashCollisionModel { 
        private Integer number;
    
        public Integer getNumber() {
            return number;
        }
    
        public HashCollisionModel(Integer number) {
            this.number = number;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o){ return true;}
            if(o instanceof HashCollisionModel){
                HashCollisionModel that = (HashCollisionModel) o;
                return that.number .equals( number);
            }
            return false;
        }
    
        @Override
        public int hashCode() {
            return number%2+1;
        }
    }

# put #

是HashMap中最复杂的部分,接下来会根据他的节点模型来分析它

## 核心分析 ##

### 获取key的hash ###

/** * 将指定值与此映射中的指定键关联。 * 如果映射以前包含了键的映射，则值被替换 */
         public V put(K key, V value) {
                return putVal(hash(key), key, value, false, true);
         }
    
         static final int hash(Object key) {
                 int h;
                 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
         }

这里首先对key取hash值,然后在去 putVal

### putVal ###

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            // 初始化检测,如果table 为null,就初始化
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            // hash 未碰撞
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            // hash 碰撞
            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) { 
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            // 检查是否超过阈值, 超过就重新设置大小
            if (++size > threshold)
                resize();
            // 节点插入成功通知
            afterNodeInsertion(evict);
            return null;
        }

内容描述  
这里可以分为五个部分:  
1. 初始化检测, 为空就重置大小  
2. 没有hash碰撞时直接新建节点,并赋值  
3. hash碰撞处理  
4. 检查是否超过阈值, 超过就重置大小  
5. 节点插入成功通知

hash碰撞描述  
而hash碰撞又分三种情况  
1. 首节点 hash和equals 都为true,旧值替换  
2. 树化加入  
3. 链表加入

加入链表描述  
加入到链表又分三种  
1. 遍历链表,hash&&equals为true时,此时不会加入到链表,而是进行旧值替换  
2. 小于7个,加入链表  
3. 大于等于第7个,进行树化

通过上述分析,得到流程图如下

### put流程图 ###

![put流程图][put]

## 普通加入 ##

先看下面的例子:

HashMap<Integer,Object> hashMap = new HashMap<>();
            hashMap.put(1,"Paul");

这样 hashMap 内部就有一个key = 1 ,value=Paul 的一对值了

接下来分析PutVal 中的`无hash碰撞`的代码块

if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);

本例的key=1,当前由于是Integer类型,hash就是它本身,本例中为 `1`

table\[(16-1)&1\] 就是table\[1\] == null.

table\[1\]没有内容,所以这里就直接新建一个节点就可以了

## 链表加入 ##

接下来分析,`putVal` 中 `加入链表`的部分

static final int TREEIFY_THRESHOLD = 8;
    
        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;
        }

判断自己是不是最后一个节点

是最后一个节点  
1. 新建节点,设置自己的下一个节点为新建的节点  
2. binCount大于等于7的时候,就会树化(treeifyBin)

如果不是最后一个节点:  
将当前key和目标进行hash和equals比较,决定是否进入下一次循环

接下来演示加入链表的三个例子

### 首节点覆盖 ###

例子:

链表首节点的 number = 1

链表图:

添加Edgar

<table> 
 <tbody> 
  <tr> 
   <td>索引</td> 
   <td>值</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Edgar</td> 
  </tr> 
 </tbody> 
</table>

添加Helen

<table> 
 <tbody> 
  <tr> 
   <td>索引</td> 
   <td>值</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Edgar-&gt;Helen</td> 
  </tr> 
 </tbody> 
</table>

添加Paul

<table> 
 <tbody> 
  <tr> 
   <td>索引</td> 
   <td>值</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Paul-&gt;Helen</td> 
  </tr> 
 </tbody> 
</table>

### 链表节点覆盖 ###

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.put(new HashCollisionModel(3),"Helen");//未hash碰撞
            hashMap.put(new HashCollisionModel(5),"Jim");//不是最后一个节点 && 不相等 加入链表
            hashMap.put(new HashCollisionModel(5),"William");//不是最后一个节点 && 相等 替换旧值number=5

链表图:

<table> 
 <tbody> 
  <tr> 
   <td>索引</td> 
   <td>值</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Helen</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Helen-&gt;Jim</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Helen-&gt;William</td> 
  </tr> 
 </tbody> 
</table>

链表首节点的 number = 3

### 加入链表末尾 ###

最后一个节点:

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.put(new HashCollisionModel(3),"Helen");//未hash碰撞
            hashMap.put(new HashCollisionModel(5),"William");//是最后一个节点 && 不相等 加入链表
            hashMap.put(new HashCollisionModel(7),"Jim");//是最后一个节点 加入链表

<table> 
 <tbody> 
  <tr> 
   <td>索引</td> 
   <td>值</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Helen</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Helen-&gt;William</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>Helen-&gt;William-&gt;Jim</td> 
  </tr> 
 </tbody> 
</table>

## 树化加入 ##

例子:

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.put(new HashCollisionModel(1),"Edgar");
            hashMap.put(new HashCollisionModel(3),"Helen");
            hashMap.put(new HashCollisionModel(5),"William");
            hashMap.put(new HashCollisionModel(7),"Jim");
            hashMap.put(new HashCollisionModel(9),"Kenneth");
            hashMap.put(new HashCollisionModel(11),"Heathcliff");
            hashMap.put(new HashCollisionModel(13),"Earnshaw");
            hashMap.put(new HashCollisionModel(15),"Catherine");
            hashMap.put(new HashCollisionModel(17),"Joseph");//树化resize
            hashMap.put(new HashCollisionModel(19),"Linton");//树化resize
            hashMap.put(new HashCollisionModel(21),"Lockwood");//树化 替换
            hashMap.put(new HashCollisionModel(23),"Roth");//树化 替换

static final int MIN_TREEIFY_CAPACITY = 64;
    
        final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
            else if ((e = tab[index = (n - 1) & hash]) != null) {
                TreeNode<K,V> hd = null, tl = null;
                do {
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

当容量小于 64 时,重置大小

大于等于64个时, 将所有节点替换为TreeNode对象  
1. 从Node对象替换为TreeNode对象,并设置所有节点的 上一个和下一个节点对象  
2. 设置树的根节点  
3. 第一个节点对tab进行树化, (tab和this.table实际上是一个对象)

# get #

## 核心分析 ##

源码:

public V get(Object key) {
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

1.  获取key的hash(本场景中 3的hash还是3)
2.  判断getNode不为null,返回node.value

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            // 表元素判断, 没有元素返回 null
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                //链表第一个值, hash&&equals 都相等就返回
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                // 遍历链表, hash&&equals 都相等就返回
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

1.  表元素判断, 没有元素返回 null
2.  链表第一个值, hash&&equals 都相等就返回
3.  如果已经树化,就执行树化获取
4.  遍历链表, hash&&equals 都相等就返回

在这里发现,在put中的三种存入方式,获取时都做了相应的处理

## 普通获取 ##

场景:

HashMap<Integer,Object> hashMap = new HashMap<>();
            hashMap.put(3,"data");
            hashMap.get(3);

## 链表获取 ##

此时会遍历节点的链表,执行do…while 代码块

do {
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        } while ((e = e.next) != null);

## 树化获取 ##

要树化获取,一定要先扩充到树化的容量

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.put(new HashCollisionModel(1),"Edgar");//无hash碰撞
            hashMap.put(new HashCollisionModel(3),"Helen");//加入链表末尾
            hashMap.put(new HashCollisionModel(5),"William");//加入链表末尾
            hashMap.put(new HashCollisionModel(7),"Jim");//加入链表末尾
            hashMap.put(new HashCollisionModel(9),"Kenneth");//加入链表末尾
            hashMap.put(new HashCollisionModel(11),"Heathcliff");//加入链表末尾
            hashMap.put(new HashCollisionModel(13),"Earnshaw");//加入链表末尾
            hashMap.put(new HashCollisionModel(15),"Catherine");//加入链表末尾
            hashMap.put(new HashCollisionModel(17),"Joseph");//加入链表末尾,扩充容量到32
            hashMap.put(new HashCollisionModel(19),"Linton");//加入链表末尾,扩充容量到64
            hashMap.put(new HashCollisionModel(21),"Lockwood");//树化 替换
            hashMap.get(new HashCollisionModel(15));//树化获取

由于已经执行了树化替换的操作,那么所有节点已经是TreeNode,会执行 TreeNode的获取

if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

# remove #

## 核心分析 ##

public V remove(Object key) {
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

1.  获取hash
2.  removeNode 成功返回删除的值,删除失败返回null

接下来解析 removeNode

final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
            Node<K,V>[] tab; Node<K,V> p; int n, index;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
                Node<K,V> node = null, e; K k; V v;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
                else if ((e = p.next) != null) {
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else {
                        do {
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) {
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        tab[index] = node.next;
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

1.  表数据验证 && 表数据索引验证
2.  表索引位置的第一个值比较
3.  遍历 表索引位置 的链表
4.  是否找到目标值 && (是否匹配value || 找到的值.value == 目标value || 找到的值.value .equals 目标value)
5.  删除成功通知

removeNode 流程图  
![removeNode流程图][removeNode]

## 普通删除 ##

HashMap<Integer,Object> hashMap = new HashMap<>();
        hashMap.put(3,"data");
        hashMap.remove(3);

## 链表删除 ##

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.put(new HashCollisionModel(3),"Helen");//未hash碰撞
            hashMap.put(new HashCollisionModel(5),"William");//是最后一个节点 && 不相等 加入链表
            hashMap.put(new HashCollisionModel(7),"Jim");//是最后一个节点 加入链表
            hashMap.remove(new HashCollisionModel(7));

## 树化删除 ##

一旦树化后,不会因为删除对象而退回为链表

# 线程安全 #

@Test
        public void testThreadSafe() throws InterruptedException {
            String EMPTY_VALUE ="";
            HashMap<Integer, Object> hashMap = new HashMap<>();
            hashMap.put(1, EMPTY_VALUE);
            Thread threadA = new Thread(() -> { Iterator<Integer> iterator = hashMap.keySet().iterator(); System.out.println("进入 iterator 临界区"); try { Thread.sleep(2000); } catch (InterruptedException e) { e.printStackTrace(); } while (iterator.hasNext()){ Integer key = iterator.next(); System.out.println(key); } System.out.println("并发判断"); }); Thread threadB = new Thread(() -> { System.out.println("并发插入节点3"); hashMap.put(3,EMPTY_VALUE); }); threadA.start(); Thread.sleep(1000); threadB.start(); threadA.join(); threadB.join(); }

这里用两个线程对 hashMap 操作.按照如下步骤产生并发插入  
1. threadA 调用 keySet/values/entrySet 的 iterator,保存modCount进入临界区  
2. threadB 执行插入  
3. 产生 ConcurrentModificationException 异常

这里以keySet为例,对临界区进行一个详细深入的分析.  
1. keySet 会创建一个继承AbstractSet 的对象,重写了iterator,返回一个KeyIterator对象

public Set<K> keySet() {
                    Set<K> ks = keySet;
                    if (ks == null) {
                        ks = new KeySet();
                        keySet = ks;
                    }
                    return ks;
            }
    
    
            final class KeySet extends AbstractSet<K> { 
                    public final Iterator<K> iterator()     { return new KeyIterator(); }
             }

1.  KeyIterator 是一个继承 HashIterator 的一个类,在构造时,保存modCount,并且重写Iterator的next(),转发给nextNode().key

final class KeyIterator extends HashIterator implements Iterator<K> { 
                public final K next() { return nextNode().key; }
            }
    
            abstract class HashIterator { 
                // 省略其他无关代码
                HashIterator() {
                    expectedModCount = modCount;
                    Node<K,V>[] t = table;
                    current = next = null;
                    index = 0;
                    if (t != null && size > 0) { // advance to first entry
                        do {} while (index < t.length && (next = t[index++]) == null);
                    }
                }
            }

1.  并发验证,modCount 被修改时,抛出异常:ConcurrentModificationException

final Node<K,V> nextNode() {
                Node<K,V>[] t;
                Node<K,V> e = next;
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
                if ((next = (current = e).next) == null && (t = table) != null) {
                    do {} while (index < t.length && (next = t[index++]) == null);
                }
                return e;
            }

那么现在你是否了解put时,modCount++这句话的意义了吗?

# 总结 #

1.  通过`阈值`自动扩容
2.  用链表和树化解决Hash碰撞
3.  不是线程安全
4.  HashMap的节点模型有:单节点,链表,树,三种形式

## 节点模型 ##

在hashMap 中,数组的节点可能会有下面三种形态,但是数组中的某一个节点只能有一个形态  
1. 无hash碰撞  
2. 链表模型  
3. 树化模型

### 无hash碰撞模型 ###

![无hash碰撞][hash]

### 链表模型 ###

![链表][.png]

### 树化模型 ###

![树][.png 1]

# 拓展 #

## 旧值替换 ##

if (e != null) { // existing mapping for key
               V oldValue = e.value;
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               afterNodeAccess(e);
               return oldValue;
           }

旧值替换不一定会替换旧值,接下来分别演示替换成功和替换失败的两种情况

### 替换旧值成功 ###

例1: 首节点替换

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.put(new HashCollisionModel(3),"Jim");//未hash碰撞
            hashMap.put(new HashCollisionModel(3),"William");//不是最后一个节点 && 相等

例2: 链表节点替换

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.putIfAbsent(new HashCollisionModel(1),"Edgar");//未hash碰撞
            hashMap.putIfAbsent(new HashCollisionModel(3),"Helen");//不是最后一个节点 && 相等
            hashMap.putIfAbsent(new HashCollisionModel(3),"William");//不是最后一个节点 && 相等

例3 : value为null时,无论首节点还是子节点都会被替换

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.putIfAbsent(new HashCollisionModel(3),null);//未hash碰撞
            hashMap.putIfAbsent(new HashCollisionModel(3),"William");//不是最后一个节点 && 相等

### 替换旧值失败 ###

例1 : 已经存在,替换失败

HashMap<HashCollisionModel,Object> hashMap = new HashMap<>();
            hashMap.putIfAbsent(new HashCollisionModel(3),"Jim");//未hash碰撞
            hashMap.putIfAbsent(new HashCollisionModel(3),"William");//不是最后一个节点 && 相等

## 重置大小 ##

### 核心解析 ###

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            @SuppressWarnings({
       "rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & 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;
        }

这里的重置大小会有多种情形,但是无论是哪种情形,

都是一个对内部数组table的长度修改的一个操作.

重点就在于  
1. 扩容的容量是多少?  
2. 扩容后对于搜索有什么好处

接下来分两种情况去分析

### 第一次put ###

例子:

HashMap<Integer, Object> hashMap = new HashMap<>();
            hashMap.put(1, "Edgar");//无hash碰撞

默认构造时的第一次put,此时只初始化了加载因子为0.75,此时进入else区,容量初始化为16,阈值为12

else {               // zero initial threshold signifies using defaults
               newCap = DEFAULT_INITIAL_CAPACITY;
               newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
           }

接着根据newCap 初始化 table = (Node

### 扩容 ###

HashMap<Integer, Object> hashMap = new HashMap<>(8, 0.3F);
                    hashMap.put(1,"");//第一次扩容
                    hashMap.put(2,"");
                    hashMap.put(3,"");//第二次扩容

这里分析第二次扩容的情况,如何重置大小.

1.  进入下面这个语句块,设置新容量 = 旧容量\*2

if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                //设置新容量 = 旧容量*2
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                //旧容量为8, 8>=16的判断为false,不会为newThr赋值
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }

1.  根据新容量,设置新的阈值

if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }

扩容了之后,接下来就是要移动内部所有的元素了,用下面的伪代码演示,如何移动所有的节点

if (oldTab != null) {
        if(table[i]!=null){
            if(是单节点){
                // TODO 单节点移动
                newTab[e.hash & (newCap - 1)] = e;
            }else if(树化节点){
              // TODO 树化节点移动
            }else if(链表节点){
               // TODO 链表节点移动
             }
        }
    
    }

接下来简单的介绍,单节点移动的table的内容

#### 单节点移动 ####

HashMap<Integer, Object> hashMap = new HashMap<>(16, 0.3F);
            hashMap.put(1,"");//第一次扩容
            hashMap.put(8,"");
            hashMap.put(24,"");
            hashMap.put(25,"");
            hashMap.put(26,"");//第二次扩容

第二次扩容之前的table的内容

第二次扩容的table的内容

[put]: http://cdn.blog.shangwantong.com/put%E6%B5%81%E7%A8%8B.png
[removeNode]: http://cdn.blog.shangwantong.com/HashMap/%E6%B5%81%E7%A8%8B%E5%9B%BE.png
[hash]: http://cdn.blog.shangwantong.com/HashMap/无hash碰撞.png
[.png]: http://cdn.blog.shangwantong.com/HashMap/链表.png
[.png 1]: http://cdn.blog.shangwantong.com/HashMap/树.png