数据结构和算法st10:查找算法哈希表散列表
哈希表用来作为缓存层,哈希表是一个存放链表的数组,通过散列函数来定位是哪个链表的头指针
案例实现–创建哈希表
特别注意在创建数组时,需要初始化每一个链表(创建了一个空的数组,数组里面没有任何的链表)!!!!实际在hashtable中,使用散列函数来定位是哪个链表后,基本所有的操作都是调用链表里的所有方法!!!!!
public class HashEmploye {
public static void main(String[] args) {
HashtaleEmp hashtable=new HashtaleEmp(5);
Scanner scanner = new Scanner(System.in);
String key="";
while(true){
System.out.println("e:退出");
System.out.println("a:添加员工");
System.out.println("l:查询hashtable");
System.out.println("s:查询id的雇员");
key=scanner.next();
switch (key){
case "a":
System.out.println("输入id");
int id=scanner.nextInt();
System.out.println("输入name");
String name=scanner.next();
Emp emp=new Emp(id,name);
hashtable.add(emp);
break;
case "l":
hashtable.list();
break;
case "s":
System.out.println("输入要查询的id号码:");
int id0=scanner.nextInt();
hashtable.findEmp(id0);
break;
case "e":
scanner.close();
System.exit(0);
break;
default:
break;
}
}
}
}
//创建hashtable
class HashtaleEmp{
private Emplinked[] emplinkedArr;
private int size;//表示链表的条数
public HashtaleEmp(int size) {
this.size=size;
emplinkedArr = new Emplinked[size];//创建了一个空的数组,数组里面没有任何的链表
//这里需要初始化每一个链表
for (int i = 0; i < size; i ) {
emplinkedArr[i]=new Emplinked();
}
}
//编写一个散列函数:根据员工的id来判断加入哪条链表(采用取模的方式)
public int hashfun(int id){
return id%size;
}
//添加雇员
public void add(Emp emp){
//相应的第hashfun(emp.id)条链表添加员工
emplinkedArr[hashfun(emp.id)].add(emp);
}
//遍历hash表
public void list(){
for (int i = 0; i < size; i ) {
emplinkedArr[i].list(i);
}
}
//查找雇员id是否存在该雇员
public void findEmp(int id){
int emplinkedNo=hashfun(id);//找出在第几条链表中查找
if(emplinkedArr[emplinkedNo].findEmp(id)==null){
System.out.println("没有查到该雇员");
}else{
System.out.println("id为:" id "的员工找到了");
}
}
}
//表示一个雇员类
class Emp{
public int id;
public String name;
public Emp next;//默认为空
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
//表示一条员工的链表类
class Emplinked{
private Emp head;//创建一个空的头指针
//添加雇员到链表,要求id能够自增长
public void add(Emp emp){
//如果是添加的次链表的第一个员工信息
if(head==null){
head=emp;
return;//注意直接添加完就返回
}
Emp cur=head;
while (true){
if(cur.next==null){//说明cur指向了链表的最后一个节点
break;
}
cur=cur.next;
}
cur.next=emp;
}
//链表的遍历
public void list(int no){
//no作为链表所在的数组位置索引
if(head==null){
System.out.println("第" no "条链表为空");
return;
}
Emp cur=head;
System.out.printf("第" no "条链表员工的信息为:\n");
while (true){
System.out.printf("id=%d,name=%s\t",cur.id,cur.name);
if(cur.next==null){
break;//说明已经到最后一个节点
}
cur=cur.next;
}
System.out.println();
}
//根据id查找一个雇员
public Emp findEmp(int id){
if(head==null){
System.out.println("链表为空");
return null;
}
Emp cur=head;
while (true){
if(cur.id==id){//就是当前的雇员
break;
}
if(cur.next==null){//说明没有找到该雇员(肯定是cur指向了最后一个雇员,
// 但是最后一个固原也不是要找的)
cur=null;
break;
}
cur=cur.next;
}
return cur;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgagbkc
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13