本文主要介绍了Java编程基础到进阶-数据结构与算法「哈希表」，通过具体的内容向大家展现，希望对大家Java开发的学习有所帮助。

基本介绍

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

Google上机题

有一个公司，当有新员工来报到时，要求将该员工的信息加入(id,性别，年龄，地址….)，当输入该员工的id时，要求查找该员工的所有信息。

要求：不使用数据库，尽量节省内存，速度越快越好。

package com.xie.hashtable;

import java.util.Scanner;

public class HashTableDemo {

    public static void main(String[] args) {

        //创建一个HashTab

        HashTab hashTab = new HashTab(7);

        String key = "";

        Scanner scanner = new Scanner(System.in);

        while (true) {

            System.out.println("add:添加雇员");

            System.out.println("list:显示雇员");

            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("输入name");

                    String name = scanner.next();

                    Emp emp = new Emp(id, name);

                    hashTab.add(emp);

                    break;

                case "list":

                    hashTab.list();

                    break;

                case "find":

                    System.out.println("请输入编号");

                    int no = scanner.nextInt();

                    hashTab.findEmpById(no);

                    break;

                case "delete":

                    System.out.println("请输入编号");

                    int deleteNo = scanner.nextInt();

                    hashTab.deleteEmpById(deleteNo);

                    break;

                case "exit":

                    scanner.close();

                    System.exit(0);

                    break;

                default:

                    break;

            }

        }

    }

}

//创建哈希表，管理多条链表

class HashTab {

    private int size;

    private EmpLinkedList[] empLinkedListArray;

    public HashTab(int size) {

        this.size = size;

        empLinkedListArray = new EmpLinkedList[size];

        for (int i = 0; i < size; i++) {

            empLinkedListArray[i] = new EmpLinkedList();

        }

    }

    //添加雇员

    public void add(Emp emp) {

        //根据员工的id，得到该员工应当添加到哪条链表

        int empLinkedListNo = hashFun(emp.id);

        //将emp添加到对应的链表

        empLinkedListArray[empLinkedListNo].add(emp);

    }

    //查找员工

    public Emp findEmpById(int id) {

        int no = hashFun(id);

        Emp empById = empLinkedListArray[no].findEmpById(id);

        if (empById == null) {

            System.out.println("不存在id=" + id + "元素");

            return null;

        } else {

            System.out.println("存在id=" + id + ",name=" + empById.name);

            return empById;

        }

    }

    //删除雇员

    public void deleteEmpById(int id) {

        int no = hashFun(id);

        empLinkedListArray[no].deleteEmp(id);

    }

    //遍历哈希表

    public void list() {

        for (int i = 0; i < size; i++) {

            empLinkedListArray[i].list(i);

        }

    }

    //编写散列函数,使用简单的取模法

    private int hashFun(int id) {

        return id % size;

    }

}

//表示雇员

class Emp {

    public int id;

    public String name;

    public Emp next;

    public Emp(int id, String name) {

        this.id = id;

        this.name = name;

    }

    @Override

    public String toString() {

        return "Emp{" +

                "id=" + id +

                ", name='" + name + '\'' +

                '}';

    }

}

//表示链表

class EmpLinkedList {

    //头指针

    private Emp head;

    //添加雇员到链表

    //说明:

    //1.当添加雇员时，id时自增的，即id分配总是从小到大,因此我们将该雇员直接加到本链表的最后即可

    public void add(Emp emp) {

        //如果是添加第一个雇员

        if (head == null) {

            head = emp;

        } else {

            Emp curr = head;

            while (true) {

                if (curr.next == null) {

                    break;

                }

                curr = curr.next;

            }

            curr.next = emp;

        }

    }

    //遍历

    public void list(int no) {

        if (head == null) {

            System.out.println("第" + (no + 1) + "链表为空");

            return;

        }

        System.out.print("第" + (no + 1) + "链表信息为:");

        Emp curr = head;

        while (true) {

            if (curr != null) {

                System.out.printf("=> id=%d,name=%s\t", curr.id, curr.name);

                curr = curr.next;

            } else {

                break;

            }

        }

        System.out.println();

    }

    //根据id查找雇员

    public Emp findEmpById(int id) {

        if (head == null) {

            System.out.println("链表为空");

            return null;

        }

        Emp temp = head;

        while (temp != null) {

            if (temp.id == id) {

                return temp;

            }

            temp = temp.next;

        }

        return null;

    }

    //根据id删除雇员

    public void deleteEmp(int id) {

        if (head == null) {

            System.out.println("没有id=" + id + "的雇员");

            return;

        }

        Emp curr = head;

        boolean flag = false;

        while (true) {

            if (curr == null) {

                break;

            }

            if (curr.next.id == id) {

                flag = true;

                break;

            }

            curr = curr.next;

        }

        if (flag) {

            curr.next = curr.next.next;

        } else {

            System.out.println("没有id=" + id + "的雇员");

        }

    }

} 

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评