Hash(哈希、雜湊)

哈希表(Hash Table)

哈希也稱雜湊，是一種 基於Key-Value（鍵值對） 的數據結構，通過哈希函數（Hash Function）將鍵映射到特定的存儲位置，以實現高效的數據查找、插入和刪除。

為了讓文章好閱讀後續都已Hash來呈現，中文太多意思怕混亂。

在現實生活中舉例就像英文與中文對應關係。

轉換成程式的話就會像這樣，有key與value對應關係，因此也稱為Hash Table(哈希表)。

在查詢時只需要輸入key就能找到對應的value，例如轉換成python dict就會是

language_mapping = {'cat' '貓','dog':'狗','fish':'魚'}

Hash Function

又稱雜湊演算法。Hash function將資訊透過演算法重新建立一個Hash codes(雜湊值），而hash code主要目的是:

• 快速查找

  例子:在 Python 的 dict 或 set，哈希函數可幫助快速查找數據。

• 資料驗證與完整性

  例子:有些下載軟體會提供Checksum，確保檔案完整性與未被篡改改驗證。

• 加密保護

  例子: 密碼不是以明碼保存，而是透過算法重新建立一Hash codes，即使洩漏攻擊者難以推出名碼。

• 避免數據重複

  例子:Git會透過演算法確認檔案內容是否變更，避免重複儲存資料。

python提供了hashlib 標準庫中的一個模組，提供了各種常用的加密Hash演算法，常用於生成數據的Hash value。

可以使用 hashlib.algorithms_guaranteed 查看當前可用的哈希演算法。常見的包括：

• md5()
• sha1()
• sha224()
• sha256()
• sha384()
• sha512()

例子

透過sha256建立Hash

import hashlib

data = "hello, world"
sha256_hash = hashlib.sha256(data.encode()).hexdigest()
print(f"SHA-256 Hash: {sha256_hash}")

為了更了解意思這邊建立一個Hash Table，以及Hash Function實作簡單Hash演算法，例子如下

建立動物的中英文Hash Table，Hash Function為單字所有 code加總取餘數，最終儲存至List中。

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key: str) -> int:
        """將Key所有英文字母加總在回傳餘數"""
        return sum(ord(char) for char in key) % self.size

    def insert(self, key: str, value: str):
        index = self.hash_function(key)
        self.table[index] = value

    def get(self, key: str):
        index = self.hash_function(key)
        return self.table[index]

hash_table = SimpleHashTable()

hash_table.insert("cat", "貓")
hash_table.insert("dog", "狗")
hash_table.insert("fish", "魚")
hash_table.insert("bat", "蝙蝠")
print(hash_table.table)
print(hash_table.get("cat")) 
print(hash_table.get("dog")) 
print(hash_table.get("fish"))  
print(hash_table.get("bat")) 

因此如果沒有衝突查詢的時間複雜度為O(1)，那這是一個可用的Hash Table與可靠的Hash演算法嗎? 恐怕不是，因為演算法沒有解決Hash Collision問題 。

Hash Collision

如字面上就是碰撞，碰撞是指算法中的結果是有機會出現重複，繼續以上面例子舉例，如果我們再新增一個動物，然後在取值會如何呢?

hash_table.insert("camel", "駱駝")

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key: str) -> int:
        """將Key所有英文字母加總在回傳餘數"""
        return sum(ord(char) for char in key) % self.size

    def insert(self, key: str, value: str):
        index = self.hash_function(key)
        self.table[index] = value

    def get(self, key: str):
        index = self.hash_function(key)
        return self.table[index]

hash_table = SimpleHashTable()

hash_table.insert("cat", "貓")
hash_table.insert("dog", "狗")
hash_table.insert("fish", "魚")
hash_table.insert("bat", "蝙蝠")
hash_table.insert("camel", "駱駝")
print(hash_table.table)
print(hash_table.get("cat"))
print(hash_table.get("dog"))
print(hash_table.get("fish"))
print(hash_table.get("bat"))
print(hash_table.get("camel"))

會發現，狗查詢最終得到駱駝，這是因為取餘數本身就容易引起碰撞，這就是所謂的Hash Collision，那要如何解決呢?

Linked List(鏈結法)

利用Linked List資料結構特性，如果有資料則接著已存在資料後的Node，以例子狗已存在在Index 4那就接再dog後面Node，因此在碰撞產生時，時間複雜度為O(n)，最好情況為下一個的話那複雜度為O(1)。

class Node:
    def __init__(self, key: str, value: str):
        self.key = key
        self.value = value
        self.next = None

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key: str) -> int:
        """將Key所有英文字母加總後回傳餘數"""
        return sum(ord(char) for char in key) % self.size

    def insert(self, key: str, value: str):
        index = self.hash_function(key)
        new_node = Node(key, value)

        if self.table[index] is None:
            self.table[index] = new_node
        else:
            current_node = self.table[index]
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node

    def get(self, key: str):
        index = self.hash_function(key)
        current_node = self.table[index]

        while current_node:
            if current_node.key == key:
                return current_node.value
            current_node = current_node.next
        return None

    def print_table(self):
        for i, node in enumerate(self.table):
            if node:
                print(f"Index {i}: ", end="")
                current_node = node
                while current_node:
                    print(f"({current_node.key}: {current_node.value})", end=" -> ")
                    current_node = current_node.next
                print("None")
            else:
                print(f"Index {i}: None")

hash_table = SimpleHashTable()

hash_table.insert("cat", "貓")
hash_table.insert("dog", "狗")
hash_table.insert("fish", "魚")
hash_table.insert("bat", "蝙蝠")
hash_table.insert("camel", "駱駝")

hash_table.print_table()

