哈希表(散列)-Google 上机题
- 看一个实际需求，google 公司的一个上机题:
-
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id 时,要求查找到该员工的 所有信息.
-
要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
哈希表的基本介绍
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
google 公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的 id 时, 要求查找到该员工的 所有信息.
要求:
- 不使用数据库,,速度越快越好=>哈希表(散列)
- 添加时，保证按照 id 从低到高插入 [课后思考：如果 id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?]
- 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
思路分析并画出示意图 - 代码实现
package com.xuge.hashTab; import java.util.Scanner; /** * author: yjx * Date :2022/5/3115:16 **/ public class HashTabDemo { public static void main(String[] args) { //1.创建哈希表 HashTab hashTab = new HashTab(7); //2.写一个简单的菜单 String key=""; Scanner scanner = new Scanner(System.in); while(true){ System.out.println("1:添加雇员"); System.out.println("2:显示雇员"); System.out.println("3:查找雇员"); System.out.println("4:退出系统"); key=scanner.next(); switch(key){ case "1": 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"2": hashTab.list(); break; case"3": System.out.println("请输入雇员号:"); id =scanner.nextInt(); hashTab.findById(id); break; case "4": System.exit(0); } } } } //hashTab，管理多条链表 class HashTab { private int size; private EmpLinkedList[] listArr; //构造器 public HashTab(int size) { this.size = size; this.listArr = new EmpLinkedList[size]; //不要忘了，初始化，每条链表 for (int i = 0; i < size; i++) { listArr[i]=new EmpLinkedList(); } } //添加雇员 public void add(Emp emp) { //根据员工的id，确定该员工应该加入那条链表编号 int no = hashFun(emp.id); //将emp加入到对饮链表 listArr[no].add(emp); } //遍历所有链表==hashTab public void list() { for (int i = 0; i < size; i++) { //遍历每个链表里的雇员信息 listArr[i].list(i); } } //编写一个散列函数 public int hashFun(int id) { return id % size; } public void findById(int id){ int no = hashFun(id); Emp emp = listArr[no].search(id); if(emp!=null){ System.out.printf("编号为"+(no+1)+"=>id=%d name=%s \t", emp.id, emp.name); }else{ System.out.println("在hashTab没有找到雇员:id"+id); } } } class EmpLinkedList { //头指针，指向第一个节点（第一个雇员） private Emp head;//默认为null //1.添加雇员到链表 //添加雇员时，id时自增的，总是在链表最后 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; } //2.遍历链表 public void list(int no) { if (head == null) { System.out.println("编号为:"+(no+1)+"当前链表为空.."); return; } Emp curEmp = head; while (true) { System.out.printf("编号为"+(no+1)+"=>id=%d name=%s \t", curEmp.id, curEmp.name); if (curEmp.next == null) {//说明遍历到了链表最后 break; } //后移 curEmp = curEmp.next; } System.out.println(); } //根据id查找雇员 public Emp search(int id){ //判断链表是否为空 if(head==null){ System.out.println("链表为空.."); return null; } Emp curTmp=head; while(true){ if(curTmp.id==id){ break;//curEmp指向雇员 } if(curTmp.next==null){//说明当前链表没有 curTmp=null; break; } curTmp=curTmp.next; } return curTmp; } } class Emp { public int id; public String name; public Emp next; public Emp(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Emp{" + "id=" + id + ", name='" + name + '\'' + '}'; } }
Original: https://www.cnblogs.com/XugeA/p/16330511.html
Author: xugeA
Title: 哈希表-简介
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604877/
转载文章受原作者版权保护。转载请注明原作者出处！