Java进阶—哈希冲突的解决

news/2025/3/17 20:01:59/

1. 什么是哈希冲突

哈希函数：哈希函数是一种将输入数据(键)映射到固定大小范围的输出值(哈希值)的函数。哈希函数通常用于存储 数据存储和检索领域，例如哈希表中。
哈希表：哈希表(Hash Table)，也成为哈希映射(Hash Map)或字典（Dictionary），是一种常见的数据结构，用于实现关联数组，它可以将键映（Key）射到值(Value)
哈希冲突：由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，当两个或更多键被哈希函数映射到相同的索引位置时，就会发生哈希冲突。

在Java中，哈希函数通常是通过hashCode()方法实现的，hashCode()方法是Object类中定义的一个方法，因此所有Java类都可以使用它。hashCode()方法的默认实现是返回对象的内存地址的哈希码，但通常情况下，我们需要重写这个方法来提供更合适的哈希函数。

在重写hashCode()方法时，通常需要遵循以下法则：

  1. 相等的对象必须具有相等哈希码。也就是说，如果两个对象通过‘equals()’方法相等，那么它们的哈希码应该相等。

如果 a.equals(b)==true,它们的hashCode一定相同吗？
哈希表中，首先会比较对象的‘hashCode’值确定它们所在的桶(bucket),然后再根据‘equals()’方法来精确匹配对象。
所以在Java中a.equals(b)==true，它们的hashCode一定是相同的。除非重写了equals方法或hashCode方法()
因此，为了保持一致性，在重写equals()方法时通常也需要重写hashCode()方法，以确保相等的对象具有相同的哈希码。

  1. 尽量减少哈希冲突，即不同的对象尽量产生不同的哈希码，以提高哈希表等数据结构的性能。
    例如，对于一个简单的Person类，我们可以重写hashCode()方法如下：

    public class Person {private String name;private int age;// 构造函数、getter和setter等方法省略@Overridepublic int hashCode() {int result = 17;result = 31 * result + name.hashCode();result = 31 * result + age;return result;}
}

    在这个例子中，我们使用了一种常见的计算哈希码的方式，即将一个基本数值（这里是17）与对象的属性哈希码相结合，然后用一个质数（31）作为乘数不断累加。这种方式可以比较有效地减少哈希冲突，但并不是万能的，具体的哈希函数设计取决于对象的属性特点和应用场景。

2. 怎么解决哈希冲突

为了解决哈希冲突，常见的方法包括开放寻址法和链表法（拉链法）。

2.1 开放寻址法

