Python 雜湊(Hashing)詳解:新手指南

更新日期: 2024 年 10 月 3 日

在 Python 編程中,雜湊(Hashing) 是一種重要的概念,廣泛應用於字典(dict)和集合(set)等數據結構中。

理解雜湊的原理和在 Python 中的應用,對於提升程式效率和編寫高性能代碼至關重要。

這篇文章將帶您深入了解 Python 中的雜湊,包括其基本概念、hash() 函數的使用、可雜湊物件(Hashable Objects)、自定義類的雜湊方法,以及在實際開發中的應用和注意事項,幫助新手更好地掌握這一重要主題。


什麼是雜湊?

定義

雜湊(Hashing) 是一種將數據映射為固定大小的值(稱為雜湊值或雜湊碼)的技術。

這些值通常是整數,用於快速查找和存儲數據。

特點

  • 快速查找:通過雜湊值,可以在常數時間內(O(1))檢索數據。
  • 固定大小輸出:無論輸入數據的大小如何,雜湊函數都會生成固定大小的輸出。
  • 不可逆:從雜湊值無法還原原始數據。

雜湊函數的性質

  • 確定性:相同的輸入必須產生相同的輸出。
  • 均勻性:輸出值應該均勻地分佈在輸出範圍內,避免「碰撞」(不同的輸入產生相同的輸出)。

Python 中的 hash() 函數

定義

Python 提供了一個內建函數 hash(),用於返回物件的雜湊值。

這個值是一個整數,用於快速比較字典的鍵和集合中的成員。

語法

hash(object)
  • object:要計算雜湊值的物件。

示例

print(hash(42))          # 整數
print(hash('hello'))     # 字串
print(hash((1, 2, 3)))   # 元組

輸出(可能因環境而異):

42
-6918205338853914552
529344067295497451

解釋:

  • hash() 函數對於可雜湊物件返回一個整數雜湊值。
  • 相同的輸入在同一次程序運行中會返回相同的雜湊值。

注意事項

  • 不可雜湊物件:如列表、字典等不可雜湊,因為它們是可變的。
  hash([1, 2, 3])  
  # TypeError: unhashable type: 'list'

可雜湊物件與不可雜湊物件

可雜湊物件(Hashable Objects)

  • 定義:具有固定雜湊值,並且在其生命週期中不可改變。
  • 常見的可雜湊物件
  • 不可變類型:如整數、浮點數、字串、元組(內部元素也必須是可雜湊的)、凍結集合(frozenset)等。

不可雜湊物件(Unhashable Objects)

  • 定義:無法計算固定的雜湊值,因為物件是可變的。
  • 常見的不可雜湊物件
  • 可變類型:如列表、字典、集合等。

為什麼不可變類型是可雜湊的?

  • 原因:不可變物件的內容在創建後不能改變,因此其雜湊值保持不變,可用作字典的鍵或集合的成員。

字典和集合中的雜湊應用

字典中的雜湊

  • 字典鍵的要求:必須是可雜湊的物件,因為字典使用雜湊表實現,通過鍵的雜湊值快速查找對應的值。

示例:

my_dict = {1: 'one', 'two': 2, (3, 4): 'three and four'}
  • 有效的鍵:整數、字串、元組。
  • 無效的鍵
  my_dict = {[1, 2]: 'list'}  # TypeError: unhashable type: 'list'

集合中的雜湊

  • 集合元素的要求:集合中的元素必須是可雜湊的,因為集合使用雜湊表來實現元素的快速查找和去重。

示例:

my_set = {1, 'two', (3, 4)}
  • 無效的元素
  my_set = {[1, 2], 3}  # TypeError: unhashable type: 'list'

雜湊的實際應用示例

去除列表中的重複元素

示例:

numbers = [1, 2, 2, 3, 4, 4, 5]
unique_numbers = list(set(numbers))
print(unique_numbers)  # 輸出:[1, 2, 3, 4, 5]

解釋:

  • 使用集合自動去除重複的元素,集合中的元素必須是可雜湊的。

檢查兩個物件是否相同

示例:

a = 'hello'
b = 'hello'
print(a == b)          # 輸出:True
print(hash(a) == hash(b))  # 輸出:True

解釋:

  • 由於字串是可雜湊的,不僅值相等,雜湊值也相等。

結論

  • 雜湊(Hashing) 是 Python 中實現高效數據查找和存儲的重要技術,廣泛應用於字典和集合等數據結構。
  • 可雜湊物件:不可變類型,如整數、字串、元組等,可以計算雜湊值,可用作字典的鍵或集合的成員。
  • 注意事項:確保物件的不可變性和方法的一致性,避免因雜湊值不穩定導致的問題。

延伸閱讀

Similar Posts