哈希表

TreeMap 分析

1. 时间复杂度(平均)

   • 添加、删除、搜索: O(logn)

2. 特点

   • Key 必须具备可比较性
   • 元素的分布是有顺序的

3. 在实际应用中，很多时候的需求

   • Map 中存储的元素不需要讲究顺序
   • Map 中的 Key 不需要具备可比较性

4. 不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1)

   • 那就是采取哈希表来实现 Map

初始哈希表

空间换时间：一开始数组里面的索引肯定是比 key 的数量多的。浪费了一定的空间。

哈希冲突

JDK8的哈希冲突解决方案

哈希函数

1、哈希表中哈希函数的实现步骤大概如下

• 用与运算（&）效率更高，一个【2 的 n 次方】的数【减一】，它的二进制一定全是 1。
• 两个二进制数做与运算，运算结果一定是小于等于 table.length-1 的。（以下图的与运算为例）
• 即最终得出来结果其实就是【0 到 table.length-1】，也就是【数组索引值】。

❗❗❗ hash_code & (table.length-1) 实际上就是保留 hash_code 的二进制表示中的低位，忽略掉高位（因为低位们就是余数）。

❗❗❗ 这样就能保证取模运算 hash_code % length 的效果和位运算 hash_code & (table.length-1) 是一样的，但是位运算的速度更快。

2^1 == 010
2^1 - 1 == 001 == 1
  
2^2 == 100
2^2 - 1 == 011 == 11

 10101       10111
&00111      &00111
-------     ------- 
 00101       00111
  

2、良好的哈希函数

1. 让哈希值更加均匀分布 -> 减少哈希冲突次数 -> 提升哈希表的性能。
2. 比如说我们索引是 0 - 100，我们算出来这个索引可能是这个索引范围内的任何位置
   • 如果算出来的索引几乎都集中在前半部分，比如说索引几乎都集中在 0- 50 这个范围，那这样的话就可能会导致哈希冲突比较严重。

哈希值计算

如何生成 key 的哈希值

key 的常见种类可能有：

1. 整数、浮点数、字符串、自定义对象
2. 不同种类的 key，哈希值的生成方式不一样，但目标是一致的
   • 尽量让每个 key 的哈希值是唯一的
   • 尽量让 key 的所有信息参与运算

在 Java 中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null

int 和 float 的哈希值

1. 整数

• 整数值当做哈希值比如 10 的哈希值就是 10

• public static int hashCode(int value) {
    return value;
  }
  

2. 浮点数

• 将存储的二进制格式转为整数值

• public static int hashCode(float value) {
    return floatToIntBits(value);
  }
  

比如浮点数 10.6f 在内存中实际上存储的就是二进制数据

// 哈希值
int code = Float.floatToIntBits(10.6f);
System.out.printIn(code);
System.out.println(Integer.toBinaryString(code));

// 控制台输出
1093245338
10000010010101100110110011010

Long 和 Double 的哈希值

long 和 double 都是 8 个字节，即 64 位。

而哈希值必须是 int，即 32 位。所以需要计算。

需注意以下几点：

1. 用异或运算（^）和无符号右移（>>>）
2. 高 32 位和低 32 位进行异或算出 32 位的哈希值
3. 要充分利用所有信息计算出哈希值

计算 long 类型：

public static int hashCode(long value) {
  return (int)(value ^ (value >>> 32));
}

计算 double 类型：

public static int hashCode(double value) {
  long bits = doubleToLongBits(value);
  return (int)(bits ^ (bits >>> 32));
}

具体如下图所示：

用【原数值的低位】和【无符号右移得到的高位】进行【异或运算】。

字符串的哈希值

字符串的哈希值计算如下：

在 JDK 中，（乘法因子）乘数 n 为 31，为什么会使用 31？

原因分析：

1. 31 不仅仅是符合 2^n-1，它还是个奇素数(既是奇数，又是素数)
2. 素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
3. 最终选择 31 是经过观测分布结果后的选择

素数是指大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。

主要有以下两个优势：

