Java基础-集合框架-5、HashMap

1. 数据结构（哈希表）

hashtable（哈希表）

1.1. 是什么

散列表（Hash table，也叫哈希表），是根据关键码值 (Key value) 而直接进行访问的 数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做 散列函数，存放记录的 数组 叫做 散列表
给定表 M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表 M 为哈希 (Hash）表，函数 f(key) 为哈希 (Hash) 函数。

1.2. 特点

hash 表 也叫散列表；特点：快 很快 神奇的快

结构：结构有多种。最流行、最容易理解：顺序表 + 链表

主结构：顺序表，每个顺序表的节点在单独引出一个链表

在无序数组中按照内容查找，效率低下，时间复杂度是 O(n)

在有序数组中按照内容查找，可以使用折半查找，时间复杂度 O(log2n)

问题：按照内容查找，能否也不进行比较，而是通过计算得到地址，实现类似数组按照索引查询的高效率 O(1) 呢

有！！！哈希表来实现

1.3. 哈希函数

1.4. native hashcode 方法

[[20221029-Java Object.hashCode()返回的是对象内存地址？ - 简书]]
OpenJDK8 默认 hashCode 的计算方法是通过和当前线程有关的一个随机数 + 三个确定值，运用 Marsaglia’s xorshift scheme 随机数算法得到的一个随机数。和对象内存地址无关。

1.5. 哈希碰撞 (哈希冲突) 解决方案

1.6. 装填因子

装填因子 a = 总键值对数 /  哈希表总长度

2. 版本变化

jdk7 和 jdk8 的区别

1. 初始 table 容量
   jdk7: 创建 HashMap 对象时，则初始 table 容量为 16
   jdk8: 创建 HashMap 对象时，没有初始 table，仅仅只是初始加载因子。只有当第一次添加时才会初始 table 容量为 16.

2. 存储类型
   jdk7: table 的类型为 Entry
   jdk8: table 的类型为 Node

3. 存储结构
   jdk7: 哈希表为数组 + 链表，不管链表的总结点数是多少都不会变成树结构
   jdk8：哈希表为数组 + 链表 + 红黑树，当链表的节点数>=8 && 桶的总个数（table 的容量、数组的长度）>=64 时，会将链表结构变成红黑树结构

2.1. JDK7 头插法

3. 遍历方式

public class TestHashMap {
  public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<>();

    //向集合中添加元素  key  value 进行添加  添加方法 put
    map.put("aa", 11);
    map.put("bb", 22);
    map.put("cc", 33);
    map.put("cc", 33);
    map.put(null, 44);

    //获取存储键值个数
    System.out.println(map.size());

    //是否包含指定的key
    System.out.println(map.containsKey("cc"));
    System.out.println(map.containsKey("dd"));

    //根据key获取value
    System.out.println(map.get("cc"));

    //根据key  删除键值对  返回被删除的值
    Integer cc = map.remove("cc");
    System.out.println(cc);

    //遍历
    /*
         * 键遍历
         * 值遍历
         * 键值遍历
         * */
    //键遍历  获取所有的键
    Set<String> strings = map.keySet();
    for (String key : strings) {
      System.out.println("key-> " + key + " value-> " + map.get(key));
    }

    //值遍历
    Collection<Integer> values = map.values();
    for (Integer value : values) {
      System.out.println(value);
    }

    //键值遍历
    Set<Map.Entry<String, Integer>> entries = map.entrySet();
    for (Map.Entry<String, Integer> entry : entries) {
      System.out.println(entry.getKey() + "- " + entry.getValue());
    }
  }
}

4. 实现逻辑

4.1. put 放入数据⭐️🔴

流程图请看 https://www.processon.com/view/635b8a0d637689731714be29?fromnew=1

当第一次添加时，将初始 table 容量为 16，临界值为 12
每次添加调用 putVal 方法：

①先获取 key 的二次哈希值与 (数组长度 n)-1 进行取与运算，得出存放的位置

②判断该存放位置上是否有元素，如果没有直接存放

如果该存放位置上已有元素，则进行继续判断：

​ 如果和当前元素直接相等，则覆盖
​ 如果不相等，则继续判断是否是链表结构还是树状结构，按照对应结构的判断方式判断相等

