数据结构程序设计——哈希表的应用(2)-＞哈希表解决冲突的方法

目录

实验须知

代码实现

实验报告

一：问题分析

二、数据结构

1.逻辑结构

2.物理结构

三、算法

（一）主要算法描述

1.用除留余数法构造哈希函数?

2.线性探测再散列法?

（一）主要算法实现代码

四、上机调试

---

实验须知

实验目的： 深入理解哈希表解决冲突的办法。

实验内容： 针对自己所在班级中学生姓名设计一个哈希表，使得平均查找长度不超过 R ，并完成相应的建表和查表程序。

实验要求：

（ 1 ）创建名为 kcsj19.cpp 的文件，在其中编写哈希查找学生姓名的程序；

（ 2 ）假设学生姓名为中国人姓名的汉语拼音形式。待填入哈希表的学生姓名共有 30 个，取平均查找 长度的上限为 2 。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突；

（ 3 ）测试数据：取读者周围较熟悉的 30 个学生姓名。

代码实现

import java.util.Arrays;
import java.util.Scanner;

public class Kcsj19 {
    private static final int TABLE_SIZE = 61;  // 哈希表的大小，选择质数可以减少冲突
    private String[] table;

    public Kcsj19() {
        table = new String[TABLE_SIZE];
        Arrays.fill(table, "");
    }

    // 哈希函数：除留余数法
    private int hashFunction(String key) {
        int hashValue = 0;
        for (char ch : key.toCharArray()) {
            hashValue = (hashValue * 31 + ch) % TABLE_SIZE;
        }
        return hashValue;
    }

    // 线性探测再散列法
    private int linearProbe(int index, int attempt) {
        return (index + attempt) % TABLE_SIZE;
    }

    // 插入元素
    private void insert(String name) {
        int index = hashFunction(name);
        int attempt = 0;

        while (!table[index].isEmpty()) {
            attempt++;
            index = linearProbe(index, attempt);
        }

        table[index] = name;
    }

    // 查找元素
    private boolean search(String name) {
        int index = hashFunction(name);
        int attempt = 0;

        while (!table[index].isEmpty()) {
            if (table[index].equals(name)) {
                System.out.println("学生姓名 " + name + " 在哈希表中。");
                return true;
            }
            attempt++;
            index = linearProbe(index, attempt);
        }

        System.out.println("学生姓名 " + name + " 不在哈希表中。");
        return false;
    }

    // 打印哈希表
    private void displayTable() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (!table[i].isEmpty()) {
                System.out.println("哈希表[" + i + "]: " + table[i]);
            }
        }
    }

    public static void main(String[] args) {
        Kcsj19 hashTable = new Kcsj19();

        // 待填入哈希表的学生姓名
        String[] students = {"蔡开俊", "陈恒", "陈慧强", "董彪", "冯迪", "冯伟宇", "谷婉如","韩欣言", "何继翔",
                             "李宝才", "李琳琳", "李现珍", "李向阳", "李毅琛", "路亚博","路政睿" ,"孙志坤","王龙杰",
                             "王蕊", "王艺涵", "薛获宇", "元亚捷", "岳婧婧", "詹思航", "张浩",
                             "张恒", "张佳熙", "张锦彩", "张梦娇", "张轩硕"};

        // 插入学生姓名到哈希表
        for (String student : students) {
            hashTable.insert(student);
        }

        // 打印哈希表
        hashTable.displayTable();

        // 测试查找学生姓名

        Scanner scanner = new Scanner(System.in);
        

        // 判断学生姓名是否存在于哈希表中
        while(true) {
        	System.out.print("请输入学生姓名（输入exit退出）：");
            String inputName = scanner.nextLine();
            if (inputName.equalsIgnoreCase("exit")) {
                System.out.println("程序已退出。");
                break;
              }
        	 hashTable.search(inputName);
        }
       
    }
}

实验报告

一：问题分析

描述问题该实验可归结为哈希表的建表和查表功能的实现。用除留余数法构建哈希表，把学生姓名以汉语拼音的形式储存在哈希表中，当发生冲突时，会使用线性探测再散列法在哈希表中的下一个位置继续搜索直到找到空槽。解决该问题的方法和思路：使用除留余数法构造哈希表，然后向表中添加学生姓名，如果在插入和查找的过程中发生冲突用线性探测散列法解决冲突。

二、数据结构

1.逻辑结构

哈希表的应用实习项目的逻辑结构是一个大小为TABLE_SIZE的数组，每个数组元素都可以存储一个学生姓名。哈希函数将学生姓名转化成一个数组索引，然后在该索引位置上插入或查找学生姓名。当插入学生姓名时，如果对应的数组索引位置已经被占用，则使用线性探测再散列法来寻找下一个可用的位置。当查找学生姓名时，根据哈希函数得到学生姓名对应的数组索引，然后根据线性探测再散列法依次检查该索引位置及其后续位置，直到找到匹配的学生姓名或者遇到空位置为止。

2.物理结构

物理结构采用的是顺序存储结构。

三、算法

（一）主要算法描述

