李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--哈希表
Leefs
2020-02-07 PM
2643℃
0条
# 数据结构和算法学习--哈希表 ### 一、哈希表(散列) (1)看一个实际需求,google公司的一个上机题: (2)有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址...),当输入该员工的id时,要求查找到该员工的所有信息。 (3)要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列) ### 二、哈希表的基本介绍 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 ![26.哈希表01.png][1] ![26.哈希表02.png][2] ### 三、Google公司的一个上机题 ``` 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的id时,要求查找到该员工的所有信息. 要求: 不使用数据库,,速度越快越好=>哈希表(散列) 添加时,保证按照id从低到高插入 [课后思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?] 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息] 思路分析并画出示意图 代码实现[增删改查(显示所有员工,按id查询)] ``` ![26.哈希表03.png][3] **代码实现** ```java public class HashTabDemo { public static void main(String[] args) { //创建Hash表 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("exit: 退出系统"); key = scanner.next(); switch (key) { case "add": System.out.println("输入id"); int id = scanner.nextInt(); System.out.println("输入名字"); 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.findEmpById(id); break; case "exit": scanner.close(); System.exit(0); default: break; } } } } //创建HashTab管理多条链表 class HashTab{ private EmpLinkedList[] empLinkedLists; private int size;//链表数量 //构造器 public HashTab(int size){ this.size=size; empLinkedLists = new EmpLinkedList[size]; for (int i=0;i
id=%d name=%s\t", curEmp.id, curEmp.name); if(curEmp.next==null){ break; } curEmp=curEmp.next; } System.out.println(); } //根据id查找雇员 //如果查找到,就返回Emp,如果没有找到,就返回null public Emp findEmpById(int id){ if(head==null){ return null; } //辅助指针 Emp curEmp=head; while(true){ if(curEmp.id==id){ break; } //退出 if(curEmp.next == null){ curEmp = null; break; } curEmp=curEmp.next; } return curEmp; } } ``` [1]: https://lilinchao.com/usr/uploads/2020/02/52562704.png [2]: https://lilinchao.com/usr/uploads/2020/02/2899444340.png [3]: https://lilinchao.com/usr/uploads/2020/02/3962089220.png
标签:
数据结构和算法
,
哈希表
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/562.html
上一篇
数据结构和算法学习--菲波那切(黄金分割法)查找算法
下一篇
数据结构和算法学习--树结构的基础部分
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
35
其它
25
GO
48
NLP
8
标签云
GET和POST
二叉树
Eclipse
SpringCloud
并发线程
Sentinel
FileBeat
Map
Kibana
Flink
HDFS
Elastisearch
Netty
Hive
SpringBoot
nginx
Java
递归
Linux
Yarn
高并发
JavaScript
Shiro
队列
持有对象
Spark Core
Java工具类
Spark RDD
Azkaban
NIO
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