记录记录笔记：

一.原理：

HashMap 就是基于散列表也就是Hash表的数据结构，通过（key-Value）来存储数据的，key不可重复，Value可以重复的，通过key的哈希值与与数组大小-1按位与来获取元素在数组中的位置，然后通过数组＋连表＋（java8之后就是数组+链表+红黑树）实现的！！！来处理哈希冲突的。

哈希冲突又是什么？

哈希冲突就是多个key的哈希值与数组大小-1按位与 映射到同一个数组的位置（hash算法本来就可能冲突，且数组大小是有限的）：tab[i = (n - 1) & hash])，导致Hash冲突。

        解决Hash冲突的方法常用就是拉链法（链地址法）：将哈希表中每个槽的位置变成一个链表，当多个键的哈希值相同时，且不是相同的对象，将它们存储在同一个链表。也就是同一个桶中的不同位置。

        JDK1.7及之前链表的插入采用的都是头查法，每当发生哈希冲突的时候，不是相同的对象的时候，新的节点总是插在链表的头部，老节点依次向后移动，并且新节点自然就指向的是后面老节点。比如进来的顺序先是C B A,然后链表的结构就是 A ->B ->C (A指向B，B指向C ，C指向NULL)

但是在多线程环境下，头查法可能导致链表形成环，特别是在并发扩容的时候。JDK1.8的时候，就改成了尾插法，即新的节点插入到链表的尾部，保持插入的顺序，并且引入了红黑树。当链表的长度大于8且数组大小大于等于64的时候，就把链表转化成红黑树，（红黑树是一种自平衡二叉搜索树，能够将最坏情况下的查找复杂度从O(n)降低到O(Iogn)）当红黑树节点小于6的时
候，又会退化成链表。

插曲一下：  计算key的hash值得时候：

