DataStructure基础——哈希表

哈希表(散列)

思路分析

基本介绍：

散列表（也叫哈希表），是根据关键码值而直接进行访问的数据结构。

它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表的价值：

对于经常要使用的数据，放在缓存层使用，减少了数据库的压力。哈希表相当于起到了一个缓存层的作用。

图解：

此处用一个实际题目来使用哈希表：

（google公司上机题:）有一个公司，当有新员工来报到时，要求将该员工的信息加入(id，性别，年龄，住址……)，当输入该员工的id时，要求查找到该员工的所有信息。要求不适用数据库，尽量节省内存，速度越快越好=》哈希表（散列）

思路分析：

1. 使用Emp类管理每个员工的信息。
2. 使用EmpLinkedList表示一条链表。
3. HashTable就是真正的哈希表，里面包含了增加、遍历、查找、删除操作。但是必须有散列函数，其作用是指示id对应的链表。

代码实现

HashTabDemo

package com.yukinoshita.dataStructure.hashTab;

import java.util.Scanner;

public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(3);

        char operate = ' ';
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("---------------------");
            System.out.println("a：增加员工");
            System.out.println("l：显示员工");
            System.out.println("f：查找员工");
            System.out.println("d：删除员工");
            System.out.println("q：退出程序");
            System.out.print("Enter operation: ");
            operate = scanner.next().charAt(0);
            System.out.println("---------------------");

            switch (Character.toLowerCase(operate)) {
                case 'a' -> {
                    System.out.print("输入id:");
                    int id = scanner.nextInt();
                    System.out.print("输入名字:");
                    String name = scanner.next();
                    hashTab.add(new Emp(id, name));
                }
                case 'l' -> {
                    hashTab.list();
                }
                case 'q' -> {
                    scanner.close();
                    System.exit(0);
                }
                case 'f'->{
                    System.out.print("请输入你要查找的员工id：");
                    int id = scanner.nextInt();
                    hashTab.findEmpById(id);
                }
                case 'd'->{
                    System.out.print("请输入你要删除的员工id：");
                    int id = scanner.nextInt();
                    hashTab.deleteByEmpId(id);
                }
                default -> System.out.println("Invalid operation");
            }
        }
    }
}

//员工
class Emp {
    public int id;
    public String name;
    public Emp next = null;//默认为空

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

//链表
class EmpLinkedList {
    private Emp head = null;//此处的head就是第一个员工

    /*
    假定添加员工时，id自增长（从小到大），则将员工添加到最后即可。
     */
    public void add(Emp emp) {
        if (head == null) {
            head = emp;
        } else {
            Emp temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = emp;
        }
    }

    public void list(int no) {
        Emp p = head;
        if (head == null) {
            System.out.println("List:" + no + " is empty");
        } else {
            do {
                System.out.print("=> id:" + p.id + " name:" + p.name);
                p = p.next;
            } while (p != null);
            System.out.println();
        }
    }

    public Emp findEmpById(int id) {
        if (head == null) {
            System.out.println("链表为空");
            return null;
        } else {
            Emp p = head;
            do {
                if (p.id == id) {
                    return p;
                }
                p = p.next;
            } while (p != null);
            return null;
        }
    }

    public void deleteByEmpId(int id) {
        if(head == null){
            System.out.println("无法删除，未找到该员工");
        }else{
            Emp p = head;
            Emp prev = head;
            do{
                if(p.id == id){
                    prev.next = p.next;//删除p节点
                    System.out.printf("员工%d：%s已成功删除\n",p.id,p.name);
                    return;
                }
                prev = p;
                p=p.next;
            }while(p != null);
            System.out.println("无法删除，未找到该员工");
        }
    }
}

//HashTab用于管理多条链表
class HashTab {
    private EmpLinkedList[] empLinkedListArray = null;
    private int size;//表示有几条链表

    public HashTab(int size) {
        this.size = size;
        empLinkedListArray = new EmpLinkedList[size];
        //不要忘了分别初始化！！！！！上述只是得到了一个数组Array，里面全为null
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }

    }

    public void add(Emp emp) {
        //根据员工id得到该员工应该添加到哪条链表
        int empLinkedListNo = hashFun(emp.id);
        empLinkedListArray[empLinkedListNo].add(emp);
    }

    //遍历所有链表，遍历hashTab（数组+链表才是hashTab）
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    //根据输入的id查找员工
    public void findEmpById(int id) {
        //使用散列函数，确定到哪条链表查找（提高查找速度的关键所在！）
        int empLinkedListNo = hashFun(id);

        Emp emp = null;
        emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
        if (emp != null) {
            System.out.println("在第"+empLinkedListNo+"条链表中找到员工："+"id:" + emp.id + " name:" + emp.name);
        }else{
            System.out.println("没有找到该员工");
        }
    }

    public void deleteByEmpId(int id){
        int empLinkedListNo = hashFun(id);//根据散列函数，定位该id所在链表
        empLinkedListArray[empLinkedListNo].deleteByEmpId(id);
    }

    //散列函数（写法很多，此处用%）
    public int hashFun(int id) {
        return id % size;
    }

}