在发生哈希冲突时，通过一定的方法(如线性探测、二次探测、双重哈希等)寻找下一个空的哈希表位置，键冲突的键值对放置在新的位置上。这样可以避免使用额外的数据结构存储冲突的键值对，节省空间。但是，如果哈希表填充率过高，开放寻址法的性能可能会收到影响。

  1. 线性探测(Linear Probing)：在发生哈希冲突时，线性探测会顺序地检查哈希表中的下一个位置，直到找到一个空闲的位置为止。具体地说，如果哈希表中位置‘i’发生了冲突，那么线性探索位置‘i+1’,‘i+2’，直到找到一个空闲位置或遍历完整个哈希表。正常不会发生找不到位置，通常情况下，但哈希表中元素达到一定阈值，会自动触发扩容操作。

    当哈希表使用线性探测解决哈希冲突时，插入和查找元素的过程如下：

    1. 插入元素时，如果计算出的哈希位置已经被占用，则向后顺序查找直到找到一个空闲位置。

    2. 查找元素时，计算出元素的哈希位置后，如果该位置为空或者元素的键与要查找的键不相等，则向后顺序查找直到要查找的元素或者遍历完整个哈希表
      以下是使用线性探测法解决哈希冲突的简单示例代码：

      class LinearProbingHashTable {private static final int DEFAULT_CAPACITY = 10;private Entry[] table;private int size;public LinearProbingHashTable() {table = new Entry[DEFAULT_CAPACITY];size = 0;}public void put(int key, String value) {int index = hash(key);while (table[index] != null && table[index].getKey() != key) {index = (index + 1) % table.length; // 线性探测下一个位置}if (table[index] == null) {table[index] = new Entry(key, value);size++;} else {table[index].setValue(value);}}public String get(int key) {int index = hash(key);while (table[index] != null && table[index].getKey() != key) {index = (index + 1) % table.length; // 线性探测下一个位置}return table[index] != null ? table[index].getValue() : null;}private int hash(int key) {return key % table.length;}private static class Entry {private int key;private String value;public Entry(int key, String value) {this.key = key;this.value = value;}public int getKey() {return key;}public String getValue() {return value;}public void setValue(String value) {this.value = value;}}
}public class Main {public static void main(String[] args) {LinearProbingHashTable hashTable = new LinearProbingHashTable();hashTable.put(1, "A");hashTable.put(11, "B");hashTable.put(21, "C");System.out.println(hashTable.get(1));  // 输出 "A"System.out.println(hashTable.get(11)); // 输出 "B"System.out.println(hashTable.get(21)); // 输出 "C"}
}

  2. 二次探测(Quadratic Probing)：二次探测是线性探测地改进版本，它使用一个二次方程来计算下一个探测位置。具体来说，如果哈希表中位置‘i’发生了冲突，那么二次探测法会一次检查位置 (i + 1^2)、(i + 2^2)、(i + 3^2)，直到找到一个空闲位置或者遍历完整个哈希表。

    以下是使用二次探测解决哈希冲突的示例代码：

    class QuadraticProbingHashTable {private static final int DEFAULT_CAPACITY = 10;private Entry[] table;private int size;public QuadraticProbingHashTable() {table = new Entry[DEFAULT_CAPACITY];size = 0;}public void put(int key, String value) {int index = hash(key);int i = 1;while (table[index] != null && table[index].getKey() != key) {index = (index + i * i) % table.length; // 二次探测下一个位置i++;}if (table[index] == null) {table[index] = new Entry(key, value);size++;} else {table[index].setValue(value);}}public String get(int key) {int index = hash(key);int i = 1;while (table[index] != null && table[index].getKey() != key) {index = (index + i * i) % table.length; // 二次探测下一个位置i++;}return table[index] != null ? table[index].getValue() : null;}private int hash(int key) {return key % table.length;}private static class Entry {private int key;private String value;public Entry(int key, String value) {this.key = key;this.value = value;}public int getKey() {return key;}public String getValue() {return value;}public void setValue(String value) {this.value = value;}}
}public class Main {public static void main(String[] args) {QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable();hashTable.put(1, "A");hashTable.put(11, "B");hashTable.put(21, "C");System.out.println(hashTable.get(1));  // 输出 "A"System.out.println(hashTable.get(11)); // 输出 "B"System.out.println(hashTable.get(21)); // 输出 "C"}
}

  3. 双重哈希(Double Hashing)：双重哈希使用两个哈希函数来计算下一个探测位置。具体地说，如果哈希表中位置‘i’发生了冲突，双重哈希会使用第二个哈希函数计算一个偏移量来计算下一个探测位置。如果这个位置仍然发生冲突，就会使用相同的方法，直到找到一个空间位置或者遍历完整个哈希表。
    以下是使用双重哈希解决哈希冲突的示例代码：

    class DoubleHashingHashTable {private static final int DEFAULT_CAPACITY = 10;private Entry[] table;private int size;public DoubleHashingHashTable() {table = new Entry[DEFAULT_CAPACITY];size = 0;}public void put(int key, String value) {int index = hash1(key);int offset = hash2(key);while (table[index] != null && table[index].getKey() != key) {index = (index + offset) % table.length; // 双重哈希探测下一个位置}if (table[index] == null) {table[index] = new Entry(key, value);size++;} else {table[index].setValue(value);}}public String get(int key) {int index = hash1(key);int offset = hash2(key);while (table[index] != null && table[index].getKey() != key) {index = (index + offset) % table.length; // 双重哈希探测下一个位置}return table[index] != null ? table[index].getValue() : null;}private int hash1(int key) {return key % table.length;}private int hash2(int key) {return 7 - (key % 7); // 可以选择不同的哈希函数}private static class Entry {private int key;private String value;public Entry(int key, String value) {this.key = key;this.value = value;}public int getKey() {return key;}public String getValue() {return value;}public void setValue(String value) {this.value = value;}}
}public class Main {public static void main(String[] args) {DoubleHashingHashTable hashTable = new DoubleHashingHashTable();hashTable.put(1, "A");hashTable.put(11, "B");hashTable.put(21, "C");System.out.println(hashTable.get(1));  // 输出 "A"System.out.println(hashTable.get(11)); // 输出 "B"System.out.println(hashTable.get(21)); // 输出 "C"}
}

2. 2 链表法(拉链法)

链表法(Separte Chaining)是一种常见到的解决哈希冲突的方法，它使用链表来存储哈希表中发生冲突的键值对。具体来说，每个哈希表的槽位上都对应一个链表，当发生哈希冲突时，新的键值对会被插入到对应槽位上的链表中，而不是直接覆盖原有的键值对。
链表法适用于经常进行插入和删除的情况。
如下一组数字,(32、40、36、53、16、46、71、27、42、24、49、64)哈希表长度为13，哈希函数为H(key)=key%13,则链表法结果如下：

0       
1  -> 40 -> 27 -> 53 
2
3  -> 16 -> 42
4
5
6  -> 32 -> 71
7  -> 46
8
9
10 -> 36 -> 49
11 -> 24
12 -> 64

在java中，链接地址法也是HashMap解决哈希冲突的方法之一，jdk1.7完全采用单链表来存储同义词，jdk1.8则采用了一种混合模式，对于链表长度大于8的，会转换为红黑树存储。
以下是使用链表法解决哈希冲突的示例代码：

import java.util.*;class SeparateChainingHashTable {private static final int DEFAULT_CAPACITY = 10;private List<Entry>[] table;private int size;public SeparateChainingHashTable() {table = new LinkedList[DEFAULT_CAPACITY];size = 0;}public void put(int key, String value) {int index = hash(key);if (table[index] == null) {table[index] = new LinkedList<>();}for (Entry entry : table[index]) {if (entry.getKey() == key) {entry.setValue(value);return;}}table[index].add(new Entry(key, value));size++;}public String get(int key) {int index = hash(key);if (table[index] != null) {for (Entry entry : table[index]) {if (entry.getKey() == key) {return entry.getValue();}}}return null;}private int hash(int key) {return key % table.length;}private static class Entry {private int key;private String value;public Entry(int key, String value) {this.key = key;this.value = value;}public int getKey() {return key;}public String getValue() {return value;}public void setValue(String value) {this.value = value;}}
}public class Main {public static void main(String[] args) {SeparateChainingHashTable hashTable = new SeparateChainingHashTable();hashTable.put(1, "A");hashTable.put(11, "B");hashTable.put(21, "C");System.out.println(hashTable.get(1));  // 输出 "A"System.out.println(hashTable.get(11)); // 输出 "B"System.out.println(hashTable.get(21)); // 输出 "C"}
}

3 建议和注意事项

  1. 选择合适的哈希函数： 哈希函数的选择对于减少哈希冲突非常重要。一个好的哈希函数应该能够将键均匀地分布到哈希表中的槽位上，减少碰撞的概率。
  2. 考虑装载因子： 装载因子是指哈希表中已存储键值对的数量与哈希表总容量的比值。当装载因子过高时，哈希冲突的概率会增加，影响性能。因此，定期调整哈希表的大小，以保持适当的装载因子是很重要的。
  3. 选择合适的解决冲突方法： 根据应用场景和性能需求，选择合适的解决哈希冲突的方法。例如，开放寻址法适用于空间紧张的情况，而链表法适用于处理大量哈希冲突的情况和频繁插入删除的操作。
  4. 考虑并发情况： 在并发环境下，需要考虑多线程同时访问哈希表可能引发的问题。可以使用线程安全的哈希表实现或者在访问哈希表时进行适当的同步操作来处理并发访问问题。

http://www.ppmy.cn/news/1394492.html

相关文章

java每日一题——买啤酒(递归经典问题)

java每日一题——买啤酒(递归经典问题)

前言&#xff1a; 非常喜欢的一道题&#xff0c;经典中的经典。打好基础&#xff0c;daydayup!!!啤酒问题&#xff1a;一瓶啤酒2元&#xff0c;4个盖子可以换一瓶&#xff0c;2个空瓶可以换一瓶&#xff0c;请问10元可以喝几瓶 题目如下&#xff1a; 啤酒问题&#xff1a;一瓶…
阅读更多...
鸿蒙一次开发，多端部署（十二）资源使用

鸿蒙一次开发，多端部署（十二）资源使用

在页面开发过程中&#xff0c;经常需要用到颜色、字体、间距、图片等资源&#xff0c;在不同的设备或配置中&#xff0c;这些资源的值可能不同。有两种方式处理&#xff1a; 应用资源&#xff1a;借助资源文件能力&#xff0c;开发者在应用中自定义资源&#xff0c;自行管理这些…
阅读更多...
SVN的branch分支合并完要不要删除

SVN的branch分支合并完要不要删除

在 SVN 中&#xff0c;当一个分支&#xff08;branch&#xff09;的工作已经完成并成功合并回主干&#xff08;trunk&#xff09;后&#xff0c;通常不需要立即删除该分支。保留分支可以有一些好处&#xff0c;例如&#xff1a; 历史记录和追溯&#xff1a;保留分支可以帮助团…
阅读更多...
智慧物联-能源分析平台

智慧物联-能源分析平台

物联能源分析平台是为了满足企业对能源管理和节能减排的需求而开发的一套在线平台。随着能源问题日益凸显&#xff0c;企业对能源的使用和管理面临着越来越大的挑战。因此&#xff0c;开发一个能够帮助企业实时监测、分析和优化能源消耗的平台变得尤为重要。 随着工业化和城市…
阅读更多...
话题——AI大模型学习

话题——AI大模型学习

AI大模型学习 在当前技术环境下&#xff0c;AI大模型学习不仅要求研究者具备深厚的数学基础和编程能力&#xff0c;还需要对特定领域的业务场景有深入的了解。通过不断优化模型结构和算法&#xff0c;AI大模型学习能够不断提升模型的准确性和效率&#xff0c;为人类生活和工作…
阅读更多...
软考 系统架构设计师系列知识点之系统性能（1）

软考 系统架构设计师系列知识点之系统性能（1）

所属章节&#xff1a; 第2章. 计算机系统基础知识 第9节. 系统性能 系统性能是一个系统提供给用户的所有性能指标的集合。它既包括硬件性能&#xff08;如处理器主频、存储器容量、通信带宽等&#xff09;和软件性能&#xff08;如上下文切换、延迟、执行时间等&#xff09;&a…
阅读更多...
MySQL实战：监控

MySQL实战：监控

监控指标 性能类指标 名称说明QPS数据库每秒处理的请求数量TPS数据库每秒处理的事务数量并发数数据库实例当前并行处理的会话数量连接数连接到数据库会话的数量缓存命中率Innodb的缓存命中率 功能类指标 名称说明可用性数据库是否正常对外提供服务阻塞当前是否有阻塞的会话…
阅读更多...
MD5是加密算法？别再傻傻分不清了

MD5是加密算法？别再傻傻分不清了

引言 MD5&#xff0c;全称为Message-Digest Algorithm 5&#xff0c;是一种广泛应用于信息技术领域的消息摘要算法。由麻省理工学院的Ronald L. Rivest在1991年设计并提出&#xff0c;作为MD4算法的改进版本&#xff0c;MD5迅速成为国际上广为接受和使用的散列函数标准之一。尽…
阅读更多...
最新文章

Copyright @ 2022~2023