③将 size 更新，判断是否超过了临界值，如果超过了，则需要重新 resize() 进行 2 倍 扩容，并打乱原来的顺序，重新排列

重新排列，为了减少碰撞

④当一个桶中的链表的节点数>=8 && 桶的总个数（table 的容量）>=64 时，会将链表结构变成红黑树结构

4.1.1. 二次哈希

二次哈希指的是将哈希码的高 16 位与低 16 位进行异或运算得到的加工过的哈希码

4.1.2. 区别

4.2. hashCode() equals()

4.3. 加载因子

[[../../../../cubox/006-ChromeCapture/20221027-面试官：为什么 HashMap 的加载因子是0.75？-技术圈]]

加载因子为 0.75，链表长度超过 8 时，转为红黑树，原因？

均值取 0.5 时，根据泊松分布公式 ，可以得到以下结果：

* threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

在理想情况下，使用随机哈希码，在扩容阈值（加载因子）为 0.75 的情况下，节点出现在频率在 Hash 桶（表）中遵循参数平均为 0.5 的泊松分布。忽略方差，即 X = λt，P(λt = k)，其中λt = 0.5 的情况，按公式：

计算结果如上述的列表所示，当一个 bin 中的链表长度达到 8 个元素的时候，概率为 0.00000006，几乎是一个不可能事件。

所以我们可以知道，其实常数 0.5 是作为参数代入泊松分布来计算的，而加载因子 0.75 是作为一个条件，当 HashMap 长度为 length/size ≥ 0.75 时就扩容，在这个条件下，冲突后的拉链长度和概率结果为：

0:    0.60653066  
1:    0.30326533  
2:    0.07581633  
3:    0.01263606  
4:    0.00157952  
5:    0.00015795  
6:    0.00001316  
7:    0.00000094  
8:    0.00000006

4.3.1. 0.5 的来历

1. λ 代表的就是单位时间或单位面积特定事件出现的平均次数，关于一个 key 是否发生碰撞的概率为 0.5。
2. 网络推断

如果观察的事件在单位时间或单位面积出现的平均次数保持不变，并且不同时段或空间区域内事件的发生是相互独立的，那么单位时间或单位面积该事件出现的实际次数 X 服从 泊松分布（Poisson distribution） ，记作 X～P （ λ ）。

具体地， X=k 的概率可表示为：

其中， λ >0。

可以进一步推导得到泊松分布的均值和方差均为 λ ，即：

因此， λ 代表的就是单位时间或单位面积特定事件出现的平均次数。

二项分布的极限是柏松分布，我们可以根据二项分布的期望 λ=np 求出 λ（n 是实验的次数，p 是单次的概率）。如果 n 比较大，p 比较小，所以我们才说满足泊松分布的条件。

4.3.2. 与 8 的关系

时间和空间成本的权衡 ==> 决定了扩容因子是 0.75 ==> 决定了泊松分布的参数λ是 0.5 ==> 计算出泊松分布结果为 8 时，概率为亿分之六 ==> 决定了树化节点为 8.
[[../../../../cubox/006-ChromeCapture/20221028-从泊松分布谈起HashMap为什么默认扩容因子是0.75 - 知乎]]

4.4. 树化

