深入理解 HashMap

朴灿烈づ我的快乐病毒、 2023-06-14 11:56 9阅读 0赞

### 文章目录 ###

*   *  什么是 HashMap？
     *  HashMap的简单使用
     *  HashMap中的负载因子和容量
     *   *   *  负载因子的默认值
     *  HashMap中的构造函数
     *   *  一、HashMap(int initialCapacity, float loadFactor)
         *   *   *  >> 与 >>> 的区别
                 *  为什么容量必须为2的整数幂？
         *  二、HashMap(int initialCapacity)
         *  三、HashMap()
         *  四、HashMap(Map<? extends K, ? extends V> m)
         *   *   *  putMapEntries(m,false)
                 *  putVal()
                 *  resize()
     *  hash冲突？
     *   *  为什么会hash冲突？
         *  hash冲突的几种情况
         *  如何解决hash冲突？
         *   *   *  开放地址法
                 *  链地址法
     *  HashMap的常用操作
     *   *  get()
         *  put()
         *  remove()
     *  jdk1.7的HashMap与1.8的HashMap有什么不同？
     *   *  一、JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法
         *  二、扩容后数据存储位置的计算方式不一样：
         *  三、结构不同
     *  HashMap为什么是线程不安全的？
     *   *  HashMap 在并发时可能出现的问题主要是两方面：
         *   *   *  1、put()操作的时候导致的多线程数据不一致
                 *  2、resize()而引起死循环
     *  HashMap与HashTable有什么不同？
     *  HashMap如何解决线程安全问题？

## 什么是 HashMap？ ##

HashMap 是基于哈希表的 Map 接口是实现的。此实现提供所有可选操作，并允许使用 null 做为值（key）和键（value）。HashMap 不保证映射的顺序，特别是它不保证该顺序恒久不变。此实现假定哈希函数将元素适当的分布在各个桶之间，可作为基本操作（get 和 put）提供稳定的性能。在jdk1.7中的HashMap是基于数组+链表实现的，在jdk1.8中的HashMap是由数组+链表+红黑树实现的（不懂，一开始就讲那么难的谁受得了？没关系，继续往下看）

## HashMap的简单使用 ##

关于HashMap的使用 [HashMap的简单使用][HashMap]

## HashMap中的负载因子和容量 ##

在介绍HashMap之前让我们先了解一下HashMap中的负载因子和容量这两个属性。

其实HashMap的实际容量如下：

实际容量 = 负载因子 x 容量，也就是 12 = 0.75 x 16

这个很重要，对效率有一定的影响，而且下面也会详细讲解为什么这两个属性很重要。

//默认初始容量-必须为2的幂次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    //最大容量，如果传入的值大于下面的值，则使用下面定义的值
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //在构造函数中未指定时使用的负载系数（上面提到的负载因子在这里出现了）
    //默认加载因子为0.75（当表容量达到3/4时才会再散列）
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    //当链表的长度 >= 8的时候，将链表转换成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    //在resize()扩容的时候，HashMap的数据存储位置会重新进行计算
    //在重新就散存储的位置后，当原有的红黑树数量 <= 6 的时候，则将红黑树转换为链表
    static final int UNTREEIFY_THRESHOLD = 6;
    
    //为了避免扩容/调整树化阀值之间的冲突，这个值不能 < 4 * TREEIFY_THRESHOLD
    static final int MIN_TREEIFY_CAPACITY = 64;

#### 负载因子的默认值 ####

有人就会问了，为什么DEFAULT\_LOAD\_FACTOR（默认的加载因子）是0.75呢？为什么不是0.76，0.77呢？，不慌，看下官方文档是怎么说的：

>  通常，默认的加载因子（0.75）在时间和空间成本之间提供了一个很好的方案。较高的值会减少空间的开销，但会增加查找的成本（在HashMap类的大多数操作中都能得到体现，包括最常用的（ get() 操作和 put() 操作）。在设置映射表的初始容量的时候，应该考虑映射中预期的 Entry 数及其负载因子，以最大程度地减少 rehash（重新哈希）操作的次数。如果初始容量大于最大条目数 / 负载因子 ，则将不会进行任何哈希操作
> 
>  如果要将许多映射存储到HashMap实例中，则创建具有足够大容量的映射将比使它根据需要增长表的自动重新哈希处理更有效地存储映射

