雜湊表（Hash Table）& 字典樹（Trie）的程式碼和補充 Malloc 用法

圖片來源和參考內容：Hash Tables and Hash Functions

更深入的雜湊表筆記請參考：資料結構學習筆記：雜湊表（Hash Table）

想像一下，如果要在一個陣列中找出「Mia」，是否需要逐一檢查每個項目？有沒有更快的方法？

雜湊函數（Hash function）

雜湊函數（Hash function）就像是一台「資料壓縮機」，它把任意長度的資料壓縮成特定範圍的數值，稱為「雜湊值」。想像一下，有一大串名字要放進抽屜裡，為了不必每次翻箱倒櫃地找，雜湊函數就像一個貼標籤的助手。它會按照某種規則，給每個名字分配一個特定抽屜號碼，比如「Mia」可能會分到抽屜 8 號，「Sam」分到 4 號。

當我們想找某個名字時，只需照著這個編號打開對應的抽屜即可。但有時候，兩個不同名字會分到同一個抽屜，這就叫「衝突」。為解決衝突，可能會用指標將兩個名字串在一起，或是換個抽屜放置。這種方法讓雜湊表的搜尋效率高，即便資料量大，仍能迅速找到所需內容

雜湊表使用在通訊錄

假設我們要建立一個通訊錄，可以用 hash table（雜湊表）來存取人名，並利用字母的開頭來快速找到對應的位置。例如，我們可以建立一個包含 26 個索引值的 hash table。

如何知道該索引值呢？以 Mia 為例，假設 Mia 的位置是 8。這是如何計算出來的呢？

1. 先將每個字母轉為 ASCII 值。
2. 再用該值除以陣列大小（在這例子中為 11），取餘數作為索引位置，因此 Mia 的索引值是 4。

在這樣的表格中記錄資料索引值，便能方便找到每個人名。但這樣的設計也可能會遇到「衝突」（collision）的問題。例如，如果 Mia 和 Rae 的餘數都是 4，則 Rae 只能向後移動，導致查找 Rae 時需要進行線性搜尋。

為了解決這個問題，可以使用指標（pointer）或「鏈結串列」來連接同一個位置的多個元素。當衝突發生時，會將新元素放到這個位置的鏈結串列中，並透過指標指向。這樣一來，我們可以在每個索引值的基礎上儲存多個元素，而不用重新排列整個表格，提升了搜尋效率。

例如下圖，Mia 跟 Sue 都的值都是 4 ，所以他們會放在同一列並用指標連結。

字典樹（Trie）

另外，另一種資料結構——字典樹（Trie）——可以用來更直觀地儲存和搜尋文字。Trie 將每個字的字母作為節點，形成一個多層的分支結構，方便快速搜尋。例如，若有「Mia」和「Max」，這兩個名字會共享相同的前綴字母「M」，然後各自分支到不同的子節點「i」和「a」。

當名字清單更多時，也可以設計 「Mi」 或是 「Ma」「Mo」為單位搜尋取代先搜尋M再往下搜尋第二個字母，時間複雜度變低，速度變快，但是所佔用的空間就會多。

這種結構特別適合用於自動完成功能或搜尋大規模字詞資料，因為它可以避免重複存儲字母，同時提高搜尋效率。

程式碼演練：Leetcode 題目

其實，我是有問ChatGPT malloc 怎麼寫，當然google也可以

我前面這篇文章提到的，實在是太淺了... 寫了一個小時才生出來...

C 語言指標－程式碼圖解

https://leetcode.com/problems/two-sum

題目是給你目標值，請從陣列當中回傳兩個相加等於目標值的位置

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

這是 Leetcode 上 被評為簡單的題目，但是用 C 語言寫需要malloc記憶體，我完全卡再 malloc 的用法。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {// leetcode已寫好這行
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) { 
            if (nums[i] + nums[j] == target) { 
                int* result = (int*)malloc(2 * sizeof(int)); 
                result[0] = i;
                result[1] = j;
                *returnSize = 2; 
                return result;
            }
        }
    }
    *returnSize = 0; 
    return NULL;
}

讓我來解釋，

int* result = (int*)malloc(2 * sizeof(int));