1. **位运算优势：**31 的二进制表示是 11111，这个特性使得在进行乘法运算时，可以通过移位和减法的组合来实现，提高了效率。
2. 素数的好处： 31 是一个奇数中的素数，这有助于避免乘法溢出时产生相同的低位结果。如果使用偶数，可能会导致在哈希值的低位上丢失信息。
   • 这就使得 JVM 能够通过位运算来优化乘法操作。具体来说，JVM 会将 31 * i 优化成 (i << 5) - i
   • 因为 2^5 == 32, 左移一位相当于乘于一个 2，所以 31 * i == i * 2^5 - i == (i << 5) - i

总之，选择 31 是为了在字符串哈希计算中充分利用计算机的位运算和乘法优化，以提高效率和性能。

源码分析：

public int hashCode() {
    int h = hash; // 步骤 1：检查是否已计算哈希值
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            // 步骤 2：使用乘法因子 31 计算哈希
            // 通过将当前哈希乘以 31 并加上当前字符的 Unicode 编码来更新哈希
            h = 31 * h + val[i];
        }
        // 步骤 3：缓存计算的哈希值以便将来使用
        hash = h;
    }
    // 步骤 4：返回计算的哈希值
    return h;
}

这是 String 类中的 hashCode 方法的源码。这方法的目的是计算字符串的哈希值，以便在哈希表等数据结构中使用。

具体说明：

1. 首先，它检查 hash 变量是否已经计算过哈希值，如果是，则直接返回这个哈希值。
2. 如果 hash 为 0（表示没有计算过哈希值），并且字符串长度大于 0，那么就进入计算哈希值的过程。
3. 使用 31 作为乘数，遍历字符串的每一个字符，不断更新哈希值。更新的方式是将当前哈希值乘以 31，然后加上当前字符的 Unicode 编码值。这里使用了位运算和加法，而不是直接进行乘法操作，这是因为位运算和加法在计算机中更为高效。
4. 最后，将计算得到的哈希值赋给 hash 变量，并返回这个哈希值。

这种哈希计算方法具有一定的效率和均匀分布的特点，适用于一般的字符串。通过遍历每个字符，以字符的 Unicode 编码值来影响最终的哈希值，从而保证字符串中每个字符都有影响。这样设计的目的是尽可能减小哈希冲突的概率。

自定义对象的哈希值⭐️

如何计算自定义对象的哈希值呢？

• 假设现在有一个对象 person。
• 把 person 当作是字符串，把 person 当作字符串，然后这每一个哈希值当作是每一个字符。

代码如下：

	@Override
	public int hashCode() {
		int hashCode = Integer.hashCode(age);
		hashCode = hashCode * 31 + Float.hashCode(height);
		hashCode = hashCode * 31 + (name != null ? name.hashCode() : 0);
		return hashCode;
	}

思考：

1、哈希值太大，整型溢出怎么办？

不用做任何处理，只要最后返回的是一个 int 类型的值就行。

2、如果不重写 hashCode() 会怎么样？⭐️

• 自定义的对象，如果不重写哈希值的话，那么它最终生成的哈希值会和这个对象的【内存地址】直接挂钩的。
• 会利用它默认的哈希值，也就是内存相关的哈希值，由它认定为内存地址相等的对象，哈希值才相等，所以导致的后果其实就是这两个会被当作不同的 key 来处理。
• 两个内容属性值相同的对象，返回的哈希值不一样。

@Data 注解生成的 hashCode() 和 MybatisX 插件生成的 hashCode() 不一样

总结

• 哈希值必须是整数（int），也就是 32 字节。
• 可能为正数，也可能为负数，但不会影响计算【索引值】。（因为索引值的计算是位运算，且一定是在某个范围内）

equals

引言⭐️

首先得明确以下几点：

• 哈希值一样，索引绝对一样

• 哈希值不一样，索引也可能一样

•  11000         10000   --- 哈希值
    &111          &111
  -------       -------
     000           000   --- 索引值
  

所以在判断两个对象是否相等时，需要用到 equals 方法，equals 和 hashCode 是两个不同的方法。

1. hashCode -- 用来寻找索引值
2. equals -- 用来判断两个 key 是否相等，如果相等就覆盖值

先利用 hashCode 计算哈希值，然后再利用哈希函数 hash 获取索引值，最后利用 equals 判断两者是否真的相等。

	@Override
	/**
	 * 用来比较2个对象是否相等
	 */
	public boolean equals(Object obj) {
		// 内存地址
		if (this == obj) return true;
		if (obj == null || obj.getClass() != getClass()) return false; // 遇到子类时，判断为 不相等，这种写法比较合理
		// if (obj == null || !(obj instanceof Person)) return false; // 遇到子类时，判断为 相等
		
		// 比较成员变量
		Person person = (Person) obj;
		return person.age == age
				&& person.height == height
				&& (person.name == null ? name == null : person.name.equals(name));
	}