看起来好像也没说为什么默认是0.75，但是知道一下就好了，因为涉及到高数那些。如果遇到面试官问这个你就把这个文档丢给他 [官方文档][Link 1]

## HashMap中的构造函数 ##

我们先从构造函数开始，一步一步讲解。在HashMap中有四个构造函数

### 一、HashMap(int initialCapacity, float loadFactor) ###

public HashMap(int initialCapacity, float loadFactor) { 
        
        //当指定的 initialCapacity （初始容量） < 0 的时候会抛出 IllegalArgumentException 异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        
        //当指定的 initialCapacity （初始容量）= MAXIMUM_CAPACITY（最大容量） 的时候 
        if (initialCapacity > MAXIMUM_CAPACITY)
            //初始容量就等于 MAXIMUM_CAPACITY （最大容量）
            initialCapacity = MAXIMUM_CAPACITY;
        
        //当 loadFactory（负载因子）< 0 ，或者不是数字的时候会抛出 IllegalArgumentException 异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        
        //tableSizeFor()的主要功能是返回一个比给定整数大且最接近2的幂次方整数
        //比如我们给定的数是12，那么tableSizeFor()会返回2的4次方，也就是16，因为16是最接近12并且大于12的数
        this.threshold = tableSizeFor(
            initialCapacity);
    }

前面的应该不难理解，因为都是一些基本的代码，可能 tableSizeFor() 会难理解点，没事，我们可以看下源码是怎么实现的，tableSizeFor()源码如下：

