仅供参考

利用哈希表的思想设计一个能快速查询的学生通讯录程序。每个学生的信息至少包括：学号（10个数字）、姓名（不超过20字符）、手机号码（11个数字）。程序主要功能：从键盘输入学生通讯录，以学号为关键字建立哈希表，酌情设计哈希函数和处理冲突的策略；采用哈希表方法根据输入的学号显示该学生的通讯录信息；能够修改学生的手机号码；能够添加和删除某个学生的通讯录信息。

要求：

(1) 请查阅参考文献了解哈希表的发展历史和应用背景，了解其优缺点和适用场合。

(2) 详细阐述哈希函数和处理冲突的设计思路和内容。

(3) 详细阐述程序主要数据的逻辑结构和存储结构，并说明其理由。

(4) 给出带有适当注释的源程序。

 

（1）哈希表就是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

哈希表的优点：不论哈希表中有多少数据，在进行查找、插入、删除的操作时运算得非常快，因为它的时间复杂度为O(1)。

哈希表的缺点：哈希表是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重。

哈希表的适用场合：适用于加密，解决冲突问题；适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器）哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

 

（2）哈希函数设计思路就是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应，它依赖于键的类型，对于每一种可能使用的键我们需要不同的函数。为了高效，通常避免使用显示类型转换，尽力代之以将键视为机器字的二进制正数表示的思想，这样有利于对其使用算术运算。一个优秀的哈希函数应该考虑到键的所有位，尤其对于由字符组成的键。要计算出长键的取模哈希函数，可以将键分块转换。或者用两个或三个不同的hash函数，进行多次hash以减少键的冲突。

无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。拉链法，拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。多哈希法，设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低。开放定址法，从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法。开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。线行探查法，线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

 

（3）该程序的数据集合采用的是HashMap进行存储的，在jdk1.8之前HashMap采用的是数组加链表来进行存储的，在jdk1.8之后采用了数组加链表加红黑树来进行存储，当HashMap数组元素为链表的时候，插入直接使用头插，插入复杂度O(1)；当链表长度达到了八个时，就会转换为红黑树，复杂度为O(logn)，这样虽然提高了查找的性能，但每次插入新的数据，都要维护红黑树的结构，这样算是对查找和插入元素时性能的一个权衡。

使用HashMap的理由就是这样的结构结合了链表在增删方面的高效和数组在寻址上的优势，使得程序运行效率提高。

 

（4）首先需要定义一个Student类用于存储学生信息，该类包含了学生的学号、姓名、手机号码三个属性，然后需要定义一个Map集合用于存储学生集合，因为学生的学号是唯一的，所以key值采用学生学号，value值就是学生对象，然后该系统需要多次交互，所以需要使用while(true)来保证程序一直运行，为了方便操作，每次程序开始和操作完成后系统都会显示菜单，匹配用户输入的菜单编号，即可执行对应的方法，如果输入的编号不对，则提示不支持该操作！当选择查询时，提示输入学号，然后读取输入的学号，调用map的get方法，判断结果是否为空即可，也可以调用map的containsKey方法判断是否为true，如果没有查询到则输出没有查询到该学生！否则输入学生信息；在新增、删除、修改手机号这几个操作时，同样使用get或containsKey方法进行查询，新增时还需使用put方法，删除时需要使用remove方法，修改手机号时也是使用的put方法，调用该方法时，如果key值不存在则新增，如果key值存在则会修改value值做到数据的更新。程序在编码过程中均考虑了用户输入信息的合法性，如果信息不合法时，会抓住异常给予用户提示，提高了程序的健壮性。

程序添加的实现效果如图4.1所示，修改功能如图4.2所示，删除功能如图4.3所，程序的查询功能图上均有用到，不再单独列出。

图片涉及个人隐私无法查看

该程序的实现代码如下：

import java.util.HashMap;
import java.util.Scanner;

/**
 * @author baikunlong
 * @date 2020/6/23 22:33
 */
public class Main {

    private static Scanner scanner;
    /**
     * 学生信息集合
     */
    private static HashMap<String, Student> map;

    public static void main(String[] args) {
        System.out.println("欢迎使用本系统~");
        scanner = new Scanner(System.in);
        String line = "";
        map = new HashMap<>();
        while (true) {
            System.out.println();
            System.out.println("菜单（输入对应序号即可进入操作）");
            System.out.println("1、根据学号查询");
            System.out.println("2、根据学号修改手机号");
            System.out.println("3、添加");
            System.out.println("4、删除");
            System.out.println("5、退出");
            line = scanner.nextLine().trim();
            switch (line) {
                case "1":
                    select();
                    break;
                case "2":
                    update();
                    break;
                case "3":
                    add();
                    break;
                case "4":
                    del();
                    break;
                case "5":
                    System.out.println("再见，欢迎下次使用~");
                    return;
                default:
                    System.out.println("不支持该操作！");
                    break;
            }
        }
    }
    /**
     * 修改学生手机号
     */
    private static void update() {
        try {
            System.out.println("请输入要修改手机号学生的学号和手机号，分别用空格隔开，输入完成后按回车：");
            String s = scanner.nextLine();
            String[] strings = s.split(" ");
            //如果包含该key，则存在该学生
            if (map.containsKey(strings[0])) {
                //取出该学生
                Student student = map.get(strings[0]);
                //修改手机号
                student.setPhone(strings[1]);
                //重新设置该key值的学生对象
                map.put(student.sno, student);
                System.out.println("修改成功！");
            } else {
                System.out.println("该学生不存在！");
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("输入信息有误！操作失败！");
        }
    }
    /**
     * 删除学生
     */
    private static void del() {
        System.out.println("请输入要删除的学生的学号：");
        String s = scanner.nextLine();
        //如果包含该key
        if (map.containsKey(s)) {
            //移除该key
            map.remove(s);
            System.out.println("删除成功！");
        } else {
            System.out.println("该学生不存在！");
        }
    }

    /**
     * 新增学生
     */
    private static void add() {
        try {
            System.out.println("请输入学号、姓名、手机号，分别用空格隔开，输入完成后按回车");
            String s = scanner.nextLine();
            String[] strings = s.split(" ");
            //如果已存在该key值，则不能插入了
            if (map.containsKey(strings[0])) System.out.println("该学生已存在！");
            else {
                //新增学生信息
                map.put(strings[0], new Student(strings[0], strings[1], strings[2]));
                System.out.println("添加成功！");
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("输入信息有误！操作失败！");
        }
    }

    /**
     * 查询学生
     */
    private static void select() {
        System.out.println("请输入学号：");
        String s = scanner.nextLine();
        //根据key值获取value值
        Student student = map.get(s);
        if (student == null) System.out.println("没有查询到该学生！");
        else System.out.println(student.toString());
    }

    /**
     * 学生类
     */
    static class Student {
        /**
         * 学号
         */
        private String sno;
        /**
         * 姓名
         */
        private String name;
        /**
         * 手机号
         */
        private String phone;

        @Override
        public String toString() {
            return "学生信息{" +
                    "学号='" + sno + '\'' +
                    ", 姓名='" + name + '\'' +
                    ", 手机号='" + phone + '\'' +
                    '}';
        }

        public String getSno() {
            return sno;
        }

        public void setSno(String sno) {
            this.sno = sno;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public String getPhone() {
            return phone;
        }

        public void setPhone(String phone) {
            this.phone = phone;
        }

        public Student(String sno, String name, String phone) {
            this.sno = sno;
            this.name = name;
            this.phone = phone;
        }
    }

}