默认的 equals 是比较内存地址是否相等

只实现 equals

假设有两个 Person 对象：p1 和 p2。

只实现 equals，不实现 hashCode，会导致判断时不稳定。

1. 此时 p1 和 p2 的哈希值是跟内存地址有关的，哈希值绝对不一样，但是索引值有可能一样。
2. 假设索引值一样，就会调用实现的 equals 方法，两个对象最后一样，最后 p2 的值会覆盖 p1 的值。
3. 如果索引值不一样，就不会覆盖。
4. 所以说这种做法不稳定，不建议只实现 equals。

只实现 hashCode

	public static void main(String[] args) {
		Person p1 = new Person(10, 1.67f, "jack");
		Person p2 = new Person(10, 1.67f, "jack");

		HashMap<Object, Object> map = new HashMap<>();
		map.put(p1, "abc");
		map.put("test", "ccc");
		map.put(p2, "bcd");
		System.out.println("map.size() = " + map.size());

	}

代码分析：

1. 此时，p1 和 p2 的哈希值相等，索引值也就必然相等
2. 但是由于只实现了 hashCode，所以两者在 equals 比较时为不相等
3. 而 test 与其他两者相比都不相等

自定义对象作为 key

自定义对象作为 key，最好同时重写 hashCode 、equals 方法

1. equals：用来判断 2 个 key 是否为同一个 key
   • 自反性: 对于任何非 null 的 x，x.equals(x) 必须返回 true
   • 对称性: 对于任何非 null 的 x、y，如果 y.equals(x) 返回 true，x.equals(y) 必须返回 true
   • 传递性: 对于任何非 null 的 x、y、z，如果 x.equals(y)、y.eguals(z) 返回 true，那么 x.equals(z) 必须反回 true
   • 一致性: 对于任何非 null 的 y，只要 equals 的比较操作在对象中所用的信息没有被修改，多次调用 x.equals(y) 就会一致地返回 true，或者一致地返回 false
   • 对于任何非 null 的 x，x.equals(null) 必须返回 false
2. hashCode：必须保证 equals 为 true 的 2 个 key 的哈希值一样
3. 反过来 hashCode 相等的 key，不一定 equals 为 true

关于使用 % 来计算索引

此时，建议哈希表的长度(size)为素数。（质数）

下方表格列出了不同数据规模对应的最佳素数，特点如下

• 每个素数略小于前一个素数的 2 倍
• 每个素数尽可能接近 2 的幂(2^n)

HashMap 源码分析

常量和阈值

注意树化的阈值是：

1. 链表长度超过这个阈值（>=9）时。
2. 当哈希表的容量（>=64）时。（当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）

    // 默认的初始容量，即哈希表在创建时的默认大小。它被设置为 16，使用了位运算 1 << 4 来表示 2 的 4 次方，即 16。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	
	// 哈希表允许的最大容量。它被设置为 2 的 30 次方，即 1073741824。
    static final int MAXIMUM_CAPACITY = 1 << 30;

	// 默认的负载因子。负载因子是表示哈希表在什么时候会进行扩容的一个因子。当哈希表中的元素数量超过容量乘以负载因子时，哈希表将会进行扩容。默认负载因子是 0.75。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

	// 当哈希桶中的链表长度超过这个阈值（>=9）时，链表将会被转化为红黑树。这是为了提高在链表中查找元素的效率。
    static final int TREEIFY_THRESHOLD = 8;

	// 当哈希桶中的红黑树节点数量小于这个阈值时，红黑树将会被转化为链表。
    static final int UNTREEIFY_THRESHOLD = 6;

	// 当哈希表的容量小于这个值时，不会进行红黑树化，即不会将链表转化为红黑树。
    static final int MIN_TREEIFY_CAPACITY = 64;

哈希函数

