一、哈希表（散列）

1. 问题引入

2. 解决办法

哈希表实现方法有： 1）数组+链表 2）数组+二叉树

底层实现：

解释： 有一个R=[15*N]的数组， 当要找某条数据的时候， 用该数值m%15解释ji解释 ，到第X行

3. 代码实现

逻辑分析：

     1. 创建emp员工类
     1. 创建empLinkedList， 把具有相似属性的员工组成一个list
     1. 创建hash表，将每个empLinkedList的首节点串起来，组成一个array.  管理多条链表

step1: 创建员工表

// 雇员类
class Emp {
    public int id;
    public String name;
    public Emp next; // next默认为空

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

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

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

    public Emp getNext() {
        return next;
    }

    public void setNext(Emp next) {
        this.next = next;
    }
}

step2: 创建员工list表，将具有某些属性的员工放入同一个list中。 根据模来决定

// EmpLinkedList, 创建hashtable的元素类
class EmpLinkedList {
    // 该类中有头节点信息
    private Emp head = null;

    // 添加雇员
    // 链表从前往后添加，默认自增长
    public void add(Emp emp) {
        // 如果是第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        // 如果不是第一个雇员，则需要一个辅助指针指向最后
        Emp currentEmp = head;
        while (true) {
            if (currentEmp.getNext() == null) {
                // 说明已经到了最后一个节点
                currentEmp.setNext(emp);
                break;
            } else {
                currentEmp = currentEmp.getNext();
            }
        }
    }

    // 遍历链表
    public void list(int no) {
        if (head == null) {
            System.out.println("第" + (no + 1) + "条链表为空！");
            return;
        }
        Emp currentEmp = head;
        while (true) {
            System.out.println("第" + (no + 1) + "条链表信息是：");
            System.out.printf("=>id=%d name=%s \t", currentEmp.getId(), currentEmp.getName());
            if (currentEmp.getNext() == null) {
                break;
            } else {
                currentEmp = currentEmp.getNext();
            }
        }
    }

    // 根据id查找雇员
    public Emp findEmpById(int id) {
        // 如果找到了，就返回雇员信息，如果没有找到，就返回-1
        if (head == null) {
            // 当前链表为空
            System.out.println("当前链表为空！");
            return null;
        }
        // 辅助指针
        Emp temp = head;
        while (true) {
            if (temp.getId() == id) {
                break;
            }
            //退出
            if (temp.getNext() == null) {
                // 到了最后一个节点了
                System.out.println("目标雇员不存在！");
                temp = null;
                break;
            }
            temp = temp.getNext();
        }
        return temp;
    }
}

step3: 创建一个数组，保存所有list的首节点

// hash表,管理多条链表
class HashTableArray {
    private int size; // 表示共有多少条数据
    private EmpLinkedList[] empLinkedListsArray; // 数组的形似，可以用数组的下标对其赋值

    public HashTableArray(int size) {
        // 初始化array的规模
        this.size = size;
        empLinkedListsArray = new EmpLinkedList[size];
        // 不要忘记，当前只是有了HashTableArray, 但是其元素为空，所有要初始化其元素（即创建员工list表）
        for (int i = 0; i < size; i++) {
            empLinkedListsArray[i] = new EmpLinkedList();
        }
    }

    // 添加雇员信息
    public void add(Emp emp) {
        // 根据员工id来判断应该添加到哪条链表中
        int empLinkedListNo = hashFun(emp.getId());
        // 将emp加入到该条链表中
        // 下标对应的数组
        empLinkedListsArray[empLinkedListNo].add(emp);  // EmpLinkedList节点信息组成的数组，EmpLinkedList本身就是链表有add（）

    }

    // 编写一个散列函数，取膜法
    public int hashFun(int id) {
        return id % size;
    }

    // 遍历所有的链表
    public void list() {
        // 遍历所有的hashTable
        for (int i = 0; i < size; i++) {
            empLinkedListsArray[i].list(i);
        }
    }

    // 根据输入的id查找雇员
    public Emp findEmpById(int id) {
        // 首先仍然根据散列来定位到具体某条链表
        int empLinkedListNo = hashFun(id);
        // 下标对应的数组
        Emp temp = empLinkedListsArray[empLinkedListNo].findEmpById(id);
        if (temp == null) {
            System.out.println("要查找的员工不存在！");
        }
        return temp;
    }

}

step4: 创建键盘交互

HashTableArray arr = new HashTableArray(20);
        // 写一个菜单，让用户通过键盘输入值进行交互
        String key = " ";
        Scanner newScan = new Scanner(System.in);
        while (true) {
            System.out.println("Add:添加雇员！");
            System.out.println("List:打印列表！");
            System.out.println("Find:查找雇员！");
            System.out.println("Exit:退出系统！");
            key = newScan.next();
            switch (key) {
                case "Add":
                    System.out.println("请输入id!");
                    int id = newScan.nextInt();
                    System.out.println("请输入名字！");
                    String name = newScan.next();
                    // 根据输入的信息创建员工
                    Emp emp = new Emp(id, name);
                    arr.add(emp);
                    break;
                case "List":
                    System.out.println("打印出所有员工信息：\n");
                    arr.list();
                    break;
                case "Find":
                    System.out.println("请输入要查找的员工编号：");
                    int findId = newScan.nextInt();
                    arr.findEmpById(findId);
                    break;
                case "Exit":
                    newScan.close();
                    System.exit(0);
                default:
                    break;
            }
        }