資料結構基礎：雜湊
雜湊涉及將雜湊演算法應用於資料項（稱為雜湊鍵）以建立雜湊值。雜湊演算法將很大範圍的值（例如所有可能的字串或所有可能的檔案）對映到較小的值集（例如 128 位數字）。
雜湊有兩個主要應用。雜湊值可用於加快資料檢索，也可用於檢查資料的有效性。
當我們要從檔案中檢索一條記錄時，搜尋檔案以查詢所需記錄所需的時間會隨著記錄數量的變化而變化。如果我們可以為記錄的鍵生成一個雜湊，我們可以使用該雜湊值作為記錄的“地址”並直接移動到它；這花費的時間與檔案中的記錄數量無關。
可以使用雜湊來檢查資料的有效性。這可以用於檢查檔案是否傳輸正確，以及檢查檔案是否在我將其上傳到某個地方到您將其下載之間的某個時間點被故意篡改。如果我釋出了檔案和從檔案中生成的雜湊值，您可以從收到的檔案中生成一個雜湊值並比較這些雜湊值。如果雜湊演算法是一個好的密碼雜湊，那麼事故或惡意行為極不可能即使稍微修改了檔案，但它仍然會產生相同的雜湊值。
為了構建一組雜湊值，我們使用雜湊演算法來建立雜湊表。看下面的圖表，透過應用雜湊演算法，每個資料項（或雜湊鍵）都有一個雜湊值。
現在，如果我們決定搜尋
| 雜湊鍵 | 雜湊函式 | 雜湊值 |
|---|---|---|
| "Sam Doe" | 應用雜湊函式 | 雜湊值 = 3 |
我們可以搜尋雜湊表以查詢雜湊值 3，如果我們找到了它，我們就知道 Sam Doe 是存在的。
但是，如果我們搜尋不存在的項怎麼辦？看看這個例子
| 雜湊鍵 | 雜湊函式 | 雜湊值 |
|---|---|---|
| "John Thompson" | 應用雜湊函式 | 雜湊值 = 9 |
現在我們可以搜尋雜湊表，可以看到雜湊值 = 9 沒有條目，因此該資料不存在，我們不必搜尋所有資料來證明這一點。
雜湊應該是可重複的，這意味著每次我們將其應用於相同資料時，我們都應該得到相同的雜湊值。這要求我們建立一個雜湊演算法或函式
看看這個（如果你忘記了 MOD 的工作原理，去檢視！）
hashKey MOD 6
如果我們將它應用於以下雜湊鍵列表
| 雜湊鍵 | 雜湊演算法 | 雜湊值 |
|---|---|---|
| 12345 | 12345 MOD 6 | 3 |
| 67564 | 67564 MOD 6 | 4 |
| 34237 | 34237 MOD 6 | 1 |
| 23423 | 23423 MOD 6 | 5 |
| 00332 | 00332 MOD 6 | 2 |
一旦我們計算出雜湊值，我們就可以開始構建雜湊表，注意因為我們使用的是 MOD 6，所以我們有 6 個不同的雜湊值
| 雜湊值 | 雜湊鍵 |
|---|---|
| 0 | |
| 1 | 34237 |
| 2 | 00332 |
| 3 | 12345 |
| 4 | 67564 |
| 5 | 23423 |
現在，如果你被問到雜湊鍵23448是否是給定資料的成員，你會做以下操作
- 使用雜湊鍵，應用雜湊演算法並計算雜湊值
- 在雜湊表中檢查雜湊值
- 如果它存在，你找到了資料，如果它不存在，資料就不存在
23448 MOD 6 = 0 Nothing attached to 0 in the hashing table Therefore 23448 isn't stored
|
練習：雜湊表 為以下雜湊鍵和雜湊演算法建立一個雜湊表 HashKey MOD 8
答案
為以下雜湊鍵和雜湊演算法建立一個雜湊表 (HashKey + 12) MOD 8
答案
你可以在以下雜湊表中找到雜湊鍵 3245 嗎？該雜湊表基於雜湊演算法：((HashKey + 67)) MOD 8
答案 不。因為 (3245 + 67) MOD 8 = 0，雜湊表中沒有資料儲存在該鍵下 描述以下內容
答案 The hashing key is the raw data in which to be hashed. 雜湊演算法是執行函式將雜湊鍵轉換為雜湊值的演算法。雜湊值是將雜湊鍵傳遞給雜湊演算法後產生的結果。 描述如何建立雜湊表 答案 雜湊表由所有有序的雜湊值及其對應的資訊組成。
解釋如何使用雜湊值來檢查是否存在某項內容 答案 雜湊值用於檢查是否存在某項內容，因為可以重新雜湊資料，然後查詢雜湊表，這比搜尋文字更有用，因為計算機在搜尋數字方面比搜尋文字更快。
|
| 完美雜湊 | 衝突鍵 |
|---|---|
 |
 |
