跳轉到

02.4-雜湊法

雜湊法（Hashing）是一種用於快速查找、插入和刪除元素的技術。它將數據通過一個特定的雜湊函數映射到一個固定大小的數組（稱為雜湊表）中。每個元素在表中的位置是由其鍵（key）經過雜湊函數運算得到的。雜湊法常常用於需要高效查找的場景，並在許多數據結構中得到應用，如哈希表（Hash Table）和哈希集合（Hash Set）。

1. 雜湊法的基本原理#

雜湊法的核心思想是利用一個雜湊函數（Hash Function）將數據的鍵映射到一個特定的索引位置，這樣可以實現快速的查找操作。具體步驟如下：

  1. 雜湊函數（Hash Function）：將輸入的鍵轉換為一個數值，這個數值對應著雜湊表中的索引。理想的雜湊函數應該能夠將不同的鍵均勻地映射到表中的各個位置。
  2. 雜湊表（Hash Table）：一個固定大小的數組，用來存儲元素。每個元素都是由鍵和對應的值（key-value pair）組成。
  3. 衝突處理（Collision Resolution）：由於不同的鍵可能會經過雜湊函數映射到相同的位置，這樣就會發生“衝突”。常見的衝突處理方法包括：
  4. 鏈式法（Chaining）：將所有哈希到同一位置的元素保存在一個鏈表中。
  5. 開放地址法（Open Addressing）：當衝突發生時，尋找表中其他空的位置來存儲元素。

2. 雜湊函數的設計#

一個好的雜湊函數應該具備以下特性： - 均勻性：雜湊函數應該能夠將不同的鍵均勻地分布到雜湊表中，避免某些位置過於集中，造成衝突。 - 快速性：雜湊函數的計算應該非常高效，避免成為性能瓶頸。 - 確定性：對於相同的輸入鍵，雜湊函數應該始終產生相同的結果。

常見的雜湊函數包括： - 除法法（Division Method）：將鍵除以表大小，並取餘數。 [ h(k) = k \mod m ] 其中 \(k\) 是鍵， \(m\) 是雜湊表的大小。 - 乘法法（Multiplication Method）：將鍵與一個常數相乘後，取小數部分並放大。 [ h(k) = \lfloor m (kA \mod 1) \rfloor ] 其中 \(A\) 是一個常數，通常取值在 \([0,1)\) 範圍內。

3. 衝突處理方法#

由於雜湊函數不能保證每個鍵都映射到唯一的位置，衝突在所難免。常見的衝突處理方法有：

3.1 鏈式法（Chaining）#

鏈式法是通過為每個雜湊表的槽位建立一個鏈表（或其他數據結構）來處理衝突。當多個元素哈希到相同的位置時，它們將被存儲在這個位置的鏈表中。

  • 查找：首先通過雜湊函數找到索引，然後遍歷該位置的鏈表來查找元素。
  • 插入：將新元素插入到對應位置的鏈表中。
  • 刪除：從鏈表中刪除元素。

優點： - 可以處理無限數量的元素，表的大小不受限。 - 插入和刪除操作較為簡單。

缺點： - 在某些情況下，若所有元素都被映射到相同的位置，查找性能會變差。

3.2 開放地址法（Open Addressing）#

開放地址法在碰到衝突時，會尋找其他的空槽來存儲元素。常見的開放地址法有： - 線性探測（Linear Probing）：當發生衝突時，檢查表中下一個位置，直到找到一個空槽。 - 二次探測（Quadratic Probing）：與線性探測類似，但步長是平方的，而不是常數。 - 雙重哈希（Double Hashing）：使用第二個哈希函數來決定步長，避免了線性探測和二次探測可能出現的聚集問題。

優點： - 不需要額外的數據結構，節省空間。 - 查找和插入操作相對簡單。

缺點： - 需要處理碰撞後的查找，可能增加運算開銷。 - 如果表過滿，性能會大幅下降。

4. 雜湊表的操作#

常見的雜湊表操作包括： - 插入：將一個鍵值對插入雜湊表中，通過雜湊函數計算索引並存儲元素。 - 查找：通過鍵值查找對應的元素，首先計算索引，然後進行相應的衝突處理（如鏈式法或開放地址法）。 - 刪除：刪除指定鍵的元素，找到元素後移除並重新處理可能的衝突。

5. 時間複雜度#

  • 查找操作：在理想情況下，雜湊法的查找時間是 \(O(1)\) ，即常數時間。然而，在最壞情況下，查找時間可能退化為 \(O(n)\) ，例如所有元素都哈希到相同的位置。
  • 插入操作：在理想情況下，插入操作的時間是 \(O(1)\) 。在衝突較少的情況下，插入仍然能夠保持高效。
  • 刪除操作：刪除操作的時間複雜度也通常是 \(O(1)\) ，但在處理衝突時，可能需要更多的時間。