其中，hash ^ (hash >>> 16 是为了保险起见，因为无法确定传进来的这个key，实现的 hashCode() 均不均匀

1. key 为 null 时，返回 0；
2. 不为 null 时，哈希值的低 16 位和 高 16 位异或。

    static final int hash(Object key) {
        int h;
        // hash ^ (hash >>> 16 是为了保险起见，因为无法确定传进来的这个key，实现的 hashCode() 均不均匀
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

put 方法

1、put(K key, V value)

    public V put(K key, V value) {
        // 表示 不仅仅在键不存在时才插入，在插入后可能触发一些处理
        return putVal(hash(key), key, value, false, true);
    }

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

• 用于将键值对放入哈希表；
• 其中，binCount 为 0 时，意味着链表的大小为 2 == 0 + 2。

参数分析：

1. onlyIfAbsent（第四个参数）：
   • 如果 onlyIfAbsent 为 true，表示仅在当前哈希表中不存在指定键（key）时才执行插入操作。
   • 如果 onlyIfAbsent 为 false，则不考虑哈希表中是否已经存在指定键，直接执行插入操作。
2. evict（第五个参数）：
   • 如果 evict 为 true，表示在执行插入操作后，可能触发一些处理，例如在插入新键值对后，会检查是否需要进行扩容或将链表转为红黑树，从而保持哈希表的性能和结构。
   • 如果 evict 为 false，表示插入新键值对后，不进行上述的检查和调整，仅简单地插入键值对。

方法分析：

1. 根据键的哈希值计算出在哈希表数组中的位置，如果该位置为空，则直接插入新节点；
2. 如果不为空，则根据节点类型进行不同的处理，可能是链表节点，也可能是红黑树节点。
3. 如果节点存在相同的键，则更新该节点的值。
4. 最后，根据哈希表的当前状态，（节点）可能进行扩容或将链表转为红黑树。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // 声明哈希表数组
    Node<K,V> p;      // 声明节点变量
    int n, i;

    // 如果哈希表为空或长度为 0，则进行扩容
    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;

        // 如果位置不为空，判断当前节点是否是目标节点
        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 和 size
    ++modCount;
    if (++size > threshold)
        resize();
    // 新增键值对后的操作
    afterNodeInsertion(evict);
    return null;
}

扩容 resize

这个方法主要作用是：对 HashMap 进行扩容，以适应更多的键值对，并在扩容时迁移旧数据到新的数组中。。

/**
 * 对HashMap进行扩容，调整数组大小，并迁移数据。
 *
 * @return 扩容后的新数组
 */
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) {
        // 如果旧的容量已经达到最大容量，直接将阈值设为 Integer.MAX_VALUE，不进行扩容
        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
    }
    // 如果旧的哈希表容量为 0 且有初始阈值
    else if (oldThr > 0)
        // 新的容量为旧的阈值
        newCap = oldThr;
    // 如果旧的容量和阈值都为 0，使用默认初始容量和阈值
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        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) {
                // 将旧数组中的槽置为 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;
                    // 将链表节点按照哈希值的最高位是否为 0 分为两组
                    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;
}

LinkHashMap 源码分析

部分成员变量

主要描述了 LinkedHashMap 中的双向链表结构和迭代顺序的属性。

1. head和tail：
   • head 是双向链表的头部，指向最老的元素（最早插入的元素）。
   • tail 是双向链表的尾部，指向最新插入的元素。
2. accessOrder：
   • 这是一个布尔值，表示 LinkedHashMap 的迭代顺序是基于【访问顺序】还是【插入顺序】。
   • 如果 accessOrder 为 true，则表示迭代顺序是基于访问顺序，即最近访问的元素排在最前面。
   • 如果 accessOrder 为 false，则表示迭代顺序是基于插入顺序，即元素按照插入的顺序排列。

这种灵活性使得 LinkedHashMap 既可以按照插入顺序来迭代，也可以按照访问顺序来迭代。这对于实现 LRU（Least Recently Used）缓存非常有用，因为可以基于访问顺序轻松实现【缓存淘汰策略】。

此外，transient 关键字表示：这两个字段不会被默认的序列化机制保存，因为 LinkedHashMap 类提供了自己的序列化机制。

    /**
     * The head (eldest) of the doubly linked list. -- 双链表的头（最早插入的元素）。
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list. -- 双链表的尾部（最新插入的元素）。
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * 表示LinkedHashMap的迭代顺序
     *
     * @serial
     */
    final boolean accessOrder;