0.题目引出:

看一个实际需求，google公司的一个上机题;
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id时,要求查找到该员工的所有信息.
要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

添加时，保证按照id从低到高插入

1.哈希表的介绍

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

2.哈希表实现思路

3.代码实现

public class HashTableDemo {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);
        Scanner scan = new Scanner(System.in);
        while (true){
            System.out.println("添加员工:add");
            System.out.println("显示员工:list");
            System.out.println("退出系统:exit");
            System.out.println("查找员工:find");
            System.out.println("删除员工:delete");
            String key = scan.next();
            switch (key){
                case "add":
                    System.out.print("输入id:");
                    int id = scan.nextInt();
                    System.out.print("输入名字:");
                    String name=scan.next();
                    Employee employee = new Employee(id, name);
                    hashTable.add(employee);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.print("请输入id:");
                    hashTable.findEmployeeById(scan.nextInt());
                    break;
                case "delete":
                    System.out.print("请输入id:");
                    hashTable.deleteEmployeeById(scan.nextInt());
                    break;
                case "exit":
                    scan.close();
                    System.exit(0);
                default:
                    break;

            }


        }



    }
}
//创建哈希表
class HashTable{
     public EmployeeLinkedList[]  employeeLinkedListArray;
    public int size;

    public HashTable(int size){
        //初始化
        employeeLinkedListArray=new EmployeeLinkedList[size];
        this.size=size;
        //初始化每个链表
        for(int i=0;i<size;i++)
            employeeLinkedListArray[i]=new EmployeeLinkedList();
    }

    //添加雇员
    public void add(Employee employee){
        int employeeLinkedListNo = hashFun(employee.id);
        //将emp添加到对应的链表中
        employeeLinkedListArray[employeeLinkedListNo].add(employee);


    }

    //遍历所有的链表
    public void list(){
        for(int i=0;i<size;i++){
            employeeLinkedListArray[i].list(i);
        }
    }
   //根据输入的id查找员工
    public void findEmployeeById(int id){
        int employeeLinkedListNo = hashFun(id);
        Employee employeeById = employeeLinkedListArray[employeeLinkedListNo].findEmployeeById(id);
        if (employeeById==null){
            System.out.println("未找到");
        }
        else {
            System.out.println("在第"+(employeeLinkedListNo+1)+"条链表找到:"+employeeById);
        }
    }
    //根据id删除员工
    public void deleteEmployeeById(int id){
        int employeeLinkedListNo = hashFun(id);
        boolean flag = employeeLinkedListArray[employeeLinkedListNo].deleteEmployeeById(id);
        if(flag){
            System.out.println("成功删除id="+id+"的员工");
        }
        else
            System.out.println("未找到指定员工");

    }



    //编写散列函数,这里使用一个简单的取模法
    public int hashFun(int id){
        return id%size;
    }





}
//创建链表
class EmployeeLinkedList {
    //头指针.直接指向第一个员工
    Employee head;

    //默认为尾插法
    public void add(Employee employee) {
        if (head == null) {
            head = employee;
            return;
        }
        Employee temp = head;
        while (temp.next!= null) {
            temp = temp.next;

        }
        temp.next=employee;


    }
    //遍历链表
    public void list(int i){
        i++;
        if(head==null){
            System.out.println("第"+i+"条链表为空");
            return;
        }
        Employee temp = head;
        System.out.print("第"+i+"条链表的信息为:");
        while (temp != null) {
            System.out.print("=====>"+temp);
            temp = temp.next;

        }
        System.out.println();



    }
    //根据id查找员工
    public Employee findEmployeeById(int id){
        if(head==null){
            return null;
        }
        Employee temp=head;
        while (temp!=null&&temp.id!=id){
            temp=temp.next;
        }
        return temp;

    }
    //根据id删除雇员
    public boolean deleteEmployeeById(int id){
        if(head==null)
            return false;
        Employee temp=head;
        if (temp.id==id)
            temp=null;
        while(temp.next!=null&&temp.next.id==id){
            temp=temp.next;
        }
        if (temp.next==null)
            return false;
        temp.next=temp.next.next;
        return true;

    }


}

//表示雇员
class Employee {
    public int id;
    public String name;
    public Employee next;

    public Employee() {
    }

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

    @Override
    public String toString() {
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

结果:

添加员工:add
显示员工:list
退出系统:exit
查找员工:find
删除员工:delete

添加和遍历

add

list

第1条链表为空
第2条链表的信息为:=====>Employee{id=1, name=’zxn’}=====>Employee{id=8, name=’ql’}
第3条链表的信息为:=====>Employee{id=2, name=’xcl’}
第4条链表为空
第5条链表为空
第6条链表为空
第7条链表为空

查找