目录

1.简介

 2.链表代码:

2.HashTable代码实现:

4.测试功能代码

1.简介

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

2.

 2.链表代码:

package com.ws;

public class StudentLinkList {
    //链表的头 默认为null
    private Student head;

    /**
     * 添加学生 按照学号从小到大
     * @param stu
     */
    public void add(Student stu) {
        //如果链表为空直接赋值
        if (head == null) {
            head = stu;
            return;
        }
        //如果不为空按顺序加入
        Student temp = head;
        //标识学生是否已经存在
        boolean flag = false;
        while (true) {
            //遍历到最后一个退出
            if (temp.getNext() == null) {
                break;
            }
            //找到 退出
            if (temp.getNext().getNo() > stu.getNo()) {
                break;
            }
            if (temp.getNext().getNo() == stu.getNo()) {
                //表示该学号已经存在
                flag = true;
            }
            temp = temp.getNext();
        }
        if (flag) {
            System.out.println("学号为:"+stu.getNo()+"的学生已存在不能再添加~");
        } else {
            stu.setNext(temp.getNext());
            temp.setNext(stu);
        }
    }

    /**
     * 按照学号查询学生信息
     * @param no
     * @return
     */
    public Student queryStudentByNo(int no) {
        if (head == null) {
//            System.out.println("链表为空 无法查找~");
            return null;
        }
        Student temp = head;
        while (true) {
            if (temp.getNo() == no) {
                return temp;
            }
            if (temp.getNext() == null) {
                break;
            }
            temp = temp.getNext();

        }
        return null;
    }

    /**
     * 遍历链表
     */
    public void list() {
        if (head == null) {
            System.out.println("链表为空~");
            return;
        }
        Student temp = head;
        while (true) {
            System.out.print("学号" + temp.getNo() + "姓名" + temp.getName());
            if (temp.getNext() == null) {
                System.out.println();
                break;
            }
            temp = temp.getNext();
            System.out.print(" ==> ");
        }
    }

}

2.HashTable代码实现:

package com.ws;

public class HashTable {
    //装链表的数组
    private StudentLinkList[] linkLists;
    //数组大小
    private int size;
    //构造器
    public HashTable(int size) {
        this.size = size;
        linkLists = new StudentLinkList[size];
        //初始化链表
        for (int i = 0; i < size; i++) {
            linkLists[i] = new StudentLinkList();
        }
    }

    /**
     * 散列函数 采用简单的取模法
     * @param no
     * @return
     */
    public int hashFunction(int no) {
        return no % size;
    }

    /**
     * 通过散列函数
     * @param student
     */
    public void add(Student student) {
        linkLists[hashFunction(student.getNo())].add(student);
    }

    /**
     * 遍历哈希表 显示所有学生信息
     */
    public void list() {

        for (int i = 0; i < size; i++) {
            System.out.print(i + "号链表:");
            linkLists[i].list();
        }
    }

    /**
     * 按照学号查询学生信息
     * @param no 学号
     * @return
     */
    public Student queryByNo(int no) {
        //根据散列函数决定到那个数组链表里找
        return linkLists[hashFunction(no)].queryStudentByNo(no);
    }



}

4.测试功能代码

package com.ws;

import java.util.Scanner;

public class Test1 {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);

        char key;
        int no;
        String name;

        //写一个简单的菜单
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        while (loop) {
            System.out.println("a : 添加学生信息");
            System.out.println("s : 显示学生信息");
            System.out.println("q : 按照学号查询");
            System.out.println("e : 退出");
            key = scanner.next().charAt(0);
            switch (key) {
                case 'a' :
                    System.out.println("请输入学号:");
                    no = scanner.nextInt();
                    System.out.println("请输入姓名:");
                    name = scanner.next();
                    Student stu = new Student();
                    stu.setNo(no);
                    stu.setName(name);
                    hashTable.add(stu);
                    break;
                case 's' :
                    hashTable.list();
                    break;
                case 'q' :
                    System.out.println("请输入你要查找学生的学号:");
                    no = scanner.nextInt();
                    Student stu1 = hashTable.queryByNo(no);
                    if (stu1 != null) {
                        System.out.print("学号" + stu1.getNo() + "姓名" + stu1.getName());
                        System.out.println();
                    } else {
                        System.out.print("在哈希表中，学号为" + no + "的学生没有找到~");
                        System.out.println();
                    }
                    break;
                case 'e' :
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}

测试结果:
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
a
请输入学号:
1
请输入姓名:
ws
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
q
请输入你要查找学生的学号:
1
学号1姓名ws
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
a
请输入学号:
2
请输入姓名:
ls
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
a
请输入学号:
8
请输入姓名:
ww
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
s
0号链表:链表为空~
1号链表:学号1姓名ws ==> 学号8姓名ww
2号链表:学号2姓名ls
3号链表:链表为空~
4号链表:链表为空~
5号链表:链表为空~
6号链表:链表为空~
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出