什么是哈希表?
哈希表(Hash Table)也叫做散列表,是一种数据结构。
它通过把关键码值映射到表中一个位置来访问记录,以加快查找速度(相当于一个缓存)。这个映射函数叫做散列函数,存放记录的数组叫做散列表
我们通过在哈希表中创建private EmpLinkedList[] empLinkedListArray;来创建多个链表,每个链表都有首节点,通过散列函数指向下一个节点
代码实现思路:
首先我们先创建一个EmpNode类(相当于个人信息类),里面存放我们每个节点的信息。
//Emp雇员节点
class EmpNode{
public int id;
public String name;
public EmpNode next;//next默认为null
public 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){//这个循环就是找到链表的最后一个节点curEmp
if (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,如果找不到就返回null
public 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;
//初始化empLinkedListArray
empLinkedListArray=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);
}
//遍历所有链表,遍历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);
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("在哈希表中,没有找到该雇员");
}
}
}