哈希线性探测实现问题：探测后学生ID无法正确显示求助

问题描述 #

我想实现线性探测哈希表，输出探测前后的结果，但执行线性探测后，学生的原ID没有正确显示。以下是我的Java代码，以及期望和实际的输出差异：

原代码 #

import java.util.*;

class practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Hashtable<Integer, String> table = new Hashtable<>(10);

        System.out.println("How many students u want to enter: ");
        int numOfSt = sc.nextInt();

        for (int i = 1; i <= numOfSt; i++) {
            System.out.println("ID: ");
            int ID = sc.nextInt();

            System.out.println("Name: ");
            String name = sc.next();

            table.put(ID, name);
        }
        for (Integer key : table.keySet()) {
            System.out.println(key.hashCode() % 10 + "\t\t" + key + "\t\t" + table.get(key));
        }

        Hashtable<Integer, String> LinearProb = new Hashtable<>(10);

        for (Integer key : table.keySet()) {
            int index = key.hashCode() % 10;

            while (LinearProb.containsKey(index)) {
                index = (index + 1) % 10;
            }

            LinearProb.put(index, key + table.get(key));

        }

        for (Integer key : LinearProb.keySet()) {
            System.out.println(key + "\t\t" + key.hashCode() % 10 + "\t\t" + LinearProb.get(key));
        }
    }
}

期望输出 #

实际输出 #

问题原因 #

1. 存储逻辑错误：用Hashtable<Integer, String>存储线性探测结果时，把探测到的索引作为键，值直接拼接ID和姓名，导致后续无法区分原ID和姓名；输出时错误地将索引键当成学号打印。
2. 数据结构不合理：没有单独存储原ID和姓名的结构，仅靠字符串拼接无法保留完整的原始数据。

修复方案 #

1. 自定义学生类：创建Student类封装学号和姓名，确保原始数据完整保留。
2. 调整哈希表类型：将线性探测后的哈希表改为Hashtable<Integer, Student>，键为探测索引，值为对应学生对象。
3. 修正输出逻辑：遍历哈希表时，直接从学生对象中提取原学号和姓名进行打印。

修复后代码 #

import java.util.*;

class Student {
    private int id;
    private String name;

    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public String getName() {
        return name;
    }
}

class Practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Hashtable<Integer, String> originalTable = new Hashtable<>(10);

        System.out.println("请输入学生数量: ");
        int numOfSt = sc.nextInt();

        for (int i = 1; i <= numOfSt; i++) {
            System.out.println("请输入学号: ");
            int id = sc.nextInt();

            System.out.println("请输入姓名: ");
            String name = sc.next();

            originalTable.put(id, name);
        }

        // 输出探测前结果
        System.out.println("\n=== 探测前的哈希表 ===");
        System.out.printf("%-8s %-8s %-8s\n", "哈希索引", "学号", "姓名");
        for (Integer key : originalTable.keySet()) {
            int hashIndex = key.hashCode() % 10;
            System.out.printf("%-8d %-8d %-8s\n", hashIndex, key, originalTable.get(key));
        }

        // 线性探测实现
        Hashtable<Integer, Student> linearProbTable = new Hashtable<>(10);

        for (Integer key : originalTable.keySet()) {
            int index = key.hashCode() % 10;

            // 寻找空索引位置
            while (linearProbTable.containsKey(index)) {
                index = (index + 1) % 10;
            }

            linearProbTable.put(index, new Student(key, originalTable.get(key)));
        }

        // 输出探测后结果
        System.out.println("\n=== 探测后的哈希表 ===");
        System.out.printf("%-8s %-8s %-8s\n", "索引", "学号", "姓名");
        for (Integer index : linearProbTable.keySet()) {
            Student student = linearProbTable.get(index);
            System.out.printf("%-8d %-8d %-8s\n", index, student.getId(), student.getName());
        }

        sc.close();
    }
}

修复后输出示例 #

输入2个学生（学号212/Ana、学号712/Sofia）后，输出如下：

请输入学生数量: 
2
请输入学号: 
212
请输入姓名: 
Ana
请输入学号: 
712
请输入姓名: 
Sofia

=== 探测前的哈希表 ===
哈希索引   学号      姓名    
2        212      Ana     
2        712      Sofia   

=== 探测后的哈希表 ===
索引      学号      姓名    
2        212      Ana     
3        712      Sofia   

内容的提问来源于stack exchange，提问作者Marshmallow -