h = key.hashCode()) ^ (h >>> 16 是 Java 中用于优化哈希值分布的一种常见技巧，通常用于哈希表（如 HashMap）的实现中。它的目的是通过将哈希码的高位信息混合到低位中，来减少哈希冲突的概率。

2. 为什么要这样做？

(1) 哈希码的范围问题

• Java 的 hashCode() 返回的是一个 32 位的整数（int 类型），范围是 -2^31 到 2^31-1。

• 在实际使用中，哈希表的大小通常远小于 2^32（例如 HashMap 的默认初始容量是 16），因此哈希码的高位信息通常会被忽略。

(2) 哈希冲突

• 如果直接使用 hashCode() 作为哈希值，可能会导致哈希冲突（即不同的对象映射到相同的索引）。

• 特别是当哈希表的大小较小时，低位相同的哈希码会导致大量冲突。

(3) 混合高位和低位

• 通过 h ^ (h >>> 16)，将哈希码的高 16 位信息混合到低 16 位中，可以增加哈希值的随机性。

• 这样可以有效减少哈希冲突，尤其是在哈希表大小较小的情况下。

列：

原始哈希码：
h = 0001 0010 0011 0100 0101 0110 0111 1000
右移动16位：
h >>> 16 = 0000 0000 0000 0000 0001 0010 0011 0100
异或操作：
h ^ (h >>> 16) = 0001 0010 0011 0100 0100 0100 0100 1100

 充分利用到高位被忽略，混淆到低位中去.

二.HashMap的put（）:

整体流程：

1.判断键值对数组table是否为空或为null，否则执行resize(进行扩容（初始化）
2.根据键值key计算hash值得到数组索引k
3.判断table[i]==null，条件成立，直接新建节点添加
4. 如果table[i]==null，不成立
        4.1判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
        4.2判断table[i]是否为treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对
        4.3遍历table[i，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在后续会据 onlyIfAbsent 参数决定是否覆盖值：如果 onlyIfAbsent 为 false，或者旧值为 null，则覆盖值。

5.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容。 

 源码部分：

// 这是HashMap的put方法，用于将键值对插入到HashMap中
public V put(K key, V value) {
    // 调用putVal方法，传入key的hash值、key、value等参数
    return putVal(hash(key), key, value, false, true);
}

/**
 * 实现Map.put及相关方法。
 *
 * @param hash key的hash值
 * @param key 键
 * @param value 要插入的值
 * @param onlyIfAbsent 如果为true，不改变已存在的值
 * @param evict 如果为false，表示表处于创建模式
 * @return 返回之前的值，如果没有则返回null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; // 用于存储HashMap的数组
    Node<K,V> p; // 当前节点
    int n, i; // n是数组长度，i是数组索引

    // 如果数组为空或者长度为0，进行扩容 初始大小为16，同时也会计算阈值为16*0.75=12
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 计算数组索引，如果该位置为空，直接插入新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; // 用于存储已存在的节点
        K k; // 用于存储当前节点的key

        // 如果当前节点的hash值和key与传入的hash值和key匹配
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 将当前节点赋值给e
        // 如果当前节点是树节点，调用树的插入方法
        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; // 继续遍历下一个节点
            }
        }
        // 判断找到的结点是否为null，如果是，则表示链表没有重复的key，正常添加了，否贼就得重新赋值了
        if (e != null) { // existing mapping for key
            V oldValue = e.value; // 获取旧值
            // 如果onlyIfAbsent为false或者旧值为null，更新值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 节点访问后回调
            return oldValue; // 返回旧值
        }
    }
    ++modCount; // 修改次数加1
    // 如果大小超过阈值，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); // 节点插入后回调
    return null; // 如果没有旧值，返回null
}

 初始扩容得部分：

三.HahsMap得扩容机制：

        HashMap中的扩容是基于负载因子(load factor)来决定的。默认情况下，HashMap的负载因子为0.75，这意味着当HashMap的已存储元素数量超过当前容量的75%时，就会触发扩容操作。
例如，初始容量为16，负载因子为0.75，则扩容阈值为16×0.75=12。当存入第13个元素时，HashMap就会触发扩容。
当触发扩容时，HashMap的容量会扩大为当前容量的两倍。例如，容量从16增加到32，从32增加到64等。
扩容时，HashMap需要重新计算所有元素的哈希值，并将它们重新分配到新的哈希桶中，这个过程称为rehashing。每个元素的存储位置会根据新容量的大小重新计算哈希值，并移动到新的数组中。

整体流程：

1. 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度＊0.75）
2. 每次扩容的时候，都是扩容之前容量的2倍；
3. 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中 开始遍历旧表中得每一个通
        没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置
        如果是红黑树，走红黑树的添加
        如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash&oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

但是这里rehashing有一个细节的地方：

就是当通的链表的时候，遍历的时候，

会拿当前节点的hash值与oldCap & 来看最高位是否为0，如果为0就是吃不到新数组的长度，就还是新数组原来位置，如果是1则就是旧数组的位置+旧数组的长度 (关键在于数组的长度是2的n次方。且扩容是2倍)        

解释:

因为数组的长度是2的n次方，所以假设以前的数组长度（16）二进制表示是010000，那么新数组的长度（32)二进制表示是100000.
它们之间的差别就在于高位多了一个1，而我们通过key的hash值定位其在数组位置所采用的方法是（数组长度-1)&hash。拿16和32长度来举例
16-1=15，二进制为 001111
32-1=31，二进制为 011111

之间的差别就在于高位多了一个1

所以直接拿老数组的长度比如16 二进制为010000
所以重点就在key的hash值的从右往左数第五位是否是1，如果是1说明需要搬迁到新位置，且新位置的下标就是原下标+16（原数组大小），如果是0说明吃不到新数组长度的高位，那就还是在原位置，不需要迁移。

所以，我们刚好拿老数组的长度（010000）来判断高位是否是1，这里只有两种情况，要么是1要么是0。

部分源码：

完整源码：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 保存旧的哈希表
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 旧表的容量
    int oldThr = threshold; // 旧的扩容阈值
    int newCap, newThr = 0; // 新表的容量和新阈值

    // 如果旧表容量大于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; // 新阈值为旧阈值的两倍
    }
    // 如果旧表容量为0，但旧阈值大于0（初始化时指定了容量）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr; // 新容量等于旧阈值
    // 如果旧表容量和阈值都为0（使用默认初始化）
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY; // 新容量为默认初始容量（16）
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新阈值为默认负载因子 * 默认容量
    }

    // 如果新阈值为0（某些情况下未计算新阈值）
    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 { // 如果当前桶是链表
                    Node<K,V> loHead = null, loTail = null; // 低位链表的头尾节点
                    Node<K,V> hiHead = null, hiTail = null; // 高位链表的头尾节点
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 根据节点的hash值判断是放入低位链表还是高位链表
                        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; // 返回新表
}

四.扩展：

HashSet 和HashMap的区别是什么？

HashSet 是基于HashMap 实现的集合类，不允许重复的元素，用于存储一组无序的唯一元素。

可以看看构造方法：

还有add()方法：

这里默认填了个PRESNET，实际上就是定义的一个Object没有任何意义，仅为了适配map需要一个value罢了。 

 我类个，这直接就不演了

因此HashSet就是封装了一下HashMap！，因此许多HashSet的操作（如add()、remove()等）实际上是调用HashMap的相应方法，内部的实现逻辑其实都由HashMap来代劳。

HashMap中java中为什么采用2得N次方：

HashMap采用2的n次方倍作为容量，主要是为了提高哈希值的分布均匀性和哈希计算的效率。

HashMap通过(n-1)&hash来计算元素存储的索引位置，这种位运算只有在数组容量是2的n次方时才能确保索引|均匀分布。位运算的效率高于取模运算（hash%n），提高了哈希计算的速度。
且当HashMap扩容时，通过容量为2的n次方，扩容时只需通过简单的位运算判断是否需要迁移，这减少了重新计算哈希值的开销，提升了rehash的效率

哈希分布均匀性
如果数组容量为2的n次方，那么n-1后低位都是1，此时进行&(两个位都为1时，结果才为1）运算可以确保哈希码的最低几位均匀分布。
比如64二进制表示为0100 0000，64-1=0011 1111。
此时00111111与哈希码进行&运算，低位能均匀的反应出哈希码的随机性。
假设来个01000000与哈希码进行&运算，那么低位得到的值就都是0了，随机性很差，都是冲突。

位运算与取模
正常情况下，如果基于哈希码来计算数组下标，我们想到的都是%（取余）计算。例如数组长度为5，那么哈希码%5得到的值就是对应的数组下标。但相比于位运算而言，效率比较低，所以推荐用位运算，而要满足i=(n－1)&hash这个公式，n的大小就必须是2的n次幂。即： 当b等于2的n次幂时,a%b操作等于a&（b- 1）

欧克，后续在慢慢补充吧！！！下一篇 ArrayList...