当前位置：首页 > news >正文

模拟解决哈希表冲突

news 来源：原创 2025/9/20 22:07:06

解决哈希表冲突原理：

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

负载因子：

动态扩容：

总结：

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则更新valint 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 hereNode[] 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 hereint 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;}@Overridepublic 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;}@Overridepublic 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的总结：

特性

HashMap

HashSet

存储结构

键值对（Key-Value）

单一对象（Key）

重复元素

键唯一，值（value）可重复

元素唯一

null支持

1个null键，多个null值

1个null元素

底层原理

哈希表（数组+链表 / 红黑树）

HashMap

核心方法

put(), get(), remove()

add(), remove(), contains()

应用场景

键值映射、缓存

去重、集合操作

解决哈希表冲突原理：