什么是哈希表?

哈希表(Hash Table)也叫做散列表,是一种数据结构。

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

我们通过在哈希表中创建private EmpLinkedList[] empLinkedListArray;来创建多个链表,每个链表都有首节点,通过散列函数指向下一个节点

代码实现思路:

首先我们先创建一个EmpNode类(相当于个人信息类),里面存放我们每个节点的信息。

//Emp雇员节点
class EmpNode{public int id;public String name;public EmpNode next;//next默认为nullpublic EmpNode(int id, String name) {this.id = id;this.name = name;}
}

然后我们创建哈希表中的EmplinkedList链表类,用来进行相关的增删改查操作

//EmpLinkedList链表
//head是首指针(指向真正存放数据的节点),不是头结点
class EmpLinkedList{private EmpNode head;//默认为null//添加雇员到链表//假定,当添加雇员时,id是自增长,即id的分配总是从小到大//因此我们将该雇员直接加入到本链表的最后即可public void add(EmpNode empNode){//如果是添加的第一个雇员if (head==null){head=empNode;return;}//如果添加的不是第一个雇员,则使用一个辅助指针,帮助定位到最后EmpNode curEmp=head;while (true){//这个循环就是找到链表的最后一个节点curEmpif (curEmp.next==null){//说明链表到最后break;}curEmp=curEmp.next;}//现在curEmp就是链表的最后一个节点//退出的时候直接将emp加入到链表最后curEmp.next=curEmp;}//遍历链表的雇员信息public void list(int no){if (head==null){//说明链表为空System.out.println("第"+(no+1)+"链表为空");return;}System.out.print("第"+(no+1)+"链表的信息为");//定义一个辅助指针来遍历这个链表EmpNode curEmp=head;while (true){System.out.printf("=> id=%d name=%s",curEmp.id,curEmp.name);if (curEmp.next==null){break;}curEmp=curEmp.next;//后移遍历}System.out.println();}//根据id查找雇员//如果找到就返回Emp,如果找不到就返回nullpublic EmpNode findEmpById(int id){//判断链表是否为空if (head==null){System.out.println("链表为空");return null;}//定义辅助指针EmpNode curEmp=head;while (true){if (curEmp.id==id){break;}curEmp=curEmp.next;if (curEmp==null){break;}}return curEmp;}
}

最后我们就可以创建哈希表啦,里面存放我们刚刚创建的链表

//创建HashTab 管理多条链表
class HashTab{private EmpLinkedList[] empLinkedListArray;private  int size;//表示有多少条链表public HashTab(int size) {this.size = size;//初始化empLinkedListArrayempLinkedListArray=new EmpLinkedList[size];//这里的初始化只是把hash表初始化,里面的节点还没有初始化//我们把里面的节点也初始化for (int i = 0; i <size ; i++) {empLinkedListArray[i]=new EmpLinkedList();}}//编写散列函数,使用一个简单的取模方法public int hashFun(int id){return  id%size;}//添加雇员public void add(EmpNode empNode){int empLinkedListNO=hashFun(empNode.id);empLinkedListArray[empLinkedListNO].add(empNode);}//遍历所有链表,遍历hashTabpublic void list(){for (int i = 0; i < size; i++) {empLinkedListArray[i].list(i);}}//根据输入的id,查找雇员public void findEmpById(int id){//使用散列函数确定到哪条链表查找int empLinkedListNO=hashFun(id);EmpNode empNode=empLinkedListArray[empLinkedListNO].findEmpById(id);if (empNode!=null){//找到System.out.printf("在第%d条链表中找到雇员 id=%d name=%s\n",(empLinkedListNO+1),id,empNode.name);}else {System.out.println("在哈希表中,没有找到该雇员");}}
}