什么是哈希表

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

试题

有一个公司，当有新员工来报道时，要求将员工的信息加入（id，性别，年龄，名字，住址），当输入员工的id时要求查找到员工的所有信息。
要求：
不使用数据库，速度越快越好。

代码

Emp：雇员类模拟结点

public class Emp {

    private int id;
    private String name;
    private Emp next; //默认为空

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
	getter and setter 方法
}

EmpLinkList：模拟一条链表

public class EmpLinkList {

    private Emp head;//默认为空

    //添加雇员到链表末尾
    public void addEmp(Emp emp){
        if (head == null) {//添加第一个雇员
            head = emp;
            return;
        }//添加的不是第一个雇员
        Emp temp = head;//辅助指针
        while (true){
            if (temp.getId() == emp.getId()){
                System.out.println("该id已经存在");
                return;
            }
            if (temp.getNext() == null){//遍历到链表最后
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(emp);//添加雇员
    }

    //遍历链表
    public void showList(int no){
        if (head == null) {
            System.out.println("第"+no+"号链表为空");
            return;
        }
        Emp temp = head;
        System.out.print("第"+no+"号链表信息为：");
        while (true){
            System.out.print(" => id="+temp.getId()+",name="+temp.getName());
            if (temp.getNext()== null) {
                break;
            }
            temp = temp.getNext();//后移遍历
        }
        System.out.println();
    }

    //根据id查找雇员
    public Emp queryById(int id){
        if (head == null) {
            System.out.println("id不存在");
            return null;
        }
        Emp temp = head;
        while(true){
            if (temp.getId() == id){
                break;
            }
            if (temp.getNext() == null){
                return null;
            }
            temp = temp.getNext();
        }
        return temp;
    }

    //根据id删除雇员
    public void deleteById(int id){
        if (head == null) {
            System.out.println("id不存在");
            return;
        }
        Emp temp = head;
        while(true){
            if (head.getId() == id){
                head = temp.getNext();
                System.out.println("删除成功");
                return;
            }
            if (temp.getNext().getId()== id){
                temp.setNext(temp.getNext().getNext());
                System.out.println("删除成功");
                return;
            }
            temp = temp.getNext();
            if (temp.getNext()== null){
                System.out.println("id不存在");
                break;
            }
        }
    }
}

HashTable：模拟哈希表

public class HashTable {
    private EmpLinkList[] empLinkListsArray;
    private int size;
    public HashTable(int size) {
        this.size = size;
        this.empLinkListsArray = new EmpLinkList[size];
        for (int i = 0; i < size; i++) {
            empLinkListsArray[i] = new EmpLinkList();
        }
    }

    //添加雇员到hash表
    public void add(Emp emp){
        //根据员工id判断应该添加到哪条链表
        int empLinkListNo = hashFunc(emp.getId());
        empLinkListsArray[empLinkListNo].addEmp(emp);
    }

    //遍历hash表
    public void showHashTable(){
        for (int i = 0; i <empLinkListsArray.length; i++) {
            empLinkListsArray[i].showList(i);
        }
    }

    //根据输入id查找雇员
    public void findEmpById(int id){
        int empLinkListNo = hashFunc(id);
        Emp emp = empLinkListsArray[empLinkListNo].queryById(id);
        System.out.println(emp==null ? "没有找到该雇员" : "雇员的信息为:id="+emp.getId()+",name="+emp.getName());
    }

    //根据输入id删除雇员
    public void delete(int id){
        int empLinkListNo = hashFunc(id);
        empLinkListsArray[empLinkListNo].deleteById(id);
    }

    //散列函数:使用取模法
    public int  hashFunc(int id){
        return id % size;
    }
}

测试类

public class Test {

    public static void main(String[] args) {
        //创建hash表
        HashTable hash = new HashTable(7);

        String key = "";
        Scanner scanner = new Scanner(System.in);
        while(true){
            System.out.println("add:添加雇员");
            System.out.println("show:显示雇员");
            System.out.println("find:查找雇员");
            System.out.println("delete:删除雇员");
            System.out.println("exit:退出");
            key = scanner.next();
            switch (key){
                case "add":
                    System.out.println("请输入id");
                    int id = scanner.nextInt();
                    System.out.println("请输入雇员名字");
                    String name = scanner.next();
                    Emp emp = new Emp(id,name);
                    hash.add(emp);
                    break;
                case "show":
                    hash.showHashTable();
                    break;
                case "find":
                    System.out.println("请输入id");
                    id = scanner.nextInt();
                    hash.findEmpById(id);
                    break;
                case "delete":
                    System.out.println("请输入id");
                    id = scanner.nextInt();
                    hash.delete(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}

输出结果

add:添加雇员
show:显示雇员
find:查找雇员
delete:删除雇员
exit:退出
add
请输入id
1
请输入雇员名字
张三

add
请输入id
8
请输入雇员名字
李四

add
请输入id
5
请输入雇员名字
王五

show
第0号链表为空
第1号链表信息为： => id=1,name=张三 => id=8,name=李四
第2号链表为空
第3号链表为空
第4号链表为空
第5号链表信息为： => id=5,name=王五
第6号链表为空

delete
请输入id
1
删除成功

show
第0号链表为空
第1号链表信息为： => id=8,name=李四
第2号链表为空
第3号链表为空
第4号链表为空
第5号链表信息为： => id=5,name=王五
第6号链表为空

exit

Process finished with exit code 0