# 雜湊表(Hash Table)

**Google上機題**

有一個公司，當有新的員工來報導時，要求將該員工的資訊加入(id,性別,年齡,住址..)，當輸入該員工的id時，要求查找到該員工的所有資訊。

要求：不使用資料庫，儘量節省記憶體，速度越快越好 = 雜湊表

後面我們會來實現這個情境。

## 基本介紹

雜湊表是根據 **鍵(key)** 直接查詢在記憶體儲存位置的資料結構。

* 鍵 如：剛剛舉例的 id

它通過把鍵值映射到表中一個位置來訪問記錄，以加快搜尋的速度。
這個映射函數叫做雜湊函數，存放記錄的陣列叫做雜湊表。

一個通俗的例子是，為了查找電話簿中某人的號碼，可以創建一個按照人名首字母順序排列的表(即建立人名 `x` 到首字母 `F(x)` 的一個函數關係)，在首字母為W的表中查找「王」姓的電話號碼，顯然比直接查找就要快得多。這裡使用**人名**作為關鍵字，「取首字母」是這個例子中雜湊函數的函數法則`F()`，存放首字母的表對應雜湊表。

關鍵字和函數法則理論上可以任意確定。

## 應用場景

我們常常會需要去資料庫抓取資料然後返回，但有些數據沒有必要每次都去資料庫抓取，所以一般來說會加一個cache，將常用的數據存在cache，直接在cache抓取數據。

通常來說我們可以用常見的Redis、Memcache來實現，但我們也可以自己寫出，比如利用雜湊表，可以把數據先放入到雜湊表中，取數據先在雜湊表中取，這樣取數據的時候便無須到資料庫取，節省了部分時間。


雜湊表常見的結構：
1. 陣列 + 鏈結串列
2. 陣列 + 二元樹

## 舉例說明
因為目前還沒提到二元樹的部分，所以我們雜湊表的實現是以陣列加鏈結串列為主。

陣列放的是鏈結串列 => 鏈結串列陣列
用雜湊函數得到這個數據在哪個鏈結串列。

比如這張圖，有 16 個鏈結串列，我要找到 `111` 這個值，只需要 `111 % 16 = 15` 就能知道 111 在第十五個鏈結串列中。


## 思路分析

我們用這張圖來理解使用雜湊表來管理員工資訊至少需要三個class

員工節點 Emp , 鏈結串列 EmpLinkedList , 雜湊表 HashTab


## 程式碼實現

節點類

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;
    }
}

鏈結串列類

class EmpLinkedList {
    // 頭節點 指向第一個 Emp, 這個鏈結串列的 head 是直接指向第一個員工
    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;
            }
            // 遍歷結束沒找到 退出
            if(curEmp.next == null) {
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }
}

雜湊表

//Hash Table 管理多條鏈結串列
class HashTable {
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    /**
     * 
     * @param size 多少條鏈結串列
     */
    public HashTable(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) {
        int empLinkedListNum = hashFun(emp.id);
        // 將 emp 添加到對應鏈結串列中
        empLinkedListArray[empLinkedListNum].add(emp);
    }

    // 遍歷所有鏈結串列, 遍歷hash table
    public void list() {
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }
    // 根據id搜尋員工
    public void findEmpById(int id) {
        // 使用雜湊函數確定到哪條鏈結串列搜尋
        int empLinkedListNum = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNum].findEmpById(id);
        if(emp != null) {
            System.out.printf("在第 %d 條鏈結串列中找到員工id = %d , name = %s a\n",(empLinkedListNum + 1), id, emp.name);
        } else {
            System.out.println("在雜湊表中沒有找到該員工資訊");
        }
    }

    // 編寫雜湊函數, 使用簡單的取模法
    public int hashFun(int id) {
        return id % size;
    }

}

主程式創建雜湊表和菜單

