10 哈希表(Hashtable)
引入:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的所有信息。
要求:不适用数据结构,尽量节省内存,速度越快越好=>哈希表(散列)
1)基础介绍
哈希表(又叫散列表),是根据关键码值(key value)而直接进行访问的数据结构。
也就是说,它通过关键码直接映射到表中的位置来访问,以加快查找速度
这个映射函数叫做散列函数,存放记录的数组叫散列表
2)哈希表实际应用场景
一个java程序会经常的调动数据库里的数据,为了加快这个调用,程序员在java程序和数据库之间加入一个缓存层,以缓存要调用的数据,依次加快调用速度。
缓存层可以是现有的缓存产品,比如:Redis、Memcache;也可以是自己写出,比如:哈希表。
3)哈希表的结构
1. 有两种形式:
数组+链表数组+二叉树
2.哈希表的内存结构
如图是数组(左)+链表(右)的形式
4)哈希表实现思路图解
google公司的一个上机题
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的所有信息。
要求:不适用数据结构,尽量节省内存,速度越快越好=>哈希表(散列)
添加时,保证id从低到高插入
做题流程:
使用链表来实现哈希表,该链表不带头(即:链表的第一个节点就存放雇员信息)思路分析并画示意图 代码实现↓
5)代码实现——增删改查
package DataStructures.Hashtable;import java.util.Scanner;public class HashTableDemo {public static void main(String[] args) {//创建哈希表HashTable hashTable = new HashTable(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:退出系统");System.out.println("del:删除雇员");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);hashTable.add(emp);break;case "list":hashTable.list();break;case "find":System.out.println("请输入要查找的id");id = scanner.nextInt();hashTable.findEmpById(id);break;case "del":System.out.println("请输入要删除的id");id = scanner.nextInt();hashTable.delEmp(id);break;case "exit":scanner.close();System.exit(0);break;default:break;}}}}//创建HashTable 管理多条链表class HashTable {private EmpLinkedList empLinkedListArray[];private int size;//构造器public HashTable(int size) {this.size = size;empLinkedListArray = new EmpLinkedList[size];//留坑=> 这时不要忘记分别初始化每一个链表for (int i=0;i<size;i++){empLinkedListArray[i] = new EmpLinkedList();}}//添加雇员public void add(Emp emp) {//根据员工的id得到该员工应该添加到哪条链表//所以要去编写一个散列函数↓int empLinkedListNO = hashFun(emp.id);//将emp添加到对应的链表中empLinkedListArray[empLinkedListNO].add(emp);}//遍历所有的链表,遍历hashtablpublic void list() {for (int i = 0; i < size; i++) {empLinkedListArray[i].list(i);}}//根据输入的id查找雇员public void findEmpById(int id){//使用散列函数确定哪条链表查找int empLinkedListNo = hashFun(id);Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);if(emp!=null){//找到System.out.printf("在第%d条链表中找到雇员 id = %d\n",(empLinkedListNo+1),id);}else {System.out.println("在哈希表中没有找到该雇员");}}//删除输入的id对应的雇员信息public void delEmp(int id){int empLinkedListNo = hashFun(id);empLinkedListArray[empLinkedListNo].del(id);}//编写散列函数,使用一个简单的取模法public int hashFun(int id) {return id % size;}}//表示一个雇员class Emp {public int id;public String name;public Emp next;public Emp(int id, String name) {super();this.id = id;this.name = name;}}//创建一个EmpLinkedList,表示链表class EmpLinkedList {//头指针,执行第一个Emp,因此我们这个链表的head是直接指向第一个Empprivate Emp head;//默认为null//添加雇员到链表//说明//1.假定添加雇员就是链表最后public void add(Emp emp) {//如果是添加第一个雇员if (head == null) {head = emp;return;}//出现了!链表必出现的辅助指针Emp curEmp = head;while (true) {if (curEmp.next == null) {break;}curEmp = curEmp.next;}//退出时,直接将emp加入链表curEmp.next = emp;}//遍历链表的雇员信息public void list(int no) {if (head == null) {System.out.println("第"+(no+1)+"条链表为空");return;}System.out.println("第"+(no+1)+"条链表信息为:");Emp curEmp = head;while (true) {System.out.printf(" =>id=%d name=%s\t", curEmp.id, curEmp.name);if (curEmp.next == null) {break;}curEmp = curEmp.next;}System.out.println();}//根据id查找雇员//如果查找到就返回Emp,如果没有就返回nullpublic Emp findEmpById(int id){//判断链表是否为空if(head==null){System.out.println("链表空");return null;}Emp curEmp = head;while (true){if(curEmp.id==id){break;}//退出条件if (curEmp.next==null){//no findcurEmp = null;break;}curEmp = curEmp.next;}return curEmp;}public void del(int id){if(head==null){System.out.println("链表为空,无法删除");return;}if (head.id==id){if(head.next==null){head=null;}else {head = head.next;}return;}Emp curEmp = head;boolean flag = false;while (true){if(curEmp.next==null){break;}if (curEmp.next.id==id){flag=true;break;}curEmp = curEmp.next;}if (flag){curEmp.next = curEmp.next.next;}else {System.out.println("要删除的节点不存在");}}}
注释:首先先监理节点Emp然后建立一个单无头链表EmpLinkedList最后以链表的形式转成哈希表HashTable(即用数组表示的链表)详见上面图解