1.介绍

HashTable可以使用数组+链表的方式实现，数组中的一个元素就代表一条链表，如下图，共有7条链表。添加元素时通过hash()函数计算这个元素在数组中的位置，也就是添加到哪条链表中。获取元素时也要通过hash()函数计算出数组下标用来确定在那条链表中寻找。

image.png

2.设计思路

• 员工类
• 链表类（实现员工的增删改查）
• HashTable(调用链表类的方法实现增删改查)

3.代码实现

package com.yc.day06;

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

public class HashTableDemo {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(8);
        Scanner scanner = new Scanner(System.in);
        String key = "";
        while (true){
            System.out.println("add:添加元素");
            System.out.println("list:显示元素");
            System.out.println("find:根据id查找元素");
            System.out.println("del:根据id删除元素");
            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);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("请输入id:");
                    int findId = scanner.nextInt();
                    hashTable.findEmpById(findId);
                    break;
                case "del":
                    System.out.println("请输入id:");
                    int delId = scanner.nextInt();
                    hashTable.delEmpById(delId);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}
class HashTable{
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    public HashTable() {
    }

    public HashTable(int size) {
        this.empLinkedListArray = new EmpLinkedList[size];
        this.size =size;
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
        System.out.println(Arrays.toString(empLinkedListArray));
    }
    public void delEmpById(int id){
        int empLinkedListNo = hash(id);
        empLinkedListArray[empLinkedListNo].delEmpById(id);
    }
    public void findEmpById(int id){
        int empLinkedListNo = hash(id);
        Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
        if(emp==null){
            System.out.println("没有找到该雇员！");
        }else {
            System.out.printf("在第%d条链表中找到id为%d的雇员",(empLinkedListNo+1),id);
            System.out.println();
        }

    }
    public void add(Emp emp){
        int index = hash(emp.id);
        empLinkedListArray[index].add(emp);
    }
    public void list(){
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }
    public int hash(int id){
        return id%size;
    }
}
//员工类
class Emp{
    public Integer id;
    public String name;
    public Emp next;//指向下一个节点
    public Emp() {
    }

    public Emp(Integer id, String name) {
        this.id = id;
        this.name = name;
    }
}
//链表
class EmpLinkedList{
    private Emp head;
    //删除指定id的雇员
    public void delEmpById(int id){
        if(head==null){
            System.out.println("链表为空");
            return;
        }
        if(head.id==id){
            head = head.next;
            System.out.println(id+"雇员已删除");
            return;
        }
        Emp temp = head;
        boolean flag = false;
        while (true){
            if(temp.next.id==id){
                flag = true;
                break;
            }
            if(temp.next==null){
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
            System.out.println(id+"雇员已删除");
        }else {
            System.out.println(id+"雇员未找到");
        }
    }
    //查找指定id的雇员
    public Emp findEmpById(int id){
        if(head==null){
            return null;
        }
        Emp temp = head;
        while (true){

            if(temp.id==id){
                break;
            }
            if(temp.next==null){
                temp = null;
                break;
            }
            temp = temp.next;
        }
        return temp;
    }
    //添加雇员
    public void add(Emp emp){
        if(head==null){
            head = emp;
            return;
        }
        Emp temp = head;
        while(true){
            if(temp.next==null){
                break;
            }
            temp = temp.next;
        }
        temp.next = emp;
    }
    //显示链表
    public void list(int i){
        if(head==null){
            System.out.println("第"+(i+1)+"条链表为空");
            return;
        }
        System.out.print("第"+(i+1)+"条链表信息为：");
        Emp temp = head;
        while (true){
            System.out.printf("  ===>id=%d,name=%s\t",temp.id,temp.name);
            if(temp.next==null){
                break;
            }
            temp = temp.next;
        }
        System.out.println();
    }
}