本篇博客是根据b站尚硅谷的数据结构教程，学习后写的学习笔记，本篇博客的重点在自己编写的代码注释上
https://www.bilibili.com/video/BV1E4411H73v?p=89
哈希表（Hash table，也叫散列表），是根据关键码值（Key value）而直接进行访问的数据结构。也就是说，它通过映射函数把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表（散列表）
哈希表一般是数组+链表或者数组+二叉树，加上哈希表的主要目的是提高查询速度
像上面这张图，左边的一侧是数组，即散列表，里面存放的不再是数据，而是一个一个的链表，然后链表里面再存储数据。比如有一个数字 16 ，散列函数是 % 15，因此用16%15=1，映射到散列表索引为1的位置，然后到这个位置对应的链表里面查询数据。这样查询速度就提升了很多倍，不需要一个一个链表的查询。
现在有一个需求：有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id，性别，年龄，姓名，住址等），当输入该员工的id时，要求查找到该员工的所有信息
这里的hashtable是一个类，里面有一个数组，数组里面存放着链表类EmplinkedList对象，即一条一条的单链表。链表类里面管理着节点类Emp对象，一个节点就是一个雇员的全部信息。这里的链表没有头节点，链表的第一个节点就存放雇员信息
这样不同的雇员，根据不同的id，经过散列函数映射到数组上的某一个位置，这个数组位置上有一条单链表，然后插入到链表尾部。这样就将不同的雇员信息散列在了不同的单链表里面，不会都存放在一条单链表上，提高了查询速度。
下面是具体的代码
首先是节点类，Emp，用来存放一个员工的信息
这里是单链表里面的节点，因此只需要一个next指向下一个节点即可
//定义一个节点的类，表示一个雇员
class Emp{
public int id;
public String name;
//单链表，next指针
public Emp next; //next默认为null
public Emp(int id,String name){
this.id = id;
this.name = name;
}
}
然后是单链表类，用来存放多个节点，管理多个雇员的信息
//创建EmplinkedList，表示链表
class EmplinkedList{
//这里链表没有头节点，因此head头指针直接指向链表的第一个数据节点
private Emp head; //默认为null
}
往单链表类里面添加不同的方法，用来管理雇员的信息
//添加雇员到链表
//这里假定添加雇员的时候，id是自增长的，即id是按从小到大的顺序进入链表
//因此直接将emp雇员添加到链表的最后面
public void add(Emp emp){
//如果head为null，说明此时链表为空，让head指向第一个雇员emp
if(head == null){
head = emp;
return;
}
//辅助变量temp，类似于指针，用来遍历整个链表
Emp temp = head;
while(true){
//temp.next为null，说明temp已经是链表的最后一个节点
if(temp.next == null){
break;
}
temp = temp.next;
}
//退出循环时，temp这个变量存放的内容就是链表的最后一个节点对象
//所以temp.next其实是给temp存放的当前节点对象里面的next变量赋值
//将emp添加到链表的最后面
temp.next = emp;
}
//遍历链表的全部节点
public void list(int no){
if(head == null){
System.out.println("第 "+no+" 条链表为空");
return;
}
System.out.print("第 "+no+" 条链表的信息为");
Emp temp = head;
while(true){
System.out.printf("=> id=%d name=%st",temp.id,temp.name);
if(temp.next == null){
break;
}
temp = temp.next;
}
System.out.println();
}
//根据id查找雇员
//如果查找到，就返回emp，如果没有找到，就返回null
public Emp getEmpById(int id){
//判断链表是否为空
if(head == null){
System.out.println("当前链表为空");
return null;
}
Emp temp = head;
while(true){
if(temp.id == id){
//找到正确雇员，结束循环
break;
}
if(temp.next == null){
//temp已经是最后一个节点，id依旧不一样，则置为null，结束循环
temp = null;
break;
}
temp = temp.next;
}
//根据循环的结果，返回雇员或者null
return temp;
}
//删除雇员
public void del(int id){
if(head == null){
System.out.println("链表为空，无法删除");
return;
}
Emp temp = head;
int flag = 0;
while(true){
if(head.id == id){
flag = 0;
break;
}
if(temp.next == null){
flag = 1;
break;
}
if(temp.next.id == id){
flag = 2;
break;
}
temp = temp.next;
}
if(flag == 0){
System.out.println("删除第一个节点");
head = head.next;
}else if(flag == 1){
System.out.println("查找的雇员id不存在");
}else{
System.out.println("删除当前节点");
temp.next = temp.next.next;
}
}
之后是HashTab类，用来创建一个hashtable对象，这个对象以数组的形式存储多个单链表
//创建HashTable数组，用来管理多条链表
class HashTab{
//HashTable是一个存储着多条链表的数组
//EmplinkedList[]类似于int[]，用来指明数组里面元素的数据类型
private EmplinkedList[] emplinkedListArray;
private int size; //表示一共有多少条链表
public HashTab(int size){
this.size = size;
//初始化emplinkedListArray数组
emplinkedListArray = new EmplinkedList[size];
//上面那一步只是初始化了一个hashtable，但是hashtable里面的链表都没有初始化
//也就是说当前只有hashTable这一个数组，数组里面全都是null，没有链表
//因此要对所有的链表进行初始化 *** 作
for(int i=0;i
初始化HashTable和单链表后，需要在HashTab类里面增加一些方法，用来管理单链表
//外界查询和增删数据只会看见HashTab，看不见链表
//用HashTab里面的方法来管理链表
//添加雇员
public void add(Emp emp){
//根据员工的id，在hashTable上查找，得到该员工应当添加到哪条链表
int emplinkedListId = hashFun(emp.id);
//将emp添加到对应的链表里面
//emplinkedListArray[emplinkedListId]就是hashTab中存储的某一条链表
emplinkedListArray[emplinkedListId].add(emp);
}
//遍历所有的链表
public void list(){
for(int i=0;i
最后在main方法中写一个菜单，测试一下
public static void main(String[] args) {
//创建一个HashTable
HashTab hashTab = new HashTab(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("del：删除雇员");
System.out.println("exit：退出系统");
key = scanner.next();
switch (key){
case "add":
System.out.println("输入id");
int id = scanner.nextInt();
System.out.println("输入name");
String name = scanner.next();
//创建雇员
Emp emp = new Emp(id, name);
hashTab.add(emp);
break;
case "list":
hashTab.list();
break;
case "find":
System.out.println("输入id");
id = scanner.nextInt();
hashTab.getEmpById(id);
break;
case "del":
System.out.println("输入id");
id = scanner.nextInt();
hashTab.del(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）