作者：周秉誼 / Tomofun 資深技術經理
Python的內建資料型別如dict和set的底層實作，依賴於hash()函式計算和雜湊表，使得dict和set資料型別能夠達到非常優異的存取效能。本文將針對Python中使到hash()函式的資料型別進行說明，並探討hash()函式的細節。
前言
在軟體開發中，資料結構的選擇和使用往往決定了程式效率的高低。Python作為一種通用型程式語言，提供了多種內建資料型別(Built-in Type)，讓開發者可以針對不同的應用場景靈活選擇合適的資料結構來處理和儲存資料。
在Python的內建資料型別中，有部分資料型別如字典(dict)和集合(set)的底層實作依賴於一個稱為hash()的函式。透過hash()函式，可以將不同的輸入值對應到唯一的數值，進而能夠將鍵值(Key)或元素(Element)對應到記憶體中特定的位置。這種將資料映射(Mapping)到獨特位址的手法，使得dict和set資料型別能夠達到非常優異的存取效能。
本文將針對Python中使到hash()函式的資料型別進行說明，並探討hash()函式的細節。
set資料型別
set型別是Python中的集合型別，是一種無序(unordered)的不重複元素集。概念和操作類似於數學上的集合概念，提供了豐富的操作，如聯集(Union)、交集(Intersection)、差集(Difference)以及對稱差集(Symmetric Difference)等。可以用於確認成員、去除重複元素、快取、資料過濾等等。在Python中的set物件在建構的時候，會建立一個雜湊表(hash table)用來儲存元素，要新增元素時就可透過hash()函式的使用，將每個元素對應到不同的數值，依這個雜湊值(hash value)存放在雜湊表中不同的位置。當hash()函式產生的雜湊值的品質夠好，就能夠無視set物件中的元素數量，在O(1)的時間複雜度內查找、新增或移除元素，因此Python中的set型別只能存放可雜湊(Hashable)的資料。但同一個set物件中是可以同時存放不同型別的資料或物件，只要這些物件是可雜湊的。
dict資料型別
dict型別是一種無序的鍵值對映集(Key-value mapping collection)，可以把不同的鍵值對應到相對的數值或物件。dict型別的原理和運作機制跟set型別非常相似，也使用了hash()函式和雜湊表等資料儲存方式，將鍵值對應到雜湊表中不同的位置，所以也能夠無視dict物件中的元素數量，在O(1)的時間複雜度內查找、新增或移除元素。因此鍵值也有可雜湊的限制，在使用時要特別注意，而另一方面，同一個dict物件中也能同時操作不同型別的鍵值。Python中的dict型別存取的效率非常好，存取效率接近可以隨機存取(Random access)的list型別，但又有set型別中常數時間(Constant time)查找、新增或移除元素的操作能力，因此用途非常廣泛，可說是Python中最好用的資料型別了。
Hashable可雜湊性
在Python語言中，可雜湊性代表著一個物件提供__hash__()成員函式(member function)且計算出來的雜湊值在其生命週期(lifetime)中永不改變，還有__eq__()成員函式可以跟其他物件進行比較，並使相等的物件會擁有相同的雜湊值。使用外層的hash()函式對物件計算雜湊值時，就會使用該物件的__hash__()成員函式取得雜湊值，在64位元(64 bits)的系統中，hash()函式會產出8位元組(8 bytes)的雜湊值。要特別注意的是，如果使用者自定義的類別預設是可雜湊的，如果該類別沒有提供__hash__()成員函式的話，將會使用id()函式的來計算雜湊值。
Python雜湊演算法
在Python中內建的雜湊值計算也經過了一些改良，在2013年的Python 3.4版之前，內建的雜湊函式是以Fowler–Noll–Vo雜湊函數的演算法來進行計算，這是一種非加密型雜湊函數，由Glenn Fowler、Landon Curt Noll和Kiem-Phong Vo在1991年共同創建。FNV是一個好的雜湊函數，但因為計算速度很快、對零值太過敏感、最右位元為輸入資料最右位元的XOR，所以不易抵擋Hash DoS攻擊，在有心人士的使用下可以產生很多雜湊碰撞(Hash collision)，使操作時間變為線性時間(linear time)，讓程式無法正常運作。因此在Python3.4之後轉為使用SipHash。
SipHash是由Jean-Philippe Aumasson和Daniel J. Bernstein在2012年創建的，基於add–rotate–xor (ARX)進行計算，可以把不同長度的訊息，轉化成64位元的數字，具有密碼學特性，但它速度很快且很小，即使對長度短的輸入也很有效率，其性能可與非加密雜湊函數如CityHash相媲美。SipHash的計算還包括了密鑰，可以更為有效地抵擋Hash DoS攻擊。
圖1. Python內建hash()函式資訊
圖2. hash()函式計算結果
結語
ldict和set是Python中常用的資料型別，是非常有效率的資料結構，它們的快速查找和檢索特性使它們成為解決各種問題的理想選擇。兩種資料型別都是透過利用hash()函函來達成高效能的儲存和查詢，理解hash()函式在它們內部實作中所扮演的關鍵角色，有助於我們正確使用這些資料結構。
參考資料
- https://peps.python.org/pep-0456/#siphash
- https://docs.python.org/3/reference/datamodel.html#object.__hash__
- https://docs.python.org/3/glossary.html#term-hashable