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

更新於 2024/11/06閱讀時間約 13 分鐘

圖片來源和參考內容: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 時需要進行線性搜尋。

raw-image


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

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

raw-image



字典樹(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 = 0nums[i] = 2
    • hashmap[2] = 0,此時 hashmap 為 {2: 0}
  2. i = 1nums[i] = 7
    • hashmap[7] = 1,此時 hashmap 為 {2: 0, 7: 1}
  3. i = 2nums[i] = 11
    • hashmap[11] = 2,此時 hashmap 為 {2: 0, 7: 1, 11: 2}
  4. i = 3nums[i] = 15
    • hashmap[15] = 3,此時 hashmap 為 {2: 0, 7: 1, 11: 2, 15: 3}

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

第二步:第二個 for 迴圈(查找符合條件的 complement

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

最後結果

此時返回 [0, 1],即 nums 中索引為 01 的兩個數字 27 加起來等於 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 = 0nums[i] = 2):
    • complement = 9 - 2 = 7
    • 7 不在 hashmap 中,因此將 2 和它的索引 0 加入 hashmap:{2: 0}
  • 第二次迴圈 (i = 1nums[i] = 7):
    • complement = 9 - 7 = 2
    • 2 在 hashmap 中,表示 2 和 7 可以組成一組和為 9 的數字對。
    • 返回 [1, hashmap[2]],即 [1, 0]。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
在 C 語言中,陣列的大小固定且使用連續記憶體空間,插入新元素可能不便。鏈結串列則提供了靈活性,可以在不需要連續記憶體的情況下,輕鬆插入新節點。本文將探討陣列與鏈結串列各自的特點,並對比它們在插入與查找操作上的 Big O 複雜度,讓讀者瞭解在不同情境下使用的最佳資料結構選擇。
延續上一篇的指標,補充 pass by value 和 pass by reference 的差別。 C 語言指標-程式碼圖解 當我們在程式中呼叫函數時,變數的傳遞方式有兩種:pass by value 和 pass by reference。這兩者的區別主要在於傳遞的是「值」還是「記憶體位置的
大魔王指標:初學者的天堂路。 指標(Pointer)是 C 語言裡的「大魔王」,是資工系學生花了至少 9 小時上的課。我們一起用 18 分鐘文章快速了解指標的基本概念,中間在字串的部分我將結果和程式碼做對照。最後,我會將我跟 ChatGPT 對話放上來跟大家一起學習。
本篇文章探討計算機理論中的 P/NP 問題,分析其在演算法和理論計算中的重要性。透過回溯法及圖靈機的介紹,讀者將更瞭解 P 問題與 NP 問題的區別,以及它們在解決複雜問題中的挑戰。最後,我們將提及停機問題,揭示計算機在面對某些問題時的侷限性。
上次我們提到了演算法(algorithm),它是一種解決問題的方式。但演算法只是資料結構與演算法(Data Structures and Algorithms, DSA)這個領域的一部分。今天,我們要進一步探索這個主題,了解它的核心概念。 什麼是資料結構與演算法呢?簡單來說,資料結構是用來組織和存
上回提到,演算法是一種解決問題的方法。光是簡單的將數字有小排到大就有很多種不同的排序演算法可以選擇。這次,我們來介紹幾個常見的排序演算法,看看它們是怎麼運作的。
在 C 語言中,陣列的大小固定且使用連續記憶體空間,插入新元素可能不便。鏈結串列則提供了靈活性,可以在不需要連續記憶體的情況下,輕鬆插入新節點。本文將探討陣列與鏈結串列各自的特點,並對比它們在插入與查找操作上的 Big O 複雜度,讓讀者瞭解在不同情境下使用的最佳資料結構選擇。
延續上一篇的指標,補充 pass by value 和 pass by reference 的差別。 C 語言指標-程式碼圖解 當我們在程式中呼叫函數時,變數的傳遞方式有兩種:pass by value 和 pass by reference。這兩者的區別主要在於傳遞的是「值」還是「記憶體位置的
大魔王指標:初學者的天堂路。 指標(Pointer)是 C 語言裡的「大魔王」,是資工系學生花了至少 9 小時上的課。我們一起用 18 分鐘文章快速了解指標的基本概念,中間在字串的部分我將結果和程式碼做對照。最後,我會將我跟 ChatGPT 對話放上來跟大家一起學習。
本篇文章探討計算機理論中的 P/NP 問題,分析其在演算法和理論計算中的重要性。透過回溯法及圖靈機的介紹,讀者將更瞭解 P 問題與 NP 問題的區別,以及它們在解決複雜問題中的挑戰。最後,我們將提及停機問題,揭示計算機在面對某些問題時的侷限性。
上次我們提到了演算法(algorithm),它是一種解決問題的方式。但演算法只是資料結構與演算法(Data Structures and Algorithms, DSA)這個領域的一部分。今天,我們要進一步探索這個主題,了解它的核心概念。 什麼是資料結構與演算法呢?簡單來說,資料結構是用來組織和存
上回提到,演算法是一種解決問題的方法。光是簡單的將數字有小排到大就有很多種不同的排序演算法可以選擇。這次,我們來介紹幾個常見的排序演算法,看看它們是怎麼運作的。
你可能也想看
Google News 追蹤
Thumbnail
本文探討了複利效應的重要性,並藉由巴菲特的投資理念,說明如何選擇穩定產生正報酬的資產及長期持有的核心理念。透過定期定額的投資方式,不僅能減少情緒影響,還能持續參與全球股市的發展。此外,文中介紹了使用國泰 Cube App 的便利性及低手續費,幫助投資者簡化投資流程,達成長期穩定增長的財務目標。
Thumbnail
在資料分析過程中,透過衡量變數之間的線性或非線性關係,能有效探索數據集,篩選出重要特徵,並進行預測建模。本文介紹瞭如何理解數據、使用相關矩陣找出變數關聯性,以及利用互資訊評估變數之間的依賴程度,幫助資料科學家在建模過程中選擇適當的變數,提升模型效果。
Thumbnail
※ 何時該使用 JOIN? JOIN 使用的時機是:當你需要同時查詢一張以上的資料表的時候。 ※ SQL有哪些TABLE JOIN的方式? INNER JOIN LEFT JOIN RIGHT JOIN SELF JOIN ※ 使用 JOIN 的時候,我們需要考慮到: 我要使用哪一種
Thumbnail
本文提供了一個關於模擬法演算法的問題,介紹了操作指令的格式及其解析。透過程式碼模擬每條指令,找出回到根目錄所需的操作次數。本文詳細說明瞭模擬法的複雜度分析,能夠幫助讀者更好地理解這個問題。
Thumbnail
這邊統整了所有過去發表過關於 QUERY 函式的教學分享,希望可以方便你按照順序閱讀和練習。 QUERY 可以用來查詢、篩選、聚集、排序資料,還可以做張簡易的資料透視表,是我在 Google 試算表上做數據分析、製作報告、製作儀表板時最常用的函式之一,既方便又好用,誠心推薦!
Thumbnail
解決電腦上遇到的問題、證明正確性、探討效率 並且很著重溝通,說服別人你做的事是正確且有效率的。 內容: 計算模型、資料結構介紹、演算法介紹、時間複雜度介紹。
Thumbnail
有個簡單的方法,把儲存格的文字串連起來!一起來看看怎麼做,很好操作唷!
Thumbnail
本文探討了複利效應的重要性,並藉由巴菲特的投資理念,說明如何選擇穩定產生正報酬的資產及長期持有的核心理念。透過定期定額的投資方式,不僅能減少情緒影響,還能持續參與全球股市的發展。此外,文中介紹了使用國泰 Cube App 的便利性及低手續費,幫助投資者簡化投資流程,達成長期穩定增長的財務目標。
Thumbnail
在資料分析過程中,透過衡量變數之間的線性或非線性關係,能有效探索數據集,篩選出重要特徵,並進行預測建模。本文介紹瞭如何理解數據、使用相關矩陣找出變數關聯性,以及利用互資訊評估變數之間的依賴程度,幫助資料科學家在建模過程中選擇適當的變數,提升模型效果。
Thumbnail
※ 何時該使用 JOIN? JOIN 使用的時機是:當你需要同時查詢一張以上的資料表的時候。 ※ SQL有哪些TABLE JOIN的方式? INNER JOIN LEFT JOIN RIGHT JOIN SELF JOIN ※ 使用 JOIN 的時候,我們需要考慮到: 我要使用哪一種
Thumbnail
本文提供了一個關於模擬法演算法的問題,介紹了操作指令的格式及其解析。透過程式碼模擬每條指令,找出回到根目錄所需的操作次數。本文詳細說明瞭模擬法的複雜度分析,能夠幫助讀者更好地理解這個問題。
Thumbnail
這邊統整了所有過去發表過關於 QUERY 函式的教學分享,希望可以方便你按照順序閱讀和練習。 QUERY 可以用來查詢、篩選、聚集、排序資料,還可以做張簡易的資料透視表,是我在 Google 試算表上做數據分析、製作報告、製作儀表板時最常用的函式之一,既方便又好用,誠心推薦!
Thumbnail
解決電腦上遇到的問題、證明正確性、探討效率 並且很著重溝通,說服別人你做的事是正確且有效率的。 內容: 計算模型、資料結構介紹、演算法介紹、時間複雜度介紹。
Thumbnail
有個簡單的方法,把儲存格的文字串連起來!一起來看看怎麼做,很好操作唷!