public class HashTabDemo {
    public static void main(String[] args) {
        // 創建雜湊表
        HashTable hashTab = new HashTable(7);

        String key = "";
        Scanner sc = new Scanner(System.in);
        while(true) {
            System.out.println("a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統");
            key = sc.next();
            switch (key) {
                case "a":
                    System.out.println("輸入員工id: ");
                    int id = sc.nextInt();
                    System.out.println("輸入員工名字: ");
                    String name = sc.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "l":
                    hashTab.list();
                    break;
                case "f":
                    System.out.println("請輸入要搜尋的id: ");
                    id = sc.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "e":
                    sc.close();
                    System.out.println("退出系統");
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

output

a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
a
輸入員工id: 
1
輸入員工名字: 
sandy
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
l
第 1 鏈結串列為空
第 2 鏈結串列資訊為 => id = 1 , name = sandy
第 3 鏈結串列為空
第 4 鏈結串列為空
第 5 鏈結串列為空
第 6 鏈結串列為空
第 7 鏈結串列為空
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
a
輸入員工id: 
8
輸入員工名字: 
tom
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
l
第 1 鏈結串列為空
第 2 鏈結串列資訊為 => id = 1 , name = sandy     => id = 8 , name = tom
第 3 鏈結串列為空
第 4 鏈結串列為空
第 5 鏈結串列為空
第 6 鏈結串列為空
第 7 鏈結串列為空
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
f
請輸入要搜尋的id: 
8
在第 2 條鏈結串列中找到員工id = 8 , name = tom 
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
e
退出系統

### 刪除節點

老師留下了刪除員工資訊的作業。

`LinkedList` 類寫一個刪除方法，主要需要使用兩個索引 temp, prev 來遍歷搜尋和刪除，temp 用於指向當前節點，prev指向當前的前一個節點，當 temp 遍歷找到要刪除的節點時，prev.next指向temp.next即能刪除節點。(這部分和雙向鏈結串列有關)

// 刪除元素
public Emp delById(int id) {
    if (head == null) {
        return null;
    }
    // 非空的鏈結串列才需要循環
    Emp temp = head;
    Emp prev = head;
    while (true) {
        if (temp.id == id) {
            // 找到要刪除的元素
            break;
        }
        if (temp.next == null) {
            // 當前節點的為最末尾
            temp = null;
            break;
        }
        prev = temp;  // 將 prev 指向當前節點
        temp = temp.next; // 將當前節點後移 繼續遍歷
    }

    // 沒有找到要刪除的元素
    if (temp == null) {
        return null;
    }
    // head 為要刪除的節點
    if (head == temp) {
        head = temp.next;
        return temp;
    }
    // 找到要刪除的元素 temp, 將 prev.next 指向 temp.next
    prev.next = temp.next;
    return temp;
}

在`HashTab` 類中也要加上刪除方法，用於接收要刪除的id，然後判斷該id屬於哪個鏈結串列之後去調用`LinkedList`類的delById方法。

// 刪除員工資訊
public Emp delById(int id) {
    // 先找到 id 所屬的鏈結串列
    int no = hashFun(id);
    // 判斷 no 值是否大於或小於範圍
    if (no > size || no < 0) {
        System.out.printf("id = %d 範圍錯誤\n", id);
        return null;
    }

    Emp emp = empLinkedListArray[no].delById(id);
    if (emp == null) {
        System.out.printf("在第 %d 條鏈結串列中沒找到 id = %d 的員工，删除失敗!! \n", no, id);
    } else {
        System.out.printf("在第 %d 條鏈結串列中找到 id = %d 的員工, name = %s , 删除成功!! \n", no, id, emp.name);
    }
    return emp;
}

來試著跑跑看

public static void main(String[] args) {
    // 創建雜湊表
    HashTable hashTab = new HashTable(7);

    String key = "";
    Scanner sc = new Scanner(System.in);
    while(true) {
        System.out.println("a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統");
        key = sc.next();
        switch (key) {
            case "a":
                System.out.println("輸入員工id: ");
                int id = sc.nextInt();
                System.out.println("輸入員工名字: ");
                String name = sc.next();
                Emp emp = new Emp(id, name);
                hashTab.add(emp);
                break;
            case "l":
                hashTab.list();
                break;
            case "f":
                System.out.println("請輸入要搜尋的id: ");
                id = sc.nextInt();
                hashTab.findEmpById(id);
                break;
            case "d":
                System.out.println("請輸入要刪除的id: ");
                id = sc.nextInt();
                hashTab.delById(id);
                break;
            case "e":
                sc.close();
                System.out.println("退出系統");
                System.exit(0);
            default:
                break;
        }
    }
}

output

a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
a
輸入員工id: 
1
輸入員工名字: 
tom
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
a
輸入員工id: 
2
輸入員工名字: 
qq
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
a
輸入員工id: 
8
輸入員工名字: 
sandy
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
f
請輸入要搜尋的id: 
2
在第 3 條鏈結串列中找到員工id = 2 , name = qq
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
l
第 1 鏈結串列為空
第 2 鏈結串列資訊為 => id = 1 , name = tom       => id = 8 , name = sandy
第 3 鏈結串列資訊為 => id = 2 , name = qq
第 4 鏈結串列為空
第 5 鏈結串列為空
第 6 鏈結串列為空
第 7 鏈結串列為空
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
d
請輸入要刪除的id: 
8
在第 1 條鏈結串列中找到 id = 8 的員工, name = sandy , 删除成功!! 
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
l
第 1 鏈結串列為空
第 2 鏈結串列資訊為 => id = 1 , name = tom
第 3 鏈結串列資訊為 => id = 2 , name = qq
第 4 鏈結串列為空
第 5 鏈結串列為空
第 6 鏈結串列為空
第 7 鏈結串列為空
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
d
請輸入要刪除的id:
2
在第 2 條鏈結串列中找到 id = 2 的員工, name = qq , 删除成功!!
a(add): 添加員工資訊 | f(find): 搜尋員工資訊 | d(delete): 刪除員工資訊 | l(list): 顯示員工資訊 | e(exit): 退出系統
l
第 1 鏈結串列為空
第 2 鏈結串列資訊為 => id = 1 , name = tom
第 3 鏈結串列為空
第 4 鏈結串列為空
第 5 鏈結串列為空
第 6 鏈結串列為空
第 7 鏈結串列為空