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