你可能已經注意到了這一點，當我們用完唯一的雜湊值時會發生什麼？當兩個雜湊鍵給出相同的雜湊值時會發生什麼？看看以下示例的最後一行，該示例基於雜湊演算法 HashKey MOD 6
| 雜湊鍵 | 雜湊演算法 | 雜湊值 |
|---|---|---|
| 12345 | 12345 MOD 6 | 3 |
| 67564 | 67564 MOD 6 | 4 |
| 34237 | 34237 MOD 6 | 1 |
| 23423 | 23423 MOD 6 | 5 |
| 00332 | 00332 MOD 6 | 2 |
| 00338 | 00338 MOD 6 | 2 !!! 衝突！ |
當兩個雜湊鍵導致相同的雜湊值時，這稱為衝突。這會導致問題，因為我們不能再快速找到資料是否在我們的雜湊表中，因為另一個數據可能具有相同的雜湊值。解決這個問題的方法有很多，我們將介紹兩種
當兩個雜湊鍵建立相同的雜湊值時，我們將衝突鍵放在下一個空閒的雜湊值中。
當兩個雜湊鍵產生相同的雜湊值時，我們會利用連結串列將衝突的鍵儲存在同一個位置，並將所有匹配該雜湊值的鍵連線起來。
MD5
MD5("The quick brown fox jumps over the lazy dog")
= 9e107d9d372bb6826bd81d3542a419d6
即使訊息中出現微小的變化，也會（以極高的機率）導致雜湊值發生很大變化。
MD5("The quick brown fox jumps over the lazy dog.")
= e4d909c290d0fb1ca068ffaddf22cbd0
正如你在學習資料庫時所瞭解的那樣，我們經常需要使用主鍵在表中搜索資料。主鍵是儲存在每個記錄中的唯一值。它通常是一個數字，但如果沒有數字主鍵，我們仍然需要能夠搜尋資料。例如，下表顯示了某個班級中一些學生的資訊，我們將根據每個學生的姓名進行搜尋。
| 姓名 | 出生日期 | 頭髮顏色 |
|---|---|---|
| John Smith | 19072000 | 棕色 |
| Lisa Smith | 07031999 | 紅色 |
| Sam Doe | 12121954 | 金色 |
| Sandra Dee | 01012006 | 金色 |
| Aubrey Carringtoe | 12101967 | 金色 |
| Aubrey Carring | 22102000 | 黑色 |
| Aubrey Carrington | 22102000 | 金色 |
| Aubrey Carringy | 31092007 | 無 |
| Aubrey Carringtone | 04042004 | 金色 |
| ... | ... | ... |
根據每個學生的姓名進行搜尋可能需要一些時間，因為我們可能需要搜尋
Anthony Tarkovsky
這可能需要檢查數千條不同的記錄和 17 個字元才能確定我們是否找到了它們。如果資料量更大，可能需要更長的時間。我們需要一種快速的方法來為每個資料項應用索引鍵，以便我們能夠快速搜尋資料。將索引鍵附加到每個資料項（或雜湊鍵）被稱為**雜湊**，索引值被稱為**雜湊值**。這個雜湊值不是隨機的，而是取決於要進行雜湊處理的雜湊鍵，因此每次使用相同的雜湊演算法對相同資料進行雜湊處理時，都會得到相同的雜湊值。
例如，如果我們將每個姓名（或雜湊鍵）進行雜湊處理，並且我們發現 Anthony Tarkovsky 的雜湊值為 12，那麼我們只需要檢查雜湊表，看看 12 是否存在，而不是在姓名欄位中搜索所有 17 個字元。
由於你無法從雜湊值推斷出原始值，因此雜湊也被用來儲存密碼。安全措施不完善的公司將密碼儲存在文字欄位中，這使得密碼更容易被盜。儲存密碼的更安全方法如下：更聰明的公司會這樣做。
- 使用者輸入密碼“thisisreallym3”。
- 資料庫系統將密碼雜湊為“fjj34N6*34£sdf234&”並將其儲存在資料庫中。
現在，當客戶返回網站並輸入密碼時，系統會執行以下操作：
- 使用者輸入密碼。
- 輸入的密碼會立即進行雜湊處理，並將雜湊值與資料庫中的值進行比較。
- 如果值相同，則允許使用者登入；如果值不同，則拒絕使用者登入。
這有利於處理以下情況：
- 指令碼小子入侵系統並竊取使用者資料庫。
- 他們獲得的使用者詳細資訊中只包含密碼的雜湊值。
- 雜湊密碼對於在沒有雜湊演算法的情況下找出真實密碼毫無用處（即使有雜湊演算法，它也很少有用！）。
- 即使使用者在所有網站都使用相同的密碼，他們在這個網站和其他網站上的帳戶也不會受到威脅。
雜湊演算法應該做到以下幾點：
- 衝突較少。
- 產生範圍廣泛的雜湊值。
- 對於相同的輸入，始終產生相同的雜湊輸出。