文章目錄
-
- 什麼是哈希表？
- 哈希表(散列)-Google 上機題
什麼是哈希表？
既然要了解哈希表，那麼就需要先去了解什麼是哈希函數：
一般的線性表，樹中，記錄在結構中的相對位置是随機的，即和記錄的關鍵字之間不存在确定的關系，是以，在結構中查找記錄時需進行一系列和關鍵字的比較。這一類查找方法建立在“比較“的基礎上，查找的效率依賴于查找過程中所進行的比較次數。 理想的情況是能直接找到需要的記錄，是以必須在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。
hash函數就是根據key計算出應該存儲位址的位置，而哈希表是基于哈希函數建立的一種查找表。
這位部落客對哈希表的解釋就得就很好：來吧！一文徹底搞定哈希表!
哈希表(散列)-Google 上機題
1)看一個實際需求，google公司的一個上機題:
2)有一個公司,當有新的員工來報道時,要求将該員工的資訊加入(id,性别,年齡,住址…),當輸入該員工的id時,要求查找到該員工的所有資訊.
3)要求:不使用資料庫,盡量節省記憶體,速度越快越好=>哈希表(散列)
哈希表的基本介紹:
散清單(Hash table，也叫哈希表)，是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。
google公司的一個上機題:
有一個公司,當有新的員工來報道時,要求将該員工的資訊加入(id,性别,年齡,名字,住址…),當輸入該員工的id時，要求查找到該員工的所有資訊.
要求:
1)不使用資料庫,.速度越快越好→>哈希表(散列)
2)添加時，保證按照id從低到高插入[課後思考:如果id不是從低到高插入，但要求各條連結清單仍是從低到高，怎麼解決?]
3)使用連結清單來實作哈希表,該連結清單不帶表頭[即:連結清單的第一個結點就存放雇員資訊]
4)思路分析并畫出示意圖
5)、代碼實作
import java.util.Scanner;
public class HashTabDemo {
public static void main(String[] args) {
//建立哈希表
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[] empLinkedListArray;
private int size; //表示有多少條連結清單
//構造器
public HashTab(int size) {
this.size = size;
//初始化empLinkedListArray
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);
}
//周遊所有的連結清單,周遊hashtab
public 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("在哈希表中，沒有找到該雇員~");
}
}
//編寫散列函數, 使用一個簡單取模法
public int hashFun(int id) {
return id % size;
}
}
//表示一個雇員
class Emp {
public int id;
public String name;
public Emp next; //next 預設為 null
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
//建立EmpLinkedList ,表示連結清單
class EmpLinkedList {
//頭指針，執行第一個Emp,是以我們這個連結清單的head 是直接指向第一個Emp
private Emp head; //預設null
//添加雇員到連結清單
//說明
//1. 假定，當添加雇員時，id 是自增長，即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;
}
//周遊連結清單的雇員資訊
public void list(int no) {
if(head == null) { //說明連結清單為空
System.out.println("第 "+(no+1)+" 連結清單為空");
return;
}
System.out.print("第 "+(no+1)+" 連結清單的資訊為");
Emp curEmp = head; //輔助指針
while(true) {
System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
if(curEmp.next == null) {//說明curEmp已經是最後結點
break;
}
curEmp = curEmp.next; //後移，周遊
}
System.out.println();
}
//根據id查找雇員
//如果查找到，就傳回Emp, 如果沒有找到，就傳回null
public Emp findEmpById(int id) {
//判斷連結清單是否為空
if(head == null) {
System.out.println("連結清單為空");
return null;
}
//輔助指針
Emp curEmp = head;
while(true) {
if(curEmp.id == id) {//找到
break;//這時curEmp就指向要查找的雇員
}
//退出
if(curEmp.next == null) {//說明周遊目前連結清單沒有找到該雇員
curEmp = null;
break;
}
curEmp = curEmp.next;//以後
}
return curEmp;
}
}
對于哈希表的學習就到這裡，剩下的就是要在力扣裡刷題了┭┮﹏┭┮