1.用除留余数法构造哈希函数?

（1）哈希函数的输入是一个字符串key，它使用了一个for循环遍历?字符串key的每个字符，并结合当前的哈希值hashValue进行计算。具体的计算公式是：hashValue=(hashValue?*?31+ch)%TABLE_SIZE。
（2）其中，ch表示当前字符的ASCII值。乘以31是为了增加哈希函数的散列性能，使得不同的字符组合能够得到不同的哈希值。最后取余数TABLE_SIZE?是将哈希值限定在哈希表的大小范围内，以确保插入和查询的正确性。
（3）然后，根据这个哈希值，确定存储学生姓名的位置（索引）在哈希表中的哪个位置。最终，将学生姓名保存在哈希表的相应位置上。

2.线性探测再散列法?

（1）代码中使用了线性探测再散列法来处理哈希冲突。在插入元素和查找元素的方法中，通过不断尝试下一个位置来解决冲突。如果当前位置已经被占用，就尝试下一个位置，直到找到一个空闲的位置或者遍历完整个哈希表。
（2）linearProbe方法接受两个参数：index表示原始的哈希值对应的索引，attempt表示当前的探测次数。通过将原始索引index和探测次数attempt相加，并对TABLE_SIZE取模，得到一个新的索引值。这个新的索引值即为通过线性探测法计算得到的下一个位置。
（3）在插入元素的方法中，先把通过学生姓名计算出的哈希值赋值给index，此时设置探测次数attempt为0，如果哈希表在index位置不为空那么attempt加一，再用linearProbe方法来计算下一个位置，即(index+attempt)?%?TABLE_SIZE。如果哈希表在index位置为空的话，就把学生姓名添加到哈希表中。
（4）在查找元素的方法中，首先通过调用hashFunction?哈希函数来计算给定学生姓名的哈希值，并将其赋值给index变量。然后，设置初始的探测次数attempt?为0。接下来，使用一个循环来判断哈希表在index位置是否为空。如果不为空，则进入循环体。在循环体中，首先判断哈希表在index位置的值与目标姓名是否相等。如果相等，说明找到了目标姓名，将相关信息打印出来，并返回true表示找到了目标。如果不相等，则增加attempt的值，并使用linearProbe方法计算下一个探测位置。linearProbe方法使用线性探测再散列法的思想，通过(index?+?attempt)%TABLE_SIZE的计算来获取下一个探测位置。当哈希表在index位置为空时，说明未找到目标姓名，将相关信息打印出来，并返回false表示未找到目标。

（一）主要算法实现代码

1.用除留余数法构建哈希表 
private int hashFunction(String key) {
? ? ? ? int hashValue = 0;
? ? ? ? for (char ch : key.toCharArray()) {
? ? ? ? ? ? hashValue = (hashValue * 31 + ch) % TABLE_SIZE;
? ? ? ? }
? ? ? ? return hashValue;
? ? }
2.线性探测再散列法解决冲突  
private int linearProbe(int index, int attempt) {
? ? ? ? return (index + attempt) % TABLE_SIZE;
}
3.向哈希表中插入元素
private void insert(String name) {
? ? ? ? int index = hashFunction(name);
? ? ? ? int attempt = 0;
? ? ? ? while (!table[index].isEmpty()) {
? ? ? ? ? ? attempt++;
? ? ? ? ? ? index = linearProbe(index, attempt);
? ? ? ? }
? ? ? ? table[index] = name;
}
4.在哈希表中查找元素
private boolean search(String name) {
? ? ? ? int index = hashFunction(name);
? ? ? ? int attempt = 0;
? ? ? ? while (!table[index].isEmpty()) {
? ? ? ? ? ? if (table[index].equals(name)) {
? ? ? System.out.println("学生姓名 " + name + " 在哈希表中。");
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
 ? ? ? ? ? attempt++;
? ? ? ? ? ? index = linearProbe(index, attempt);
? ? ? ? }
 ? ? ? System.out.println("学生姓名 " + name + " 不在哈希表中。");
 ? ? ? return false;
? ? }

四、上机调试

问题1：?输入exit并不会退出程序，而是输出“学生姓名exit不在哈希表中”。

图2 无法退出程序

解决办法：出现这种情况的原因是使用“==”来判断两个字符串是否相等，要比较两个字符串的内容是否相等，可以使用equals方法，或者equalsIgnoreCase方法（可以忽略大小写）。

图3 使用equalsIgnoreCase方法比较字符串是否相同

问题2：哈希表的存储与哈希值有关，?如何获取字符串的哈希值，?进行存储。
解决办法：对于输入的字符串key，遍历其中的每个字符ch，将hashValue乘以31后加上ch的ASCII码值，并取模TABLE_SIZE，得到新的哈希值。

问题3：?出现空指针异常。

?图4出现空指针异常

解决办法：出现异常的原因是没有对数组进行初始化。使用Arrays.fill()方法将数组中所有元素赋值为空字符串，避免在插入或查找元素时出现值null，?因为如果数组元素为null，那么在调用字符串方法时，就会抛出空指针异常。

图5对数组进行初始化