1、 哈希表(散列)-Google 上机题

2、哈希表的基本介绍

3、 google 公司的一个上机题

思路分析

使用的是对象数组+链表的方式来进行存储数据信息并且通过散列函数来确定对应数组的位置。

代码实现(说明+完整过程+测试)

源代码：HashTab.java

说明：创建三个类，第一个类是员工类包含next指针，第二个类是管理员工的链表类包含head节点(头节点)，第三个类就是哈希表包含对象数组(对象为链表类)。

链表类：包含增加、查询、遍历链表、根据id查找链表的方法
哈希表：同样包含增加、查询、遍历、以及根据id查找方法(调用链表中的方法有点像web中的DAO层与Service
层)，并且包含对应散列函数方法用于计算获取到对应数组下标的链表。

注意点：**①** 这里的链表头节点不为空与之前学习的空头节点有些不同
② 创建对象数组时，创建完对象还需要创建数组中每个自定义类的对新昂

主要类

① 员工类

//创建职工类
class Emp{
    public String name;
    public int id;
    public Emp next;//下一个节点
    public Emp(String name, int id) {
        super();
        this.name = name;
        this.id = id;
    }
    @Override
    public String toString() {
        return "Emp [name=" + name + ", id=" + id + "]";
    }
}

② 员工链表类

//创建管理类的链表
class EmpList{
    private Emp head;//表示头节点
    //添加emp类到该链表的最后
    public void add(Emp emp) {
        if(head == null) {
            head = emp;//emp节点则为头节点
            return;
        }
        //设置一个辅助节点
        Emp cur = head;
        while(true) {
            //如果辅助节点下一个节点为null，那么此时就是最后一个节点
            if(cur.next == null) {
                cur.next = emp;//将emp节点插入到最后即可退出
                return;
            }
            cur = cur.next;//继续向后遍历
        }
    }
    // 遍历该链表
    public void list(int n) {
        if (head == null) {
            System.out.println("第"+n+"组链表为空!");
            return;
        }
        // 设置一个辅助节点
        Emp cur = head;
        System.out.printf("第"+n+"组链表如下：");
        while (true) {
            System.out.print(cur);//直接打印信息
            if(cur.next == null) {//说明这里是最后一个节点
                System.out.println();
                return;
            }
            //向后继续遍历
            cur = cur.next;
        }
    }
    //根据id来查找到对应emp类
    public Emp findEmpById(int id) {
        //如果头节点为空，那么返回null值
        if(head == null) {
            return null;
        }
        Emp cur = head;
        while(true) {
            if(cur.id == id) {
                break;//退出循环，此时cur为找到职工
            }
            //如果此时已经是最后一个节点，那么cur置为null，退出循环
            if(cur.next == null) {
                cur = null;
                break;
            }
            cur = cur.next;//往下进行遍历
        }
        return cur;//统一进行返回即可
    }
    //根据id删除对应信息
    public int deleteEmpById(int id) {
        if(head == null) {//链表为空返回-1
            return -1;
        }
        Emp cur = head;
        if(head.id == id) {//因为头节点是有数据的所以先单独判断头节点
            head = head.next;//直接删除本身节点
            return 1;//表示删除成功
        }
        while(true) {
            if(cur.next == null) {
                return -1;//如果到最后一个节点依旧没有找到直接返回-1表示为删除
            }            
            if(cur.next.id == id) {
                cur.next = cur.next.next;//本身节点的next直接指向删除节点的下一个节点
                return 1;//删除成功
            }
            cur = cur.next;//进行后移操作        
        }
    }
}

③ 哈希表

//创建hashtable类
class MyHashTab{
    private EmpList[] empLists;//创建一个员工链表数组
    private int size;//size表示多少个员工链表
    //创建hashtable类并配置对应size
    public MyHashTab(int size) {
        this.size = size;
        empLists = new EmpList[size];//进行开辟数组空间
        //注意点：对于对象数组不仅要开辟数组空间还要开辟对象空间
        for(int i = 0;i<size;i++) {
            empLists[i] = new EmpList();
        }
    }
    //创建一个散列函数,根据id来得到散列值
    public int hashFun(int id) {
        return id%size;
    }
    //进行添加操作
    public void add(Emp emp) {
        int hashFun = hashFun(emp.id);//获取散列值
        //根据获取的散列值来分配对应链表中，并执行该链表的add操作
        empLists[hashFun].add(emp);
    }
    //进行遍历操作
    public void list() {
        //直接遍历数组进行输出
        for(int i = 0;i<empLists.length;i++) {
            //这里进行判断即可
            if(empLists[i] != null) {
                empLists[i].list(i);
            }
        }
    }
    //进行根据id查找工作
    public void find(int id) {
        int hashFun = hashFun(id);//获取到对应数组链表的下标
        //通过对应下标找到链表进行调用方法
        Emp findEmpById = empLists[hashFun].findEmpById(id);
        if(findEmpById != null) {
            System.out.println("已在第"+hashFun+"组链表中找到，信息为:"+findEmpById);
        }else {
            System.out.printf("未找到id为%d的信息\n",id);
        }
    }
    //根据id值来进行删除工作
    public void deleteEmpById(int id) {
        int hashFun = hashFun(id);//获取到对应数组链表的下标
        int deleteEmpById = empLists[hashFun].deleteEmpById(id);
        if(deleteEmpById == 1) {
            System.out.printf("已删除第%d组下的对应id员工！\n",hashFun);
        }else {
            System.out.println("链表为空或无该节点!");
        }
    }
}

测试类(已测试)

package hashTableExer;
import java.util.Scanner;
public class HashTab {
    public static void main(String[] args) {
        MyHashTab myHashTab = new MyHashTab(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while(true) {
            System.out.println("请选择你想使用的操作：\n"
                    + "add：添加职员\n"+"list:遍历职员\n"+"find:输入id查找\n"+"delete:根据id删除\n"+"exit:退出程序");
            key = scanner.next();
            switch (key) {
            case "add":
                System.out.println("请输入姓名：");
                String name = scanner.next();
                System.out.println("请输入id：");
                int id = scanner.nextInt();
                myHashTab.add(new Emp(name, id));//向哈希表中添加一个雇员
                System.out.println("添加成功！");
                break;
            case "list":
                myHashTab.list();//进行遍历哈希表中的所有链表
                break;
            case "find":
                System.out.println("请输入你想要查找的id：");
                int findId = scanner.nextInt();
                myHashTab.find(findId);
                System.out.println("查找完成!");
                break;
            case "delete":
                System.out.println("请输入你想要删除的id：");
                int deleteId = scanner.nextInt();
                myHashTab.deleteEmpById(deleteId);
                break;
            case "exit":
                scanner.close();//手动关闭
                System.exit(0);//退出程序
            default:
                break;
            }
        }
    }
}

运行结果：这里仅仅展示删除操作，其余操作太多

整理者：长路 时间：2020/8/24-2020/8/25