// TREEIFY_THRESHOLD为8，如果tab.length>=64也满足，树化时一个桶的节点数为9
// 因为binCount=0时已经有1个头节点，又加了一个节点，是2个，
// 循环到binCount=7时7>=8-1成立，所以此时生成的树有7+2个节点
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;  
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
    //申明tab 和 p 用于操作原数组和结点
    Node<K,V>[] tab; Node<K,V> p;
    int n, i;
    //如果原数组是空或者原数组的长度等于0，那么通过resize()方法进行创建初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        //获取到创建后数组的长度n
        n = (tab = resize()).length;

    //通过key的hash值和 数组长度-1 计算出存储元素结点的数组中位置（和1.7一样）
    //并且，如果该位置为空时，则直接创建元素结点赋值给该位置，后继元素结点为null
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //否则，说明该位置存在元素
        Node<K,V> e; K k;
        //判断table[i]的元素的key是否与添加的key相同，若相同则直接用新value覆盖旧value
        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 {
            //遍历table[i]，并判断添加的key是否已经存在，和之前判断一样，hash和equals
            //遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
            for (int binCount = 0; ; ++binCount) {
                //如果遍历的下一个结点为空，那么直接插入
                //该方法是尾插法（与1.7不同）
                //将p的next赋值给e进行以下判断
                if ((e = p.next) == null) {
                    //直接创建新结点连接在上一个结点的后继上
                    p.next = newNode(hash, key, value, null);
				//如果插入结点后，链表的结点数大于等7（8-1，即大于8）时，则进行红黑树的转换
				//注意:不仅仅是链表大于8，并且会在treeifyBin方法中判断数组是否为空或数组长度是否小于64
				//如果小于64则进行扩容，并且不是直接转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    //完成后直接退出循环
                    break;
                }
                //不退出循环时，则判断两个元素的key是否相同
                //若相同，则直接退出循环，进行下面替换的操作
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //否则，让p指向下一个元素结点
                p = e;
            }
        }
        //接着上面的第二个break，如果e不为空，直接用新value覆盖旧value并且返回旧value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //添加成功后，判断实际存在的键值对数量size是否大于扩容阈值threshold（第一次时为12）
    if (++size > threshold)
        //若大于，扩容
        resize();
    //添加成功时会调用的方法（默认实现为空）
    afterNodeInsertion(evict);
    return null;
}

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，桶就是数组
链表长度超过 8

4.5. 链化

基本思想是当红黑树中的元素减少并小于一定数量时，会切换回链表。而元素减少有两种情况：

• 1、调用 map 的 remove 方法删除元素

hashMap 的 remove 方法，会进入到 removeNode 方法，找到要删除的节点，并判断 node 类型是否为 treeNode，然后进入删除红黑树节点逻辑的 removeTreeNode 方法中，该方法有关解除红黑树结构的分支如下：

//判断是否要解除红黑树的条件
if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
复制代码

可以看到，此处并没有利用到网上所说的，当节点数小于UNTREEIFY_THRESHOLD时才转换，而是通过红黑树根节点及其子节点是否为空来判断。而满足该条件的最大红黑树结构如下： 节点数为 10，大于 UNTREEIFY_THRESHOLD（6），但是根据该方法的逻辑判断，还是需要转换为链表的。

• 2、resize 的时候，对红黑树进行了拆分

resize 的时候，判断节点类型，如果是链表，则将链表拆分，如果是 TreeNode，则执行 TreeNode 的 split 方法分割红黑树，而 split 方法中将红黑树转换为链表的分支如下：

//在这之前的逻辑是将红黑树每个节点的hash和一个bit进行&运算，
//根据运算结果将树划分为两棵红黑树，lc表示其中一棵树的节点数
if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
复制代码

这里才用到了 UNTREEIFY_THRESHOLD 的判断，当红黑树节点元素小于等于 6 时，才调用 untreeify 方法转换回链表

[[../../../../cubox/006-ChromeCapture/20221027-jdk1.8的hashmap真的是大于8就转换成红黑树，小于6就变成链表吗 - 掘金]]

4.6. resize（rehash）

当 HashMap 中的元素越来越多的时候，hash 冲突的几率也就越来越高，因为数组的
长度是固定的。所以为了提高查询的效率，就要对 HashMap 的数组进行扩容，数组扩容
这个操作也会出现在 ArrayList 中，这是一个常用的操作，而在 HashMap 数组扩容之后，
最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，
这就是 resize。

那么 HashMap 什么时候进行扩容呢？当 HashMap 中的元素个数超过数组大小
loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，这是一个折中的取值。
也就是说，默认情况下，数组大小为 16，那么当 HashMap 中元素个数超过 16*0.75=12
的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中
的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap 中元素的个
数，那么预设元素的个数能够有效的提高 HashMap 的性能。

HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算 （n-1）& hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到“原位置 + 旧容量”这个位置。
例如，原来的容量为 32，那么应该拿 hash 跟 31（0x11111）做与操作；在扩容扩到了 64 的容量之后，应该拿 hash 跟 63（0x111111）做与操作。新容量跟原来相比只是多了一个 bit 位，假设原来的位置在 23，那么当新增的那个 bit 位的计算结果为 0 时，那么该节点还是在 23；相反，计算结果为 1 时，则该节点会被分配到 23+31 的桶上。
正是因为这样巧妙的 rehash 方式，保证了 rehash 之后每个桶上的节点数必定小于等于原来桶上的节点数，即保证了 rehash 之后不会出现更严重的冲突。

