[数据结构与算法]数据结构与算法第7章：Hash表

谷歌上机题

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

Hash表介绍

散列表（Hash table， 也叫哈希表(对照java的HashMap)

• 它通过把关键码值映射到表中一个位置来访问记录， 以加快查找的速度。 这个映射函数叫做散列函数， 存放记录的数组叫做散列表。
• 实现思路
  根据对象的 hashCode 值，找到对应的数组下标，其实就是找到存储对象的链表
  

Hash表作用

• 缓存
• 快速定位查找
  

代码实现

员工emp。也就是每一个链表节点

  //头指针，执行第一个emp，因为我们这个链表的head是指向第一个Emp
    //表示员工
    static class Emp {
        public int id;
        public String name;
        public Emp next;

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

链表

//创建EmpLinkedList，表示链表
    static class EmpLikendList {

        private Emp head;

        //添加emp到链表
        //1.假定，当添加emp时，id是自增长的，即id的分配总是从小到大。因此将emp直接加入链表尾部
        public void addEmp(Emp emp) {
            //如果是添加第一个emp
            if (head == null) {
                head = emp;
                return;
            }
            Emp temp = head;
            while (true) {
                if (temp.next == null) {
                    //找到链表最后了
                    break;
                }
                temp = temp.next;
            }
            //退出循环时证明找到了链表最后一位，将next指向emp即可
            temp.next = emp;
        }

        //遍历emp链表
        public void listEmp() {
            if (head == null) {
                System.out.println("emp链表为空~");
                return;
            }
            Emp temp = head;
            while (true) {
                System.out.println("id:" + temp.id + "---name:" + temp.name);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }

        }

        //按id查找。如果找到返回emp，否则返回null
        public Emp findByEmpId(int id){
            if (head == null){
                //链表空
                return null;
            }
            Emp temp = head;
            while (temp != null){
                if (temp.id == id){
                    //找到了
                    break;
                }
                temp = temp.next;
            }
            return temp;
        }

        //按id删除。
        public void delById(int id){
            if (head == null){
                System.out.println("链表为空~");
                return;
            }
            //因为该链表设计时并无头节点，第一个节点就是员工信息。所以要判断id=链表第一个员工时
            if (head.id == id){
                //此处采用移花接木。直接让第一个元素的id，name等于第二个元素
                if (head.next == null){
                    //链表就这一个员工,链表置空即可
                    head = null;
                }else {
                    //链表还有其他员工，但是要删除链表首个员工
                    Emp temp = head.next;
                    head.id = temp.id;
                    head.name = temp.name;
                    head.next = temp.next;
                }
                return;
            }
            //要删除的不是头节点,只需找到要删除元素的上一节点即可
            //是否找到
            boolean flag = false;
            Emp temp = head;
            while (true){
                if (temp.next == null){
                    //找到了最后
                    break;
                }
                if (temp.next.id == id){
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            //判断是否找到了要删除的员工
            if (flag){
                temp.next = temp.next.next;
            }else {
                System.out.println("未找到要删除的员工=>id:"+id);
            }
        }
    }

Hash表，多个链表组成的数组

 //创建hash表管理emp链表
    static class HashTable {
        private EmpLikendList[] empLikendLists;
        //表示共有多少条链表
        private int size;

        //构造器
        public HashTable(int size) {
            this.size = size;
            //初始化empLikendLists
            empLikendLists = new EmpLikendList[size];
            //这里初始化完成还必须实例化，不然数组每个元素为null。
            for (int i = 0; i < empLikendLists.length; i++) {
                empLikendLists[i] = new EmpLikendList();
            }
        }

        //添加emp
        public void add(Emp emp) {
            //根据empId，计算emp应该放哪条链表
            int hash = getHash(emp.id);
            //将emp添加到链表尾部
            empLikendLists[hash].addEmp(emp);
        }

        //遍历hash表
        public void listHashTable() {
            for (int i = 0; i < size; i++) {
                System.out.println("=====第" + (i + 1) + "个链表=====");
                empLikendLists[i].listEmp();
            }
        }

        //按id查找
        public void findById(int id){
            //先计算出hash找到所在数组哪个位置也就是说在哪个链表
            int hash = getHash(id);
            Emp emp = empLikendLists[hash].findByEmpId(id);
            if (emp == null){
                System.out.println("未找到id为:"+id+"的员工");
            }else {
                System.out.println("id:" + emp.id + "---name:" + emp.name);
            }
        }

        //按id删除员工
        public void delById(int id){
            int hash = getHash(id);
            empLikendLists[hash].delById(id);
        }


        //编写散列函数，使用一个简单取模法
        public int getHash(int id) {
            return id % size;
        }

    }

完整代码

package com.ghl.hash;

import java.util.Scanner;

/**
 * <b>Function: </b> todo
 *
 * @program: HashTableDemo
 * @Package: com.ghl.hash
 * @author: GuoHeLong
 * @date: 2021/08/02
 * @version: 1.0
 * @Copyright: 2021 www.g1info.com Inc. All rights reserved.
 * 
 * hash表demo
 */
public class HashTableDemo {
    public static void main(String[] args) {
        HashTable table = new HashTable(6);
        String opera = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add:添加员工");
            System.out.println("list:显示");
            System.out.println("find:查找");
            System.out.println("del:id");
            System.out.println("exit:退出");
            opera = scanner.next();
            switch (opera) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入name");
                    String name = scanner.next();
                    //创建员工
                    Emp emp = new Emp(id, name);
                    table.add(emp);
                    break;
                case "list":
                    table.listHashTable();
                    break;
                case "find":
                    System.out.println("输入要查找的员工id");
                    int findId = scanner.nextInt();
                    table.findById(findId);
                    break;
                case "del":
                    System.out.println("输入要删除的员工id");
                    int delId = scanner.nextInt();
                    table.delById(delId);
                    break;
                default:
                    scanner.close();
                    System.exit(0);
            }
        }
    }

    //创建hash表管理emp链表
    static class HashTable {
        private EmpLikendList[] empLikendLists;
        //表示共有多少条链表
        private int size;

        //构造器
        public HashTable(int size) {
            this.size = size;
            //初始化empLikendLists
            empLikendLists = new EmpLikendList[size];
            //这里初始化完成还必须实例化，不然数组每个元素为null。
            for (int i = 0; i < empLikendLists.length; i++) {
                empLikendLists[i] = new EmpLikendList();
            }
        }

        //添加emp
        public void add(Emp emp) {
            //根据empId，计算emp应该放哪条链表
            int hash = getHash(emp.id);
            //将emp添加到链表尾部
            empLikendLists[hash].addEmp(emp);
        }

        //遍历hash表
        public void listHashTable() {
            for (int i = 0; i < size; i++) {
                System.out.println("=====第" + (i + 1) + "个链表=====");
                empLikendLists[i].listEmp();
            }
        }

        //按id查找
        public void findById(int id){
            //先计算出hash找到所在数组哪个位置也就是说在哪个链表
            int hash = getHash(id);
            Emp emp = empLikendLists[hash].findByEmpId(id);
            if (emp == null){
                System.out.println("未找到id为:"+id+"的员工");
            }else {
                System.out.println("id:" + emp.id + "---name:" + emp.name);
            }
        }

        //按id删除员工
        public void delById(int id){
            int hash = getHash(id);
            empLikendLists[hash].delById(id);
        }


        //编写散列函数，使用一个简单取模法
        public int getHash(int id) {
            return id % size;
        }

    }


    //创建EmpLinkedList，表示链表
    static class EmpLikendList {

        private Emp head;

        //添加emp到链表
        //1.假定，当添加emp时，id是自增长的，即id的分配总是从小到大。因此将emp直接加入链表尾部
        public void addEmp(Emp emp) {
            //如果是添加第一个emp
            if (head == null) {
                head = emp;
                return;
            }
            Emp temp = head;
            while (true) {
                if (temp.next == null) {
                    //找到链表最后了
                    break;
                }
                temp = temp.next;
            }
            //退出循环时证明找到了链表最后一位，将next指向emp即可
            temp.next = emp;
        }

        //遍历emp链表
        public void listEmp() {
            if (head == null) {
                System.out.println("emp链表为空~");
                return;
            }
            Emp temp = head;
            while (true) {
                System.out.println("id:" + temp.id + "---name:" + temp.name);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }

        }

        //按id查找。如果找到返回emp，否则返回null
        public Emp findByEmpId(int id){
            if (head == null){
                //链表空
                return null;
            }
            Emp temp = head;
            while (temp != null){
                if (temp.id == id){
                    //找到了
                    break;
                }
                temp = temp.next;
            }
            return temp;
        }

        //按id删除。
        public void delById(int id){
            if (head == null){
                System.out.println("链表为空~");
                return;
            }
            //因为该链表设计时并无头节点，第一个节点就是员工信息。所以要判断id=链表第一个员工时
            if (head.id == id){
                //此处采用移花接木。直接让第一个元素的id，name等于第二个元素
                if (head.next == null){
                    //链表就这一个员工,链表置空即可
                    head = null;
                }else {
                    //链表还有其他员工，但是要删除链表首个员工
                    Emp temp = head.next;
                    head.id = temp.id;
                    head.name = temp.name;
                    head.next = temp.next;
                }
                return;
            }
            //要删除的不是头节点,只需找到要删除元素的上一节点即可
            //是否找到
            boolean flag = false;
            Emp temp = head;
            while (true){
                if (temp.next == null){
                    //找到了最后
                    break;
                }
                if (temp.next.id == id){
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            //判断是否找到了要删除的员工
            if (flag){
                temp.next = temp.next.next;
            }else {
                System.out.println("未找到要删除的员工=>id:"+id);
            }
        }
    }

    //头指针，执行第一个emp，因为我们这个链表的head是指向第一个Emp
    //表示员工
    static class Emp {
        public int id;
        public String name;
        public Emp next;

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