基本概念是要新增兩個整數的空間，拆成兩階段來看：

• sizeof(int)：這個函式會回傳一個整數的位元組大小。在大多數系統中，int 佔用 4 個位元組（Bytes），所以 sizeof(int) 通常是 4。
• 2 * sizeof(int)：表示分配一段空間，大小為兩個整數所需的空間（在大多數系統上就是 8 個位元組）。這樣我們就能在這段記憶體中存放兩個整數（即我們找到的兩個索引）。例［0,1］
• 通常建立的記憶體儲存空間沒有指定資料型別，所以我這裡使用 (int*) 將 void* 轉型為 int*，表示這段記憶體是一組整數。result[0] 和 result[1] 存取這兩個整數位置，也就是 twoSum 找到的兩個索引。

用雜湊表使時間複雜度變 O(n)

這裡我有偷看答案怎麼建立 hash table XD，因為 C 語言寫雜湊表對我來說太難了 ，所以我用 Python 來解釋，著重在介紹概念。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:#這行程式已經內建好了　
        hashmap = {}
        for i in range(len(nums)): 
            hashmap[nums[i]] = i
        for i in range(len(nums)):
            complement = target - nums[i] #complement是代表互補值的變數，後面可以直接拿來查表
            if complement in hashmap and hashmap[complement] != i:
                return [i, hashmap[complement]]
        # If no valid pair is found, return an empty list
        return []

hashmap = {}

• 這行才是真正建立一個空的 hash table（即 hashmap）。

for i in range(len(nums)):

		hashmap[nums[i]] = i

這裡的 for 迴圈只負責將 nums 中的每個數字及其索引全部存入 hashmap 中。在這個迴圈完成後，hashmap 會包含 nums 中所有數字及其對應的索引。

第二個回圈是開始檢查互補值是否存在於 hashmap 中。

第二個 for 迴圈會重新遍歷 nums，然後計算每個數字的 complement。它會檢查兩件事：

1. complement 是否存在於 hashmap 中。
2. hashmap[complement] != i（即 complement 的索引不能和當前數字的索引相同，不可以自己相加）。

運作範例

第一步：第一個 for 迴圈（建立 hashmap）

1. i = 0，nums[i] = 2
2. • hashmap[2] = 0，此時 hashmap 為 {2: 0}
2. i = 1，nums[i] = 7
3. • hashmap[7] = 1，此時 hashmap 為 {2: 0, 7: 1}
3. i = 2，nums[i] = 11
4. • hashmap[11] = 2，此時 hashmap 為 {2: 0, 7: 1, 11: 2}
4. i = 3，nums[i] = 15
5. • hashmap[15] = 3，此時 hashmap 為 {2: 0, 7: 1, 11: 2, 15: 3}

到此為止，我們完成了 hashmap 的建立，hashmap 已經包含了 nums 陣列中每個數字的索引。_{(這段我請 ChatGPT 幫忙寫)}

第二步：第二個 for 迴圈（查找符合條件的 complement）

1. i = 0，nums[i] = 2
2. • complement = target - nums[i] = 9 - 2 = 7
   • 7 在 hashmap 中，且 hashmap[7] != 0（7 的索引為 1，不是 0），滿足條件
   • 找到答案：return [0, 1]

最後結果

此時返回 [0, 1]，即 nums 中索引為 0 和 1 的兩個數字 2 和 7 加起來等於 9，符合題目要求。

更快的方式：一次迴圈解決

^{（因方格子介面問題，註解的部分沒有反灰）}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]: 
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i
        # Return an empty list if no solution is found
        return []

運作範例

假設 nums = [2, 7, 11, 15] 且 target = 9，這段程式碼的執行步驟如下：

• 第一次迴圈 (i = 0，nums[i] = 2)：
• • complement = 9 - 2 = 7
  • 7 不在 hashmap 中，因此將 2 和它的索引 0 加入 hashmap：{2: 0}
• 第二次迴圈 (i = 1，nums[i] = 7)：
• • complement = 9 - 7 = 2
  • 2 在 hashmap 中，表示 2 和 7 可以組成一組和為 9 的數字對。
  • 返回 [1, hashmap[2]]，即 [1, 0]。