模拟解决哈希表冲突

目录

解决哈希表冲突原理：

模拟解决哈希表冲突代码：

负载因子：

动态扩容：

总结：

HashMap和HashSet的总结：

---

解决哈希表冲突原理：

        黑色代表一个数组，当 出现哈希冲突时（相同数组下标），该位置下标会变成一个链表（上图红色区域）。这样就能存储了。叫做开散列 / 哈希桶。链表长度超过阈值（默认8）时转为红黑树，优化冲突性能。

        虽然哈希表⼀直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是⼀个常数，所以，通常意义下，我们认为哈希表的插⼊/ 删除/查找时间复杂度是O(1）。

模拟解决哈希表冲突代码： private static class Node { private int key; private int value; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } private Node[] array; private int size; // 当前的数据个数 private static final double LOAD_FACTOR = 0.75; //默认最大负载因子 private static final int DEFAULT_SIZE = 8; //默认桶的大小 //初始化哈希桶 public HashBucket() { array = new Node[DEFAULT_SIZE]; } //放元素 public int put(int key, int value) { //1.遍历index数组下的链表，如果有相同的key则更新val int index = key % array.length; Node cur = array[index]; while(cur != null) { if(cur.key == key) { cur.value = value; return 1; } cur = cur.next; } //2.头插法擦插入节点 Node node = new Node(key,value); node.next = array[index]; array[index] = node; //3.重新计算当前的负载因子 是不是超过了 我们规定的负载因子 if(loadFactor() >= LOAD_FACTOR) { //扩容 resize(); } return -1; } //扩容 private void resize() { // write code here Node[] newArray = new Node[array.length * 2]; for (int i = 0; i < array.length; i++) { Node cur = array[i]; while(cur != null) { int newindex = cur.key % newArray.length; //把当前节点 放到新的数组的 newindex 位置 头插法 Node curN = cur.next; cur.next = newArray[newindex]; newArray[newindex] = cur; cur = curN; } } array = newArray; } //计算负载因子 private double loadFactor() { return size * 1.0 / array.length; } //取对应key的value值 public int get(int key) { // write code here int index = key % array.length; Node cur = array[index]; while (cur != null) { if(cur.key == key) { return cur.value; } cur = cur.next; } return -1; } 负载因子：

哈希表中已存储的元素数量（n）与哈希表的容量（m）的比值，通常用公式表示为： 负载因子 = 已存储元素数量哈希表容量 / 哈希表容量。 例如，一个哈希表的容量是 100，当前已经存储了 50 个元素，那么此时该哈希表的负载因子就是 50 / 100 = 0.5

        负载因子主要用于衡量哈希表的空间使用程度和性能，它直接影响哈希表的插入、查找和删除操作的效率：

空间利用率：负载因子越大，说明哈希表中存储的元素越满，空间利用率越高；反之，负载因子越小，空间利用率越低，意味着有较多的空闲存储桶。

冲突概率：冲突是指不同的键通过哈希函数计算得到了相同的存储桶索引。负载因子越大，发生冲突的概率就越高。因为随着元素数量的增加，有限的存储桶被占用的比例也在增大，新元素更容易被映射到已经有元素的桶中。

动态扩容：

为了保证哈希表在不同的元素数量下都能保持较好的性能，当负载因子超过某个阈值（通常是默认的负载因子）时，哈希表会进行动态扩容操作。具体步骤如下：

创建更大的哈希表：通常新的哈希表容量是原容量的 2 倍。重新哈希：将原哈希表中的所有元素重新计算哈希值，并插入到新的哈希表中。更新引用：将原哈希表的引用指向新的哈希表。

总结：

1.java 中使用的是哈希桶方式解决冲突的。

2.java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）。

3. java 中计算哈希值（相当于计算出的数据应该在数组放的下标位置）实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的  equals 方法。

        所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须重写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode ⼀定是⼀致的：

比如：

import java.util.HashMap; import java.util.Map; class Person { private int id; public Person(int id) { this.id = id; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Person person = (Person) o; return id == person.id; } @Override public int hashCode() { return id; } } public class HashMapDuplicateKeyExample { public static void main(String[] args) { Map<Person, String> map = new HashMap<>(); Person p1 = new Person(1); Person p2 = new Person(1); map.put(p1, "Alice"); map.put(p2, "Bob"); System.out.println(map.size()); // 输出: 1 } }

代码过程：

HashMap 先计算 p1 的哈希码，因为 p1 的 id 是 1，所以哈希码就是 1

根据这个哈希码找到对应的哈希桶，把键值对 (p1, "Alice") 存进去。

HashMap 计算 p2 的哈希码，由于 p2 的 id 也是 1，所以哈希码同样是 1，和 p1 的哈希码一样，会对应到同一个哈希桶。

接着，HashMap 会用 equals() 方法比较 p1 和 p2，因为 p1 和 p2 的 id 相等，equals() 方法返回 true，这表明 p1 和 p2 是相同的键。

此时，HashMap 不会再新增一个键值对，而是用新的值 "Bob" 覆盖掉原来键 p1（和 p2 视为相同键）对应的值 "Alice"。

由于 p1 和 p2 被 HashMap 判定为相同的键，所以 HashMap 里实际上只有一个键值对，调用 map.size() 就会输出 1。

此段代码我们知道：

hashCode 方法用于确定键对象在哈希表中的存储位置。

如果两个键的 hashCode 相同，并且 equals 方法返回 true，则认为这两个键是相同的，后插入的键值对会覆盖之前的。

        

HashMap和HashSet的总结： 特性HashMapHashSet存储结构键值对（Key-Value）单一对象（Key）重复元素键唯一，值（value）可重复元素唯一null支持1个null键，多个null值1个null元素底层原理哈希表（数组+链表 / 红黑树）HashMap核心方法put(), get(), remove()add(), remove(), contains()应用场景键值映射、缓存 去重、集合操作