print(hash_table.get("cat"))
print(hash_table.get("dog"))
print(hash_table.get("fish"))
print(hash_table.get("bat"))
print(hash_table.get("camel"))

在搜尋時，先找出Index，接著比對node key是否符合，如果不是就一直持續迴圈。

while current_node:
    if current_node.key == key:
        return current_node.value
    current_node = current_node.next

Open addressing(開放定址法)

思路很簡單，當找到狗時往下尋找空的位置，而複雜度與Linked List一樣，時間複雜度為O(n)，最好情況為下一個的話那複雜度為O(1)。

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key: str) -> int:
        return sum(ord(char) for char in key) % self.size

    def insert(self, key: str, value: str):
        index = self.hash_function(key)

        original_index = index
        while self.table[index] is not None:
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")

        self.table[index] = value

    def get(self, key: str):
        index = self.hash_function(key)

        original_index = index
        while self.table[index] is not None:
            if self.table[index] == key:
                return self.table[index]
            index = (index + 1) % self.size
            if index == original_index:
                return None
        return None

    def print_table(self):
        for i, value in enumerate(self.table):
            if value:
                print(f"Index {i}: {value}")
            else:
                print(f"Index {i}: None")

hash_table = SimpleHashTable()

hash_table.insert("cat", "貓")
hash_table.insert("dog", "狗")
hash_table.insert("fish", "魚")
hash_table.insert("bat", "蝙蝠")
hash_table.insert("camel", "駱駝")

hash_table.print_table()

print(hash_table.get("cat"))
print(hash_table.get("dog"))
print(hash_table.get("fish"))
print(hash_table.get("bat"))
print(hash_table.get("camel"))

以上提了兩種解決Hash Collision的方法，當然如果Hash Table太小就會常發生Hash Collision，這兩種方法都要做線性搜尋，但如果Hash Table太大時又會造成記憶體的浪費，因此Hash Table有個著名的評估公式來Load Factor調整。

Load Factor(負載係數)

前者提到有時Hash Table一直發生Hash Collision就得做線性搜尋效率會降低，如果擴大Hash Table又會浪費記憶體空間，因此有個公式可以來做判斷，一般建議當負載係數超過 0.7 時可以考慮擴大Hash Table，如果低於0.2可以考慮縮小Hash Table。

公式

$\text{負載係數} = \frac{\text{已使用的元素}}{\text{哈希表的總大小}}$

例子

以期面所舉例的Hash Table

• Hash Table總數（size） = 10
• 已使用的元素 = 4 (1、2、4、6)

Load Factor為 0.4，好的Hash Table均勻散布，爛的Hash Table常發生Hash Collision，這時就要考慮是否調整Hash Table以及演算法。

Hash Table時間複雜度彙整

Hash Table 操作的時間複雜度表格：

因此在不太會發生Collision的情況下，使用Hash Table可以達到高效處理。

Hash應用-雲端處理上傳圖片

在許多應用中，尤其是需要處理大量檔案上傳的場景中，圖片檔名的管理至關重要。若檔名沒有適當管理，容易出現檔案名稱衝突、隱私洩漏等問題。為了避免這些問題，我們可以使用哈希值來重新命名圖片檔案，並將其儲存至 Amazon S3。

import hashlib
import boto3
from pathlib import Path

s3 = boto3.client('s3')

def generate_hash(filename: str) -> str:
    """使用哈希函數生成文件的哈希值作為新檔名"""
    hash_object = hashlib.sha256(filename.encode())
    return hash_object.hexdigest()

def upload_image_to_s3(image_path: str, bucket_name: str):
    """將圖片上傳至 S3 並使用哈希值作為檔名"""
    image = Path(image_path)

    hashed_filename = generate_hash(image.name)

    with open(image_path, 'rb') as file:
        s3.upload_fileobj(file, bucket_name, hashed_filename)

    print(f"圖片已上傳，並使用哈希命名：{hashed_filename}")

upload_image_to_s3('path/to/your/image.jpg', 'your-s3-bucket-name')

使用Hash當圖片檔名好處有:

• 避免檔名衝突

  如果用用戶檔名儲存那肯定會遇到衝突，像是上傳圖片為image.png之類的，如果使用Hash不重複特性就能避免這種事情。

• 保護隱私與安全

  用戶上傳圖片檔名通常是用用戶設置的，像是上傳圖片如: maidcafe.png，直接看檔名就知道這是一個去女僕咖啡廳的圖片，如果加上Hash就可以保護隱私看檔名連結不出照片內容。

• 提高存儲效率

  因為Hash時間複雜度為O(1)，因此在操作是高效的。

• 確保資料一致性

  Hash因為不重複，所以就能保證內容不變性，就能比對圖片沒有被篡改或插入惡意隱碼。

Hash為何會在資安應用?

Hash在資安尤其是加密這一塊運用非常常見，因為他有著不可逆的特性與對稱加密不同，因此取得 value幾乎很難回推，因此應用上可以看到Checksum驗證和密碼儲存，但也不是說Hash就一定安全，像是密碼強度太弱一樣可以用暴力破解以及彩虹表，以前在做研究時曾經針對大學宿舍做暴力破解，基本上1050Ti的算力針對密碼強度過低20分鐘內就可破解，改天有空再針對資安寫一篇文章。

總結

總結來說，哈希資料結構是一個高效的工具，能夠加速數據存儲與檢索。雖然面臨碰撞問題，但通過合理的解決方法（如鏈結法和開放定址法），可以有效提高其性能。了解如何選擇合適的哈希函數及調整哈希表大小，是確保其效能的關鍵。掌握哈希資料結構對於編程和資料處理至關重要，尤其在處理大規模數據時，能顯著提高效率。