總目錄：地址如下看總綱
1、Google 公司曾 一個實際需求
1朦拖、當(dāng)有新的員工來報道時,要求將該員工的信息加入(id,性別,年齡,住址..),當(dāng)輸入該員工的id時,要求查找到該員工的 所有信息.
2需忿、不使用數(shù)據(jù)庫,盡量節(jié)省內(nèi)存,速度越快越好=>哈希表(散列)
2、哈希表介紹
散列表（Hash table畔况，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)慧库。
也就是說跷跪，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度齐板。
這個映射函數(shù)叫做散列函數(shù)吵瞻，存放記錄的數(shù)組叫做散列表（15 = 111 % 15）
image.png
image.png
3、哈希表設(shè)計思想
HashTab 既一個數(shù)組甘磨，用于存儲多個鏈表（其實 hashtab源碼 底層也是一個動態(tài)擴展的數(shù)組）
Emp 既一個店員
EmpLinkedList 既一個鏈表橡羞，將這些店員串起來的鏈表
image.png
4、代碼
/**
* title:
* @author 阿K
* 2020年12月27日 下午11:23:07
*/
public class HashTabDemo {
public static void main(String[] args) {
// 創(chuàng)建哈希表
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: 退出系統(tǒng)");
key = scanner.next();
switch (key) {
case "add":
System.out.println("輸入id");
int id = scanner.nextInt();
System.out.println("輸入名字");
String name = scanner.next();
// 創(chuàng)建 雇員
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;// 鏈表條數(shù)
// 構(gòu)造器(一系列初始化工作
public HashTab(int size) {
this.size = size;
// 初始化 hashTab卿泽，
// 注：不僅僅初始化 hashTab ，以及存放的 linkedList也需要初始化
empLinkedListArray = new EmpLinkedList[size];
for (int i = 0; i < empLinkedListArray.length; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
// 添加
public void add(Emp emp) {
// 獲取店員的id，根據(jù)id 決定應(yīng)當(dāng)添加到哪條鏈表
int empLinkedListNo = hashCodeLow(emp.id);
// 將 emp 添加到對應(yīng)的鏈表中
empLinkedListArray[empLinkedListNo].add(emp);
}
// 遍歷 hashtab == 遍歷所有鏈表
public void list() {
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
// 根據(jù)輸入的 id 签夭，查找店員
public void findEmpById(int id) {
// 使用散列函數(shù)值齐邦，確定在哪條鏈表進行查找
int empLinkedListNo = hashCodeLow(id);
Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
if (emp != null) {// 找到
System.out.printf("在第%d條鏈表中找到 店員 id = %d\n", (empLinkedListNo + 1), id);
} else {
System.out.println("在哈希表中，沒有找到該店員~");
}
}
// 散列函數(shù)（低配版--源碼可能比較牛逼）
public int hashCodeLow(int id) {
return id % size;
}
}
// 鏈表
class EmpLinkedList {
// 頭節(jié)點第租，直接指向 第一個 emp
private Emp head;
// 添加：
// 1措拇、若添加店員時，id總是從小到大自增長慎宾，因此我們該將店員直接插入到鏈表最后即可
public void add(Emp emp) {
// 若添加的是第一個店員
if (head == null) {
head = emp;
return;
}
// 若不是則需要一個輔助直接丐吓，幫助定位到最后
Emp curEmp = head;
while (true) {
if (curEmp.next == null) {// 到了最后一個節(jié)點
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) {
// 已經(jīng)到最后一個節(jié)點
break;
}
curEmp = curEmp.next;// 后移
}
System.out.println();
}
// 要查找的店員 id
public Emp findEmpById(int no) {
// 判空
if (head == null) {
System.out.println("空鏈表趟据，您查找的雞兒券犁？");
return null;
}
// 輔助指針，查找
Emp temp = head;
while (true) {
if (temp.id == no) {
// 找到
break;
}
// 說明遍歷到最后還是沒找到(退出
if (temp.next == null) {
temp = null;// 既沒找到汹碱，最終要返回的就是 null
break;
}
temp = temp.next;// 后移
}
return temp;
}
// 刪除 根據(jù)id
}
// 店員
class Emp {
public int id;
public String name;
public Emp next;// 默認 null
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
5族操、展示
image.png