6. 小結#

雜湊法是一種高效的數據結構和算法，廣泛應用於需要快速查找的場景。通過選擇合適的雜湊函數和衝突處理方法，可以大大提高操作的效率。然而，為了保持高效，通常需要合理設計雜湊表的大小和負載因子，以避免性能下降。

SHA-256（Secure Hash Algorithm 256-bit）是一種加密雜湊函數，屬於SHA-2（Secure Hash Algorithm 2）家族。它是用來生成固定長度的256位元（32字節）雜湊值，並且是加密領域中廣泛應用的雜湊算法之一。SHA-256被設計為加密安全，且不可逆，即無法從輸出的雜湊值反推出原始數據。它常用於數位簽名、資料完整性驗證以及區塊鏈技術中。

1. SHA-256 的基本原理#

SHA-256 接受任意長度的輸入，並將其映射到一個256位的雜湊值。這個雜湊值是固定長度的，無論輸入數據的大小如何。它的運作過程通常包括以下步驟：

  1. 填充（Padding）： 由於SHA-256要求輸入長度為448模512，即長度必須是512的倍數減去64位。當輸入數據長度不足時，會在數據末尾填充1，然後再填充若干個0，直到長度達到該要求。最後，將原數據長度（64位）附加到數據末尾。

  2. 分塊處理（Message Scheduling）： 將填充後的數據分為若干個512位的塊。對每一塊數據進行處理，產生一組預處理的變量。

  3. 初始化哈希值： SHA-256使用8個32位的初始哈希值（H0, H1, ..., H7），這些值是從固定的常數中獲得的。

  4. 主循環（Main Loop）： 在每一個512位的塊中，SHA-256會進行64輪的哈希運算。每一輪會使用一個常數Kt，並且會根據數據和前一輪的哈希值進行運算，更新哈希狀態。

  5. 最終哈希值（Final Hash）： 經過所有塊的運算後，將得到256位的最終雜湊值，這就是SHA-256的輸出。

2. SHA-256的應用#

SHA-256主要用於以下幾個領域：

  1. 數位簽名與消息認證： 使用SHA-256生成消息的雜湊值，再利用私鑰對該雜湊值進行加密，從而實現數位簽名和消息的完整性驗證。

  2. 區塊鏈技術： SHA-256是比特幣等區塊鏈技術中不可或缺的一部分，主要用於生成區塊的哈希值以及工作量證明（Proof of Work）算法。

  3. 資料完整性檢查： 當文件或數據傳輸時，可以用SHA-256生成校驗和，接收方可以重新計算並驗證其完整性，確保數據未被篡改。

  4. 密碼學安全： 由於其單向性質，SHA-256常用於密碼學中生成密鑰或密碼的雜湊值，這些雜湊值可用於認證和密碼保護。

3. SHA-256 的特性#

  • 不可逆：從SHA-256的雜湊值無法推算出原始輸入數據。
  • 固定輸出：無論輸入數據大小，SHA-256的輸出始終是256位（32字節）。
  • 抗碰撞性：在計算上難以找到兩個不同的輸入數據，它們的SHA-256雜湊值相同。
  • 雪崩效應：即使輸入數據有微小變化，SHA-256的輸出也會大幅改變，這使得其適用於保證數據完整性。

4. Python 中使用 SHA-256#

在Python中，使用hashlib模塊可以方便地實現SHA-256雜湊計算。以下是一個使用Python計算SHA-256雜湊值的範例：

import hashlib

# 要雜湊的數據
data = "Hello, World!".encode('utf-8')

# 計算SHA-256雜湊值
sha256_hash = hashlib.sha256(data)

# 輸出SHA-256雜湊值（以十六進制表示）
print(sha256_hash.hexdigest())

輸出： 

a591a6d40bf420404a011733cfb7b190d62c65bf0bcdaee3d5a6e32e039f86bf

在這個例子中，我們將字符串 "Hello, World!" 轉換為字節類型，然後使用 hashlib.sha256() 計算其SHA-256雜湊值，最後使用 hexdigest() 方法將其輸出為十六進制字符串。

5. 小結#

SHA-256是一個非常強大的加密雜湊算法，廣泛應用於數位簽名、區塊鏈和資料完整性檢查等領域。由於其單向性和抗碰撞性，它在許多需要保證安全性的場合都被使用。了解其工作原理及特性對於加密學和數據安全領域的應用至關重要。