[[../../../../cubox/006-ChromeCapture/20221028-HashMap常见问题_Android_la的博客-CSDN博客]]
[[../../../../cubox/006-ChromeCapture/20221028-史上最全HashMap面试题汇总_原野的稻草人的博客-CSDN博客_hashmap面试题]]

4.7. rehash

4.8. Fail-Fast 机制-modCount

%%
▶4.🏡⭐️◼️【🌈费曼无敌🌈⭐️第一步⭐️】◼️⭐️-point-20230411-1745%%❕ ^43oza9

我们知道 java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了 map，那么将抛出 ConcurrentModificationException，这就是所谓 fail-fast策略。
这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对 HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。

在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：
注意到 modCount 声明为 volatile，保证线程之间修改的可见性。
这里说的 volatile 是在 JDK5 和 JDK6 的时候，也许是正确的，因为在 JDK5 和 JDK6 中变量 modCount 确实声明为 volatile。但在 JDK7 和 JDK8 中，已经没有这样声明了！！！！！
由所有 HashMap 类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

4.8.1. 其他作用

ConcurrentHashMap 中 size 方法中用来判断是否是稳定有效的 size，最少 2 次比较，最多 4 次，4 次后加锁

4.9. 扩容死锁与环链行程

[[20221029-JDK1.7版本HashMap的源码分析_老dubbo的博客-CSDN博客]]
https://blog.csdn.net/aidaowuqiong/article/details/103492264

https://www.bilibili.com/video/BV1mT4y177YC/?vd_source=c5b2d0d7bc377c0c35dbc251d95cf204

4.10. 扩容优化

4.10.1. 区别

4.10.2. 哪些位置需要换桶

[[../../../../cubox/006-ChromeCapture/20221104-HashMap扩容时的rehash方法中(e.hash & oldCap) == 0详解 - CodeAntenna]]

4.11. null 键 null 值

HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值 (多个) 和 null 键 (1 个)。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

// JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
      // 1. 取hashCode值： h = key.hashCode() 
      // 2. 高位参与低位的运算：h ^ (h >>> 16)  
      static final int hash(Object key) {
           int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
            // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
            // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
     }

4.12. 2 的 N 次方⭐️🔴

4.12.1. 原因

新索引值=二次哈希值 &（当前容量 -1）

之所以底层数组的长度是 2 的整数次幂，是因为让按位与运算与取模运算结果相等

原因分析：

