作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。
前言
今天我们需要认识目前非常高效的一种查找算法----散列查找，下面我们就来系统的学习一下如何正确使用散列查找，如何在开发中应用。
一、什么是散列查找
**散列查找（也称为哈希查找）**是基于散列函数（或哈希函数）的查找技术，它是一种非常高效的查找方法。散列函数将要查找的键值映射到一个位置上，这样可以直接访问到存储在那个位置上的值，进行查找操作。
在散列查找中，数据元素的存储位置和它的关键字之间存在一种确定的对应关系，因此，存取时间可以近似认为是常数时间，即 O(1)。这种查找方法在实际应用中非常普遍，如数据库索引、编程语言中的哈希表等。
散列函数
散列函数能够将一个大范围的键值映射到一个较小范围的整数值。这个整数值通常用作数组索引。
散列冲突
由于不同的键值可能映射到相同的索引上，这种情况称为散列冲突（哈希冲突）。解决散列冲突的方法有多种，最常用的是链地址法和开放寻址法。
- 链地址法（Separate Chaining）: 每个数组元素构成一个链表，发生冲突时，冲突的元素将被加入到相同索引位置的链表中。
- 开放寻址法（Open Addressing）: 发生冲突时，通过探测序列找到表中的一个空闲位置。
散列查找步骤
- 计算键值: 使用散列函数计算出键值所对应的散列地址。
- 检查散列地址: 访问散列地址对应的位置。
- 处理冲突: 如果发生冲突，则使用预定的冲突解决方法找到该键值。
- 返回结果: 返回找到的值，如果没有找到则说明该键值不存在。
散列查找的效率极高，但其性能严重依赖于散列函数的设计与冲突解决策略的合理性。一个好的散列函数应尽量减少冲突，使得散列尽可能均匀。
二、使用链地址法和开放地址法解决冲突
数组为 [15, 11, 27, 8, 12]，并且我们需要将这些数字存入哈希表中，然后进行查找操作。我们定义我们的哈希函数为 hash(x) = x % 5，这样它会将数值映射到一个大小为5的哈希表中。
使用链地址法（Separate Chaining）
- 构建哈希表
- 初始化一个大小为5的哈希表，每个槽位初始化为空链表。
- 插入
- 对于每个元素
x使用hash(x)计算散列值。 - 将
x添加到对应散列值的链表中（即散列值作为索引的槽位）。
- 解决冲突
- 如果插入的位置已经有元素（即发生冲突），将新元素添加到链表的头部或尾部，这里我们选择头部。
- 查找
- 为了找到特定的数字，先计算它的哈希值，然后在对应的链表中顺序查找。
让我们通过插入来详细看看如何操作：
15的哈希值为15 % 5 = 0，插入索引0的链表中。11的哈希值为11 % 5 = 1，插入索引1的链表中。27的哈希值为27 % 5 = 2，插入索引2的链表中。8的哈希值为8 % 5 = 3，插入索引3的链表中。12的哈希值为12 % 5 = 2，但索引2的链表中已经有元素27，现在将12添加到该链表的头部。
现在我们的哈希表如下所示（[] 表示链表）：
0: [15] 1: [11] 2: [12, 27] （发生了冲突，12 被添加到链表的头部） 3: [8] 4: []
要查找元素 27：
- 计算哈希值为
27 % 5 = 2； - 顺序检查索引为
2的链表，发现27。
使用开放寻址法（Open Addressing）- 线性探测
- 构建哈希表
- 初始化一个大小为5的哈希表，每个槽位初始化为空。
- 插入
- 对于每个元素
x使用hash(x)计算散列值。 - 如果散列值对应的槽位已被占用，线性探测下一个槽位，直到找到空槽位。
- 解决冲突
- 如果当前位置已占用，继续检查下一个位置
index = (index + 1) % table_size。
- 查找
- 为了找到特定数字，计算它的哈希值。
- 如果槽位不是目标值且不为空，继续进行线性探测。
让我们通过插入来详细看看如何操作：
15的哈希值为15 % 5 = 0，插入索引0的槽位。11的哈希值为11 % 5 = 1，插入索引1的槽位。27的哈希值为27 % 5 = 2，插入索引2的槽位。8的哈希值为8 % 5 = 3，插入索引3的槽位。12的哈希值为12 % 5 = 2，但索引2的槽位已被占用，因此我们进行线性探测，2+1=3也被占用，接着尝试3+1=4，索引4的槽位是空的，于是将12插入索引4。
现在我们的哈希表如下所示：
0: 15 1: 11 2: 27 3: 8 4: 12 （发生了冲突，后通过线性探测找到空位插入）
要查找元素 27：
- 计算哈希值为
27 % 5 = 2； - 直接在索引
2的槽位找到27。
以上两种冲突解决方法都允许我们将一个集合的元素插入到哈希表中，并且能够在发生冲突时，通过各自的方法来解决这些冲突，最后成功地找到目标元素。
三、Java代码示例
分别用链地址法和开放寻址法的一个例子来说明如何从一组数组中使用散列查找和解决散列冲突。
链地址法（Separate Chaining）
假设我们有一个键值对数组，需要构建一个散列表（哈希表）来存储这些数据，以便我们可以快速检索到每个键值对。
class HashNode { int key; int value; HashNode next; public HashNode(int key, int value) { this.key = key; this.value = value; this.next = null; } } class HashMap { private HashNode[] buckets; // 哈希表数组 private int capacity; // 哈希表容量 public HashMap(int capacity) { this.capacity = capacity; this.buckets = new HashNode[capacity]; } // 哈希函数（示例为求模运算） private int hash(int key) { return key % capacity; } // 插入键值对 public void put(int key, int value) { int index = hash(key); HashNode head = buckets[index]; // 检查键是否存在，如果存在就更新 while (head != null) { if (head.key == key) { head.value = value; return; } head = head.next; } // 插入新节点 head = buckets[index]; HashNode newNode = new HashNode(key, value); newNode.next = head; buckets[index] = newNode; } // 查找键对应的值 public Integer get(int key) { int index = hash(key); HashNode head = buckets[index]; while (head != null) { if (head.key == key) { return head.value; } head = head.next; } // 如果键不存在，返回 null return null; } } // 存放在散列表中的数据 int[][] data = {{1, 100}, {2, 200}, {3, 300}, {4, 400}}; HashMap hashMap = new HashMap(10); for (int[] pair : data) { hashMap.put(pair[0], pair[1]); } // 查找键为 2 的值 Integer value = hashMap.get(2); // 返回 200
开放寻址法（Open Addressing）
以线性探测为例，如果计算得到的散列位置已被占用，将按顺序检查下一个位置，直到找到空位。
class LinearProbingHashMap { private Integer[] keys; private Integer[] values; private int capacity; public LinearProbingHashMap(int capacity) { this.capacity = capacity; keys = new Integer[capacity]; values = new Integer[capacity]; } private int hash(int key) { return key % capacity; } public void put(int key, int value) { int index = hash(key); while (keys[index] != null && keys[index] != key) { index = (index + 1) % capacity; // 线性探测 } keys[index] = key; values[index] = value; } public Integer get(int key) { int index = hash(key); while (keys[index] != null) { if (keys[index] == key) { return values[index]; } index = (index + 1) % capacity; // 线性探测 } return null; } } // 存放在散列表中的数据 int[][] data = {{1, 100}, {2, 200}, {3, 300}, {4, 400}}; LinearProbingHashMap hashMap = new LinearProbingHashMap(10); for (int[] pair : data) { hashMap.put(pair[0], pair[1]); } // 查找键为 2 的值 Integer value = hashMap.get(2); // 返回 200
在链地址法的实现中，每个数组槽位是一个链表。如果发生冲突（两个键的散列值相同），新的元素将被添加到链表的头部或尾部。而在开放寻址法（以线性探测为例）的实现中，如果散列到的位置已经被占用，我们将顺序地探测下一个槽位直到找到空位。
以上两个示例都在Java语言中实现了散列查找和解决散列冲突的具体方法。实际应用中，应当根据数据特点和场景需求选择最合适的冲突解决策略。
四、思考：哈希查找的两种冲突解决方法中，哪种方法更适合处理大量数据的查找？
在处理大量数据的查找时，选择散列冲突解决方法要考虑几个因素，包括数据的性质、散列函数的选择、负载因子（即数据量与哈希表容量的比例）、以及数据的分布情况等。下面对链地址法和开放寻址法进行比较：
链地址法（Separate Chaining）
优点：
- 链地址法可以更好地处理哈希冲突，因为每个槽位可以存储多个元素。
- 在负载因子较高时（即哈希表比较满时）仍然表现良好。
- 链表可以无限增长，这使得它适合存储大量数据。
- 对于数据分布不均匀的场景，链地址法的性能损失相对较小。
缺点：
- 链表节点的存储需要额外的空间来保存 next 指针。
- 如果链表很长，可能会影响查找性能，因为需要遍历链表。
- 缓存性能可能较差，因为链表节点在内存中可能不连续。
开放寻址法（Open Addressing）
优点：
- 开放寻址法对于数据量较小或者负载因子较低（表很空）的情况下表现良好。
- 不需要额外空间来存储指针，整个哈希表存储为一个连续的数组。
- 因为数据存储在数组中，可能有更好的缓存性能（空间局部性）。
缺点：
- 当哈希表较满时，开放寻址法的性能会急剧下降，因为线性探测可能会导致聚集效应。
- 删除操作较为复杂，需要特别的方法来处理已删除的元素位置。
- 随着数据量的增加，为了保持良好性能，可能需要频繁地调整哈希表的大小。
总的来说，如果处理的是大量数据且哈希表的负载较高，链地址法往往更受青睐，因为它能更稳定地处理冲突，拥有更可预测的性能。尽管链地址法可能在内存使用上有一些开销，但它的扩展性和对不均匀数据的容忍度使得它成为处理大量数据时的一个较好选择。
最终的选择应该基于具体应用的需求、实际数据和性能测试的结果。在某些情况下，也可能使用到这两种方法的混合，或者使用其他更高级的冲突解决方法。
五、Java实战项目
让我们构建一个简单的Java项目：一个基于散列表（HashTable）实现的学生信息管理系统。这个系统可以让我们添加学生信息、按学号进行查找以及打印出所有学生信息。在这个项目中，我们将使用Java的HashMap类来实现散列查找的功能。HashMap是一种能够提供快速插入和查找的数据结构，它通过散列函数来决定元素的存储位置，以达到高效的数据管理。
我们将首先定义一个Student类，然后将创建一个StudentManagementSystem类，它会使用HashMap来管理学生信息。
这是Student类的代码：
public class Student { private String id; private String name; private int age; // 构造函数，用于创建学生对象 public Student(String id, String name, int age) { this.id = id; this.name = name; this.age = age; } // 获取学生ID public String getId() { return id; } // 获取学生姓名 public String getName() { return name; } // 获取学生年龄 public int getAge() { return age; } // 重写toString方法，方便打印学生信息 @Override public String toString() { return "Student{" + "id='" + id + '\'' + ", name='" + name + '\'' + ", age=" + age + '}'; } }
接下来是StudentManagementSystem类的实现：
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class StudentManagementSystem { private Map<String, Student> students; // 构造函数，初始化学生管理系统 public StudentManagementSystem() { students = new HashMap<>(); } // 添加学生信息 public void addStudent(Student student) { students.put(student.getId(), student); System.out.println("学生信息添加成功！"); } // 根据学号查找学生信息 public void findStudentById(String id) { Student student = students.get(id); if (student != null) { System.out.println("找到学生信息：" + student); } else { System.out.println("没有找到学生信息。"); } } // 打印所有学生信息 public void printAllStudents() { for (Student student : students.values()) { System.out.println(student); } } // 主程序入口 public static void main(String[] args) { StudentManagementSystem system = new StudentManagementSystem(); Scanner scanner = new Scanner(System.in); System.out.println("欢迎使用学生管理系统！"); String option; do { System.out.println("\n选项：1. 添加学生 2. 查找学生 3. 显示所有学生信息 4.退出"); System.out.print("请输入你的选择："); option = scanner.next(); switch (option) { case "1": // 添加学生信息 System.out.print("请输入学号："); String id = scanner.next(); System.out.print("请输入姓名："); String name = scanner.next(); System.out.print("请输入年龄："); int age = scanner.nextInt(); Student student = new Student(id, name, age); system.addStudent(student); break; case "2": // 查找学生信息 System.out.print("请输入学号以查找学生："); String studentId = scanner.next(); system.findStudentById(studentId); break; case "3": // 显示所有学生信息 system.printAllStudents(); break; case "4": System.out.println("退出系统。"); break; default: System.out.println("无效的选项，请重新输入。"); break; } } while (!option.equals("4")); } }
在这个项目中：
HashMap类是实现散列表的核心，它利用了散列的概念来快速存取键值对。addStudent方法添加学生的信息到系统中，以学号作为Key，Student对象作为Value存储到HashMap。findStudentById方法通过学号快速检索学生信息。printAllStudents方法列出了系统中所有的学生信息。
使用HashMap作为散列表实现的数据结构在这个项目中是合理的，因为它提供了平均情况下常数时间复杂度的查找性能，并且操作简单易于理解。在这个程序中，学号作为唯一的键（Key），这样就能保证每个学生信息的唯一性与快速访问。
总结
希望大家可以好好掌握散列查找，以后经常会遇到。
感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!