//对于给定的目标容量，返回两倍大小的幂
    static final int tableSizeFor(int cap) { 
        
        //为了防止cap已经是2的幂次方时，执行完后面的几条无符号右移操作之后
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

可能会有很多人会想这是什么东东？一开始看到上面的代码也是很懵，不过没关系，下面就为你讲解：

//假如在tableSizeFor(int cap)中传入一个12，那么经过下面这句运算之后 n = 11
    int n = cap - 1; 
    //这个应该不难理解，ok，继续往下看

/** * 1、这又是什么东东？这才是比较懵的吧？那么这句代码如何理解呢？ * 2、通过上面的代码我们可以知道 n 经过运算之后等于 11 * 3、11的二进制为 00001011，>>>是右移的意思，1代表移动一一位。有人又会问了，>>不也是右移吗？这两个有什么区别 呢？这个稍后解释，这里先知道是这么个回事 * | 或操作：意思是把某两个数中, 只要其中一个的某一位为1，则结果的该位就为1 */
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;

##### >> 与 >>> 的区别 #####

现在来讲解一下 >> 与 >>> 的区别

*  1、>> ：按二进制形式把所有的数字向右移动对应位数，低位移出（舍弃），高位的空位补符号位，即正数补零，负数补1。符号位不变。
 *  2、>>> ： 二进制右移补零操作符，左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充

逐步分析：

*  n |= n >>> 1

//假设给定的cap值是10，那么n=9，9的二进制为 -> 00001001
    n    		    ------------- 00001001
    n >>> 1		    ------------- 00000100
    n |= n >>> 1     ------------- 00001101

*  n |= n >>> 2

//这里的 n 是接着上个 n 的值，即：
    n				------------ 00001101
    n >>> 2    		 ------------ 00000011
    n |= n >>> 2     ------------ 00001111

此时 n 的所有位 均为 1，后续的操作均不会改变 n 的值，十进制均为15

因为 HashMap 要保证容量是 2 的整数次幂， 该方法实现的效果就是如果你输入的 cap 本身就是偶数，那么就返回 cap 本身，如果输入的 cap 是奇数，返回的就是比 cap 大的最小的 2 的整数幂

##### 为什么容量必须为2的整数幂？ #####

> 因为获取 key 在数组中对应的下标是通过 key 的哈希值与数组长度 -1 进行与运算，如：i = (n - 1) & hash
> 
> 1、n 为 2 的整数次幂，这样 n-1 后之前为 1 的位后面全是 1，这样就能保证 (n-1) & hash 后相应的位数既可能是 0 又可能是 1，这取决于 hash 的值，这样能保证散列的均匀，同时与运算效率高
> 
> 2、如果 n 不是 2 的整数次幂，会造成更多的 hash 冲突（为什么会冲突，稍后会讲解）

在Java8中，HashMap中key的hash值是由hash(key)方法计算的，hash方法代码如下：

/** * 计算key.hashCode（）并扩展（XOR）哈希的更高位降低。 由于该表使用2的幂次掩码，因此仅在当前掩码上方的位上 * 变化的散列将总是相撞。 （其中一些示例是Float键集在小表中保存连续的整数。）所以我们应用变换以扩展较高位的 * 影响向下。 在速度，效用和比特扩散的质量。 因为许多常见的哈希集已经合理分配（因此不要从传播），并且因为我 * 们使用树来处理大量的箱中的碰撞，我们只是将减少系统损失的最便宜的方法，以及合并否则会影响最高位的影响由于 * 表的限制，从不用于索引计算。 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

HashMap中存储数据的table的index是由key的hash值决定的

在HashMap中存储数据的时候，我们希望数据能够均匀地分布，以防止哈希冲突

自然地我们就会想到用 % 取余操作来实现  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70_pic_center]

> 取余（%）操作：如果除数是2的幂次方则等价于其除数减一的与操作（&）

以下来自resize()方法：

//这段代码等价于 index = e.hash % newCap
    //这也就解释了为什么一定要求cap要为2的幂次方的原因
    if (e.next == null){ 
        //e代表的是Node类，next代表节点
        newTab[e.hash & (newCap - 1)] = e;
    }

到这里相信大部分读着都能够明白了为什么容量必须为2的幂次方，如果还是有点懵的，没事，我们举个例子就明白了

我们把 tableSizeFor() 代码搬过来测试一下，如：

public class StringDemo { 
        
        //最大容量
        static final int MAXIMUM_CAPACITY = 1 << 30;
        
        //这是tableSizeFor源码
        static final int tableSizeFor(int cap) { 
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
        
        //主函数
        public static void main(String[] args) { 
            int size = tableSizeFor(10); //比如我们这里传入的数字是10，那么打印的size会是多少呢？
            System.out.println(size);
        }
    }

答案是：16

这16怎么来的？答案就是上面是所讲的 >>> 操作，我们debug看一下变量的情况，由于debug显示的是上一步操作的结果，所以大家看variable变量的时候记得是上一步操作后的结果

可以看到，一开始的cap是10  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70]  
ok，继续执行下一步，可以看到这时候的 n 为 9，是因为cap的减一操作，这个没问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 1]  
ok，继续执行，经过上一步的操作之后 9 异或运算之后变为了 13

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 2][]  
继续执行，经过上一步操作后13 变为了 15

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qBmiBM8e-1574154616687)(D:\\工具类\\typora\\img\\image-20191119144129298.png)\]][img-qBmiBM8e-1574154616687_D_typora_img_image-20191119144129298.png]

继续执行，还是 15

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-96Qfu0eK-1574154616688)(D:\\工具类\\typora\\img\\image-20191119144228371.png)\]][img-96Qfu0eK-1574154616688_D_typora_img_image-20191119144228371.png]

还是15，继续执行  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R2swMasF-1574154616689)(D:\\工具类\\typora\\img\\image-20191119144356970.png)\]][img-R2swMasF-1574154616689_D_typora_img_image-20191119144356970.png]  
ok，重点来了，以下的15是上一步操作也就是（n |= n >>> 16）得来的，大家不要以为是return的哈

也就是说该方法实现的效果就是判断你输入的数字是否为2的指数幂，如果是则返回这个数的本身，否则返回比这个数大且最接近的2次幂  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hk8NmlxW-1574154616690)(D:\\工具类\\typora\\img\\image-20191119144515715.png)\]][img-hk8NmlxW-1574154616690_D_typora_img_image-20191119144515715.png]  
15 在 return语句中加一之后就是16啦  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 3]  
是不是感觉已经掌握了这个tableSizeFor()方法？很激动？别，还有很多东西要学呢，这才写了第一个构造函数呢（囧），继续往下看

### 二、HashMap(int initialCapacity) ###

//构造一个初始容量为 initialCapacity，负载因子为 0.75的HashMap
    public HashMap(int initialCapacity) {     
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

### 三、HashMap() ###

//使用默认的初始容量构造一个空的HashMap（16）和默认负载系数（0.75）。
    public HashMap() { 
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

### 四、HashMap(Map<? extends K, ? extends V> m) ###

##### putMapEntries(m,false) #####

//构造一个和指定Map有相同的mappings的HashMap，初始容量能充足的容下指定的Map，负载因子为0.75
    public HashMap(Map<? extends K, ? extends V> m) { 
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

ok，见招拆招，我们点击 putMapEntries(m,false)

//将m的所有元素存入到该HashMap实例中
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
        
        //获取 m 中元素的个数
        int s = m.size();
        
        //当 m 中有元素的时候，需要将Map中的元素放入此HashMap实例中
        if (s > 0) { 
            
            //判断table是否已经初始化，如果table已经初始化，则先初始化一些变量（table的初始化指在put的时候）
            if (table == null) {  // pre-size
                
                //根据待插入的Map的大小（size）计算要创建的 HashMap 容量
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                
                //将要创建的 HashMap 容量存在 threshold 中
                if (t > threshold)
                    //threshold是一个整型变量
                    threshold = tableSizeFor(t);
            }
            
            //如果table初始化过了，因为别的函数也会调用到它，所以有可能HashMap已经被初始化过了
            //判断待插入的 Map 的 大小（size），如果size > threshold ，则先进行 resize() 扩容
            else if (s > threshold)
                resize();
            
            //然后开始遍历，待插入的 Map ，将每一个<Key,Value> 插入到该HashMap实例中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
                K key = e.getKey();
                V value = e.getValue();
                
                //然后调用 putVal 函数进行元素的插入操作
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

##### putVal() #####

又来了一个大招，这 putVal又是什么？我们点击看下，为了能够更好地理解这个 putVal 之前，我们先把 putVal 用到的东西看一下

/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */
    //英文看不懂？那就练练英语吧（滑稽）
    //官方注释第一句说了table？没错，Node实际上是存储key，value的数组，只不过被Node封装了
    transient Node<K,V>[] table;
    
    /** * The number of key-value mappings contained in this map. */
    transient int size;
    
    /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
    transient int modCount;
    
    /** * The next size value at which to resize (capacity * load factor). * * @serial */
       // (The javadoc description is true upon serialization.
       // Additionally, if the table array has not been allocated, this
       // field holds the initial array capacity, or zero signifying
       // DEFAULT_INITIAL_CAPACITY.)
    //这个就是上面所说的 tableSizeFor(t) 赋予的值
    int threshold;
    
    /** * The load factor for the hash table. * * @serial */
    final float loadFactor;

> 其实这里说的就是哈希表，HashMap使用链表的方式避免哈希冲突（相同的hash值），当链表长度大于 TREEIFY\_THRESHOLD （默认为8）的时候，将链表转换成红黑树；当小于 UNTREEIFY\_THRESHOLD （默认为6）的时候，又会转回链表以达到性能均衡（搞那么复杂无非就是为了性能嘛对吧）

为了能够更好的理解table，我们我们可以先看下HashMap的数据结构（数组+链表+红黑树）如下：

![img][]

以下是 putVal 源码：

//实现 put 和相关方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { 
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        //如果table为空或者长度为0，则进行resize()（扩容）
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        //确定插入table的位置，算法是上面提到的 (n - 1) & hash，在 n 为 2 的时候，相当于取模操作
        if ((p = tab[i = (n - 1) & hash]) == null)
            //找到key值对应的位置并且是第一个，直接插入
            tab[i] = newNode(hash, key, value, null);
        
        //在table的 i 的位置发生碰撞，分两种情况
        //1、key值是一样的，替换value值
        //2、key值不一样的
        //而key值不一样的有两种处理方式：1、存储在 i 的位置的链表 2、存储在红黑树中
        else { 
            Node<K,V> e; K k;
            
            //第一个Node的hash值即为要加入元素的hash
            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 { 
                //如果不是TreeNode的话，即为链表，然后遍历链表
                for (int binCount = 0; ; ++binCount) { 
                    
                    //链表的尾端也没有找到key值相同的节点，则生成一个新的Node
                    //并且判断链表的节点个数是不是到达转换成红黑树的上界达到，则转换成红黑树
                    if ((e = p.next) == null) { 
                        
                        //创建链表节点并插入尾部
                        p.next = newNode(hash, key, value, null);
                        
                        //超过了链表的设置长度（默认为8）则转换为红黑树
                        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;
                }
            }
            
            //如果e不为空
            if (e != null) {  // existing mapping for key
                //就替换就的值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

根据源码可以知道，如果table为null的话，那么就设置何时的threshold，如果table不为null的话就指定map的size > threshold，然后就resize()。然后再把指定的Map的所有Key，Value通过putVal添加到我们创建的新的Map中

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

putVal 中传入了一个hash(key)，这个hash(key)在上面也讲到过，如下：

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这异或运算又来了（哈哈）

为什么要这么做呢？

> 这样做的好处是可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。掺杂的元素多了，生成的hash值的随机性就越大

if (++size > threshold)
        resize();

putVal中有一段代码提到了resize()，也就是扩容，我们来看下源码

##### resize() #####

以下是 resize() 源码：

final Node<K,V>[] resize() { 
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        
        //判断Node的长度，如果不为零
        if (oldCap > 0) { 
            //判断当前Node的长度，如果当前长度超过 MAXIMUM_CAPACITY（最大容量值）
            if (oldCap >= MAXIMUM_CAPACITY) { 
                //新增阀值为 Integer.MAX_VALUE
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            
            //如果小于这个 MAXIMUM_CAPACITY（最大容量值），并且大于等于 DEFAULT_INITIAL_CAPACITY （默认16）
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                //进行2倍扩容
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            //指定新增阀值
            newCap = oldThr;
        
        //如果数组为空
        else {                // zero initial threshold signifies using defaults
            //使用默认的加载因子(0.75)
            newCap = DEFAULT_INITIAL_CAPACITY;
            //新增的阀值也就为 16 * 0.75 = 12
            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数组
        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;
                            
                            //哈希值和原数组长度进行&操作，为0则在原数组的索引位置
                            //非0则在原数组索引位置+原数组长度的新位置
                            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;
    }

## hash冲突？ ##

### 为什么会hash冲突？ ###

就是根据key即经过一个函数f(key)得到的结果的作为地址去存放当前的key，value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经有人先来了。就是说这个地方要挤一挤啦。这就是所谓的hash冲突啦

### hash冲突的几种情况 ###

*  两个节点的key值相同（hash值一定相同），导致冲突
 *  两个节点的key值不同，由于hash函数的局限性导致hash值相同，导致冲突
 *  两个节点的key值不同，hash值不同，但hash值对数组长度取模后相同，导致冲突

### 如何解决hash冲突？ ###

解决hash冲突的方法主要有两种，一种是 开放地址法，另一种是 链地址法

##### 开放地址法 #####

> 开放地址法的原理很简单，就是当一个 Key 通过 hash 函数获得对应的数组下标已被占用的时候，我们可以寻找下一个空档位置

比如有个 Entry6 通过 hash 函数得到的下标为 2，但是该下标在数组中已经有了其它的元素，那么就向后移动 1 位，看看数组下标为 3 的位置是否有空位  
![在这里插入图片描述][20191203164306458.png]  
但是下标为 3 的数组也已经被占用了，那么久再向后移动 1 位，看看数组下标为 4 的位置是否为空  
![在这里插入图片描述][20191203164456353.png]  
OK，数组下标为4的位置还没有被占用，所以可以把Entry6存入到数组下标为4的位置。这就是开放寻址的基本思路，寻址的方式有很多种，这里只是简单的一个示例

##### 链地址法 #####

链地址法也正是被应用在了 HashMap 中，HashMap 中数组的每一个元素不仅是一个 Entry 对象，还是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个Entry 节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可  
![在这里插入图片描述][20191203165510546.png]

## HashMap的常用操作 ##

### get() ###

相对于上面所讲的，get操作和put操作就比较简单了，根据key获取hash值，其他没什么可说的，有值就返回value，没有值返回null，直接进入 getNode()

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

getNode()方法如下：

final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        
        	//这个table与putVal中使用的table是一样的，简单的说就是只要使用了put操作就可以进行get操作
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) { 
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                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;
        }

### put() ###

put操作只要使用的函数就是 putVal（好熟悉的feel），也就是上面所讲的，这里不再解释

public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }

### remove() ###

remove(key) 方法 和 remove(key, value) 方法都是通过调用removeNode的方法来实现删除元素的

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

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 { 
                    
                    //此处是一个链表，遍历链表返回node
                    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;
    }

## jdk1.7的HashMap与1.8的HashMap有什么不同？ ##

### 一、JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法 ###

那么为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法就是能够提高插入的效率，但是也会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题

### 二、扩容后数据存储位置的计算方式不一样： ###

1.  在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1）
2.  而在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式

### 三、结构不同 ###

JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（N）变成O（logN）提高了效率）

## HashMap为什么是线程不安全的？ ##

### HashMap 在并发时可能出现的问题主要是两方面： ###

##### 1、put()操作的时候导致的多线程数据不一致 #####

比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的 hash桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为

##### 2、resize()而引起死循环 #####

这种情况发生在HashMap自动扩容时，当2个线程同时检测到元素个数超过 数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize()，两个线程同时修改一个链表结构会产生一个循环链表（JDK1.7中，会出现resize前后元素顺序倒置的情况）。接下来再想通过get()获取某一个元素，就会出现死循环

> 注：JDK7使用是hash值与数组长度-1 这个掩码进行与运算，得到Entry元素的新下标位置，得到的结果直接就是下标位置 ；  
> Jdk1.8中是使用hash值与 数组长度 进行与运算，得到的是0 或者非零。如果是0  
> 表示新位置下标不变，如果不是0那么表示位置有变动，如果有变动下标位置是原位置加上数组长度。

**性能**  
JDK8中resize方法并没有比JDK7中性能更好。Entry的key最坏的情况下在Map中是一个链表，JDK8为优化这个问题在链表数目大于8的时候转化为红黑树，但是resize中，又必需拆解和重建红黑树。

**拆解过程**  
和普通的Entry链表一样，顺序遍历(此时只用它的next指针)，使用上述判断方式，分离成需要变动和不需要变动的两个列表。

**重建过程**  
如果列表长度小于6，去掉树结构指针，维持成一个链表  
如果列表长度大于8，重新构造成一棵树。  
总的来看，JDK7的resize时间复杂度n，JDK8的复杂度为nlog(n)

## HashMap与HashTable有什么不同？ ##

除了非同步和允许键值为null之外，HashMap和HashTable大致相同

## HashMap如何解决线程安全问题？ ##

既然HashMap不是线程安全的，那么如何使它成为线程安全的呢？，通过以下代码就可以使HashMap为线程安全的

HashMap<String,Integer> hashMap = new HashMap<String,Integer>();
    Map<String, Integer> map = Collections.synchronizedMap(hashMap);

> 这只是HashMap的其中一部分源码，不过也差不多够用了，关于HashMap的更多内容还需要继续学习，加油吧

本文尽量以文字描述+源码+图解的方式来展开对HashMap的理解，方便大家学习，第一次对源码展开深入学习并且记录，难免会有一些不对的地方，如有写的不好或者有错误，请指导一下，谢谢

[HashMap]: https://blog.csdn.net/Woo_home/article/details/94332922
[Link 1]: https://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/202008142055494.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191119171423126.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191119171301313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191119171204942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[img-qBmiBM8e-1574154616687_D_typora_img_image-20191119144129298.png]: https://img-blog.csdnimg.cn/20191119171243306.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[img-96Qfu0eK-1574154616688_D_typora_img_image-20191119144228371.png]: https://img-blog.csdnimg.cn/20191119171517960.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[img-R2swMasF-1574154616689_D_typora_img_image-20191119144356970.png]: https://img-blog.csdnimg.cn/20191119171552303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[img-hk8NmlxW-1574154616690_D_typora_img_image-20191119144515715.png]: https://img-blog.csdnimg.cn/20191119171609408.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191119171640210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dvb19ob21l,size_16,color_FFFFFF,t_70
[img]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy81Njc5NDUxLWM2ZTgwZDMwYjY2NTMzMjQucG5n?x-oss-process=image/format,png
[20191203164306458.png]: https://img-blog.csdnimg.cn/20191203164306458.png
[20191203164456353.png]: https://img-blog.csdnimg.cn/20191203164456353.png
[20191203165510546.png]: https://img-blog.csdnimg.cn/20191203165510546.png