[Java数据结构][9]以雇员为例的哈希表HashTable代码展开

[Java数据结构][9]以雇员为例的哈希表HashTable代码展开

文章目录

[Java数据结构][9]以雇员为例的哈希表HashTable代码展开定义一个雇员类创建一个含有添加、遍历、查找功能的雇员链表创建一个hashtable，含有添加功能，遍历功能，查找功能以及哈希函数功能(通过所给的雇员id返回一个哈希值，这里使用最简单的取模法）完整代码执行案例

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

下图就是一个简易哈希表，采用数组+链表的模式

我们的问题

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

定义一个雇员类

/* 表示一个employee */ class Emp{ public int id; public String name; public Emp next;//默认为null public Emp(int id,String name){ super(); this.id = id; this.name = name; } }

创建一个含有添加、遍历、查找功能的雇员链表

/* 创建EmpLinkedList表示链表 */ class EmpLinkedList { //头指针 private Emp head; //默认为Null /** * 假定，增加雇员时，id是自增的，从小到大，我们将该雇员直接加入到本链表的最后即可 * * @param emp 雇员 */ public void add(Emp emp) { //如果是第一个雇员 if (head == null) { head = emp; return; } //如果不是第一个雇员,使用辅助指针定位到最后 Emp curEmp = head; while (true) { if (curEmp.next == null) { break; } curEmp = curEmp.next;//后移 } //直接将Emp加入到链表最后即可 curEmp.next = emp; } /** * 遍历链表的雇员信息 * * @param no 编号 */ public void list(int no) { if (head == null) { System.out.println("第" + (no + 1) + "条链表为空~"); return; } System.out.print("第" + (no + 1) + "条链表的信息为："); Emp curEmp = head;//辅助指针 while (true) { System.out.printf("-> id = %d name = %s\t", curEmp.id, curEmp.name); if (curEmp.next == null) {//说明已经是最后的节点 break; } curEmp = curEmp.next; //后移 } System.out.println(); } /** * 根据id查找雇员 * * @param id 雇员id * @return Emp 返回雇员信息 */ public Emp findEmpById(int id) { //判断链表是否为空 if (head == null) { System.out.println("链表为空"); return null; } //辅助指针 Emp curEmp = head; while (true) { if (curEmp.id == id) {//已经找到 break; } //推出 if (curEmp.next == null) {//说明遍历当前链表没有找到 curEmp = null; break; } curEmp = curEmp.next; } return curEmp; } }

创建一个hashtable，含有添加功能，遍历功能，查找功能以及哈希函数功能(通过所给的雇员id返回一个哈希值，这里使用最简单的取模法）

/* 创建HashTable */ class HashTable { private EmpLinkedList[] empLinkedListArray; private int size; //表示有多少条链表 /** * 构造器 */ public HashTable(int size) { this.size = size; //初始化empLinkedListArray empLinkedListArray = new EmpLinkedList[size]; for (int i = 0; i < size; i++) { empLinkedListArray[i] = new EmpLinkedList(); } } /** * 添加信息 * * @param emp 雇员 */ public void add(Emp emp) { //根据员工id，得到该员工应该添加到哪一个链表 int empLinkedListNo = hashFun(emp.id); //将emp添加到相应的链表 empLinkedListArray[empLinkedListNo].add(emp); } /** * 遍历hashtable */ public void list() { for (int i = 0; i < size; i++) { empLinkedListArray[i].list(i); } } /** * 哈希函数，使用取模法 * * @param id 员工号 */ public int hashFun(int id) { return id % size; } /** * 根据输入的id查找雇员 */ public void findEmpById(int id) { //确定在哪条链表查找 int empLinkedListNo = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id); if (emp != null) {//找到 System.out.printf("在第%d条找到雇员 id = %d\n", (empLinkedListNo + 1), id); } else { System.out.println("在哈希表中，没有找到该雇员"); } } }

完整代码

public class HashTabDemo { public static void main(String[] args) { //创建哈希表 HashTable hashTable = new HashTable(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("exit:退出系统"); key = scanner.next(); switch (key) { case "add": System.out.print("输入id："); int id = scanner.nextInt(); System.out.print("输入名字："); String name = scanner.next(); //创建雇员 Emp emp = new Emp(id, name); hashTable.add(emp); break; case "list": hashTable.list(); break; case "find": System.out.print("输入要查找的id:"); id = scanner.nextInt(); hashTable.findEmpById(id); break; case "exit": scanner.close(); System.exit(0); default: break; } } } } /* 创建HashTable */ class HashTable { private EmpLinkedList[] empLinkedListArray; private int size; //表示有多少条链表 /** * 构造器 */ public HashTable(int size) { this.size = size; //初始化empLinkedListArray empLinkedListArray = new EmpLinkedList[size]; for (int i = 0; i < size; i++) { empLinkedListArray[i] = new EmpLinkedList(); } } /** * 添加信息 * * @param emp 雇员 */ public void add(Emp emp) { //根据员工id，得到该员工应该添加到哪一个链表 int empLinkedListNo = hashFun(emp.id); //将emp添加到相应的链表 empLinkedListArray[empLinkedListNo].add(emp); } /** * 遍历hashtable */ public void list() { for (int i = 0; i < size; i++) { empLinkedListArray[i].list(i); } } /** * 哈希函数，使用取模法 * * @param id 员工号 */ public int hashFun(int id) { return id % size; } /** * 根据输入的id查找雇员 */ public void findEmpById(int id) { //确定在哪条链表查找 int empLinkedListNo = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id); if (emp != null) {//找到 System.out.printf("在第%d条找到雇员 id = %d\n", (empLinkedListNo + 1), id); } else { System.out.println("在哈希表中，没有找到该雇员"); } } } /* 表示一个employee */ class Emp { public int id; public String name; public Emp next;//默认为null public Emp(int id, String name) { super(); this.id = id; this.name = name; } } /* 创建EmpLinkedList表示链表 */ class EmpLinkedList { //头指针 private Emp head; //默认为Null /** * 假定，增加雇员时，id是自增的，从小到大，我们将该雇员直接加入到本链表的最后即可 * * @param emp 雇员 */ public void add(Emp emp) { //如果是第一个雇员 if (head == null) { head = emp; return; } //如果不是第一个雇员,使用辅助指针定位到最后 Emp curEmp = head; while (true) { if (curEmp.next == null) { break; } curEmp = curEmp.next;//后移 } //直接将Emp加入到链表最后即可 curEmp.next = emp; } /** * 遍历链表的雇员信息 * * @param no 编号 */ public void list(int no) { if (head == null) { System.out.println("第" + (no + 1) + "条链表为空~"); return; } System.out.print("第" + (no + 1) + "条链表的信息为："); Emp curEmp = head;//辅助指针 while (true) { System.out.printf("-> id = %d name = %s\t", curEmp.id, curEmp.name); if (curEmp.next == null) {//说明已经是最后的节点 break; } curEmp = curEmp.next; //后移 } System.out.println(); } /** * 根据id查找雇员 * * @param id 雇员id * @return Emp 返回雇员信息 */ public Emp findEmpById(int id) { //判断链表是否为空 if (head == null) { System.out.println("链表为空"); return null; } //辅助指针 Emp curEmp = head; while (true) { if (curEmp.id == id) {//已经找到 break; } //推出 if (curEmp.next == null) {//说明遍历当前链表没有找到 curEmp = null; break; } curEmp = curEmp.next; } return curEmp; } }

执行案例

add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入id：16543135 输入名字：jacky add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入id：16543138 输入名字：tom add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 add 输入id：16543420 输入名字：jerry add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 find 输入要查找的id:5 在哈希表中，没有找到该雇员 add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 find 输入要查找的id:6 链表为空 在哈希表中，没有找到该雇员 add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 list 第1条链表的信息为：-> id = 16543135 name = jacky 第2条链表为空~ 第3条链表为空~ 第4条链表的信息为：-> id = 16543138 name = tom 第5条链表为空~ 第6条链表的信息为：-> id = 16543420 name = jerry 第7条链表为空~ add:添加雇员 list:显示雇员 find:查找雇员 exit:退出系统 exit Process finished with exit code 0