1. 提高 hash 效率：因为这里的哈希算法是用的除留取余法，即要做取模运算，为了提高效率，转变为按位与运算，而要想结果相等，就要求容量值为 2 的整数次幂，否则除留取余无法转变成按位与运算。
   运算相比于取模运算速度大幅度提升 (按照 Bruce Eckel 给出的数据，大约可以提升 5～8 倍）。

2. 充分利用空间：如果不是 2 的 n 次方，有些位置可能为 0，与任何数做与运算都是 0，导致无法获取到数组的某些角标位置，造成空间浪费。

3. 减少 hash 碰撞：为 2 的 n 次方时，2n-1 得到的二进制数的每个位上的值都为 1，这使得在低位上&时，得到的和原 hash 的低位相同，加之 hash(int h) 方法对 key 的 hashCode 的进一步优化，加入了高位计算，就使得只有相同的 hash 值的两个值才会被放到数组中的同一个位置上形成链表。所以说，当数组长度为 2 的 n 次幂的时候，不同的 key 算得得 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
   

4. 扩容判断优化：1.8 中的高低位也用到了 n-1 低位都为 1 的特性，即上文所说，每次扩容都是翻倍，与原来计算 （n-1）& hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到“原位置 + 旧容量”这个位置。

   4.12.2. 源码

   

5. 红黑树

红黑树是平衡二叉树的一种实现方式，另一种实现方式是最初的 AVL 树。

TreeSet TreeMap 中里都是红黑树

6. hash 索引与 B 树索引的区别

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像 B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的 IO 访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。

（1）Hash 索引仅仅能满足”=”,”IN” 和”<=>” 查询，不能使用范围查询。 
由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和 Hash 运算前完全一样。

（2）Hash 索引无法被用来避免数据的排序操作。 
由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且 Hash 值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

（3）Hash 索引不能利用部分索引键查询。 
对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。

（4）Hash 索引在任何时候都不能避免表扫描。 
前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash 运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

（5）Hash 索引遇到大量 Hash 值相等的情况后性能并不一定就会比 B-Tree 索引高。 
对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

7. 各种比较

                                   底层结构      版本		 线程安全（同步）	允许null键null值

底层结构：哈希表
jdk7: 数组 + 链表
jdk8: 数组 + 链表 + 红黑树

源码分析：
jdk8： HashMap 中维护了 Node 类型的数组 table，当 HashMap 创建对象时，只是对 loadFactor 初始化为 0.75；table 还是保持默认值 null

当第一次添加时，将初始table容量为16，临界值为12
每次添加调用putVal方法：
    ①先获取key的二次哈希值并进行取与运算，得出存放的位置
    ②判断该存放位置上是否有元素，如果没有直接存放

     如果该存放位置上已有元素，则进行继续判断：
                            如果和当前元素直接相等，则覆盖
                            如果不相等，则继续判断是否是链表结构还是树状结构，按照对应结构的判断方式判断相等

    ③将size更新，判断是否超过了临界值，如果超过了，则需要重新resize()进行2倍扩容，并打乱原来的顺序，重新排列

    ④<span style="background-color:#ff00ff">当一个桶中的链表的节点数>=8 &&  桶的总个数（table的容量）>=64时，会将链表结构变成红黑树结构</span>

jdk7 和 jdk8 的区别
1.jdk7: 创建 HashMap 对象时，则初始 table 容量为 16
jdk8: 创建 HashMap 对象时，没有初始 table，仅仅只是初始加载因子。只有当第一次添加时才会初始 table 容量为 16.

2.jdk7:table的类型为Entry
  jdk8:table的类型为Node

3.jdk7:哈希表为数组+链表，不管链表的总结点数是多少都不会变成树结构
  jdk8：哈希表为数组+链表+红黑树，当链表的节点数>=8 &&  桶的总个数（table的容量）>=64时，会将链表结构变成红黑树结构

应用层面：

    要求添加元素的key重写hashCode和equals方法

8. 泊松分布

9. 特点

10. 防止哈希碰撞的措施⭐️🔴

 * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
 * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算

   /**
     * 分析1：hash(key)
     * 作用：计算传入数据的哈希码（哈希值、Hash值）
     * 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
     * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
     * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
     */

      // JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
      static final int hash(int h) {
        h ^= k.hashCode(); 
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
     }

      // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
      // 1. 取hashCode值： h = key.hashCode() 
      // 2. 高位参与低位的运算：h ^ (h >>> 16)  
      static final int hash(Object key) {
           int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
            // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
            // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
     }

   /**
     * 计算存储位置的函数分析：indexFor(hash, table.length)
     * 注：该函数仅存在于JDK 1.7 ，JDK 1.8中实际上无该函数（直接用1条语句判断写出），但原理相同
     * 为了方便讲解，故提前到此讲解
     */
     static int indexFor(int h, int length) {  
          return h & (length-1); 
          // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
          }
复制代码

11. 参考

11.1. 黑马

11.1.1. 视频

https://www.bilibili.com/video/BV1A741127DP/?p=2&spm_id_from=pageDriver&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204

11.1.2. 资料

/Users/taylor/Nutstore Files/Obsidian_data/pages/002-schdule/001-Arch/001-Subject/001-基础知识专题/001-集合框架/黑马-HashMap

11.2. old

Java 并发编程全套视频教程（JMM+AQS+synchronized+hashmap）
https://www.bilibili.com/video/BV17c411h7Vw/?spm_id_from=333.337.search-card.all.click&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204

https://juejin.im/post/5aa5d8d26fb9a028d2079264

[[../../../../cubox/006-ChromeCapture/20221028-Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？ - 掘金]]

https://www.bilibili.com/video/BV15Q4y1e7q6?p=6&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204

[[../../../../cubox/006-ChromeCapture/20221104-Java 8系列之重新认识HashMap - 美团技术团队]]