6.5.散列

在前面的部分中，我們可以利用關于元素在集合中存儲位置的信息來改進搜索算法。例如，通過知道一個列表是有序的，我們可以使用二分搜索在對數時間內進行搜索。在本節中，我們將嘗試進一步構建一個可以在O(1)時間內進行搜索的數據結構。這個概念被稱為散列。

為了做到這一點，當我們在集合中尋找它們時，我們將需要知道更多關于這些元素可能在哪里的信息。如果每個元素都在應該的位置，那么搜索可以使用單個比較來發現元素的存在。然而，我們將看到，通常情況并非如此。

哈希表是一組元素的集合，這些項的存儲方式使以后很容易找到它們。哈希表的每個位置（通常稱為槽）可以容納一個元素，并由從0開始的整數值命名。例如，我們將有一個名為0的插槽，一個名為1的插槽，一個名為2的插槽，依此類推。最初，哈希表不包含任何項，因此每個槽都是空的。我們可以使用一個列表來實現哈希表，每個元素都初始化為特殊的Python值None。圖4顯示了一個大小為\（m=11\）的哈希表。換句話說，表中有m個插槽，名為0到10。

哈希表中該元素所屬的槽之間的映射稱為哈希函數。哈希函數將接受集合中的任何項，并返回槽名稱范圍內的整數，介于0和m-1之間。假設我們有一組整數項54、26、93、17、77和31。我們的第一個散列函數，有時被稱為“remainder method”，它只接受一個元素并除以表大小，返回余數作為其哈希值（h（item）=item%11）。表4給出了示例項的所有哈希值。注意，這個余數方法（模算術）通常以某種形式出現在所有散列函數中，因為結果必須在槽名稱的范圍內。

Table 4: Simple Hash Function Using Remainders

Item

Hash Value

54	10
26	4
93	5
17	6
77	0
31	9

一旦計算出哈希值，我們就可以將每個元素插入到哈希表中指定的位置，如圖5所示。請注意，11個插槽中的6個現在已被占用。這被稱為荷載系數，通常表示為$\lambda =\frac{numberofitems}{tablesize}$，對于這個例子，$\lambda =\frac{6}{11}$。

Figure 5: Hash Table with Six Items

現在，當我們想要搜索一個條目時，我們只需使用hash函數來計算該條目的槽名，然后檢查哈希表以查看它是否存在。這個搜索操作是O(1)，因為計算哈希值并在該位置索引哈希表需要一定的時間量。如果一切都在它應該在的地方，我們已經找到了一個固定時間搜索算法。

您可能已經看到，只有當每個項映射到哈希表中的一個唯一位置時，這種技術才有效。例如，如果元素44是我們集合中的下一個元素，它的哈希值將為0（44%11==0）。因為77的散列值也是0，我們就有問題了。根據hash函數，兩個或多個項需要在同一個槽中。這被稱為哈希碰撞。顯然，碰撞會給哈希技術帶來問題。我們稍后會詳細討論。

6.5.1.哈希函數

給定一組元素，將每個元素映射到唯一槽的哈希函數稱為完美哈希函數。如果我們知道元素和集合永遠不會改變，那么就可以構造一個完美的哈希函數（有關完美哈希函數的更多信息，請參閱練習）。不幸的是，給定一個任意的元素集合，沒有系統的方法來構造一個完美的散列函數。幸運的是，我們不需要哈希函數是完美的，仍然可以獲得性能效率。

始終擁有一個完美的哈希函數的一種方法是增加哈希表的大小，以便可以容納項范圍中的每個可能值。這保證每個項目都有一個唯一的槽。雖然這對于數量較少的項目是可行的，但是當可能的項目數量很大時，這是不可行的。例如，如果項目是9位數的社會保障號碼，這種方法將需要近10億個插槽。如果我們只想為一個25人的班級存儲數據，我們將浪費大量的內存。

我們的目標是創建一個哈希函數，該函數將沖突數量最小化，易于計算，并且在哈希表中均勻地分布項目。有許多常用的方法來擴展簡單余數方法。我們將在這里考慮其中一些。

構造散列函數的折疊方法首先將元素分成大小相等的部分（最后一部分可能大小不同）。然后將這些片段相加，得到結果散列值。例如，如果我們的項目是電話號碼436-555-4601，我們會將數字分成2組（43,65,55,46,01）。加上43+65+55+46+01，得到210。如果我們假設哈希表有11個槽，那么我們需要執行除以11并保留剩余部分的額外步驟。在本例中，210%11是1，因此電話號碼436-555-4601哈希到插槽1。有些折疊方法更進一步，在添加之前每隔一片反轉一次。對于上面的例子，我們得到了43+56+55+64+01=219，其中219%11=10。

另一種構造散列函數的數值技術稱為中央平方法。我們首先將元素平方，然后提取得到的數字的一部分。例如，如果項目是44，我們將首先計算44²=1936。通過提取中間兩位數93，并執行余數步驟，我們得到5（93%11）。表5顯示了余數法和中平方法下的項目。您應該確認您了解這些值是如何計算的。

Table 5: Comparison of Remainder and Mid-Square Methods?

Item

Remainder

Mid-Square

54	10	3
26	4	7
93	5	9
17	6	8
77	0	4
31	9	6

我們還可以為基于字符的元素（如字符串）創建哈希函數。“cat”這個詞可以看作是一系列序數值。

>>> ord('c') 99 >>> ord('a') 97 >>> ord('t') 116

然后，我們可以取這三個序數值，將它們相加，然后使用remainder方法得到一個散列值（參見圖6）。Listing 1顯示了一個名為hash的函數，它接受一個字符串和一個表大小，并返回0到tablesize-1范圍內的散列值。

Figure 6: Hashing a String Using Ordinal Values

Listing 1

def hash(astring, tablesize):sum = 0for pos in range(len(astring)):sum = sum + ord(astring[pos])return sum%tablesize

有趣的是，當使用這個散列函數時，anagrams將始終被賦予相同的散列值。為了彌補這個問題，我們可以使用角色的位置作為權重。圖7顯示了使用位置值作為權重因子的一種可能方法。對散列函數的修改作為練習。

Figure 7: Hashing a String Using Ordinal Values with Weighting

您可能可以想出許多其他方法來計算集合中遠古三的哈希值。重要的是要記住哈希函數必須是高效的，這樣它就不會成為存儲和搜索過程的主要部分。如果哈希函數太復雜，那么計算槽名的工作量就要比前面描述的簡單地進行基本的順序或二分搜索要多。這將很快破壞散列的目的。

6.5.2.碰撞解決

現在我們回到碰撞問題。當兩個項目哈希到同一個槽時，我們必須有一個系統的方法將第二個項目放入哈希表中。這個過程稱為碰撞解決。如前所述，如果哈希函數是完美的，則不會發生沖突。然而，由于這通常是不可能的，沖突解決成為哈希的一個非常重要的部分。

一種解決沖突的方法查看哈希表，并嘗試找到另一個打開的槽來保存導致沖突的項。一種簡單的方法是從原始哈希值位置開始，然后按順序在插槽中移動，直到遇到第一個空的插槽。注意，我們可能需要回到第一個槽（循環）來覆蓋整個哈希表。這個沖突解決過程被稱為開放尋址，因為它嘗試在哈希表中查找下一個打開的插槽或地址。通過一次一個地系統地訪問每個插槽，我們正在執行一種稱為線性探測的開放尋址技術。

圖8顯示了簡單余數方法散列函數（54,26,93,17,77,31,44,55,20）下整數項的擴展集。上面的表4顯示了原始項的哈希值。圖5顯示了原始內容。當我們試圖將44放入插槽0時，會發生碰撞。在線性探測下，我們按順序逐槽查找，直到找到一個打開的位置。在本例中，我們找到插槽1。

同樣，55應該進入插槽0，但必須放在插槽2中，因為它是下一個打開的位置。最后一個值是20個哈希到槽9。由于插槽9已滿，我們開始進行線性探測。我們訪問插槽10、0、1和2，最后在位置3找到一個空插槽。

Figure 8: Collision Resolution with Linear Probing

一旦我們使用開放尋址和線性探測構建了一個哈希表，就必須使用相同的方法來搜索項。假設我們要查找93號條目。當我們計算散列值時，我們得到5。在第5槽中顯示93，我們可以返回True。如果我們要找20個呢？現在哈希值是9，槽位9當前保存31。我們不能簡單地返回False，因為我們知道可能有碰撞。我們現在被迫從第10位開始進行順序搜索，直到找到第20項或者找到一個空的插槽。

線性探測的一個缺點是傾向于聚集；項在表中變得聚集。這意味著，如果在同一哈希值下發生多個沖突，則線性探測分辨率將填充周圍的許多插槽。這將對正在插入的其他項產生影響，正如我們在嘗試添加上面的第20項時看到的那樣。必須跳過散列到0的值簇，才能最終找到打開的位置。這個集群如圖9所示。

Figure 9: A Cluster of Items for Slot 0

處理集群的一種方法是擴展線性探測技術，這樣我們就不用按順序查找下一個打開的插槽，而是跳過插槽，從而更均勻地分布導致沖突的項目。這可能會減少發生的群集。圖10顯示了使用“plus 3”探針進行沖突解決時的項目。這意味著一旦發生碰撞，我們將每隔三個槽查看一次，直到找到一個空槽為止。

Figure 10: Collision Resolution Using “Plus 3”

這個在碰撞后尋找另一個插槽的過程的通稱是重新散列。對于簡單的線性探測，rehash函數是newhashvalue=rehash（oldhashvalue），其中rehash（pos）=（pos+1）%sizeoftable。“plus 3”再哈希可以定義為rehash（pos）=（pos+3）%sizeoftable。通常，rehash（pos）=（pos+skip）% sizeoftable。需要注意的是，“跳過”的大小必須使表中的所有槽最終都被訪問。否則，該表的一部分將不被使用。為了確保這一點，通常建議表大小為質數。這就是我們在示例中使用11的原因。

線性探測思想的一種變體稱為二次探測。我們不使用常量“skip”值，而是使用一個rehash函數，該函數將哈希值遞增1、3、5、7、9，依此類推。這意味著，如果第一個散列值是h，則后續值為h+1、h+4、h+9、h+16，依此類推。一般來說，i將是i² rehash（pos）=（h+i²）。換句話說，二次探測使用由連續的完美正方形組成的跳躍。圖11顯示了使用此技術放置后的示例值。

Figure 11: Collision Resolution with Quadratic Probing

處理沖突問題的另一種方法是允許每個槽保存對項目集合（或鏈）的引用。鏈接允許許多元素存在于哈希表中的同一位置。當發生沖突時，該項仍然放在哈希表的適當槽中。隨著越來越多的項散列到同一位置，在集合中搜索該項的難度增加。圖12顯示了將這些項添加到哈希表中時的情況，該表使用鏈接來解決沖突。

Figure 12: Collision Resolution with Chaining

當我們要搜索一個項目時，我們使用哈希函數生成它應該駐留的槽。由于每個槽都包含一個集合，所以我們使用搜索技術來確定該項是否存在。這樣做的好處是，平均而言，每個槽中的項目可能會少很多，因此搜索效率可能會更高。我們將在本節末尾查看哈希分析。

6.5.3.實現Map抽象數據類型

最有用的Python集合之一是dictionary。回想一下，字典是一種關聯數據類型，您可以在其中存儲鍵-數據對。鍵用于查找關聯的數據值。我們經常把這個想法稱為map。

map抽象數據類型的定義如下。結構是鍵和數據值之間關聯的無序集合。映射中的鍵都是唯一的，因此鍵和值之間存在一對一的關系。操作如下所示。

• Map()創建一個新的空映射。它返回一個空的映射集合。
• put(key,val)向映射添加新的鍵值對。如果鍵已經在映射中，則用新值替換舊值。
• get(key)給定一個鍵，返回存儲在映射中的值，否則返回None。
• del使用del map[key]格式的語句從映射中刪除鍵值對。
• len()返回存儲在映射中的鍵值對的數目。
• in如果給定鍵在映射中，則返回True，否則返回False。

字典的最大好處之一是，給定一個鍵，我們可以很快地查找相關的數據值。為了提供這種快速查找功能，我們需要一個支持有效搜索的實現。我們可以使用帶有順序或二進制搜索的列表，但是使用如上所述的哈希表會更好，因為在哈希表中查找項可以達到O（1）的性能。

在Listing 2中，我們使用兩個列表來創建一個實現映射抽象數據類型的哈希表類。一個名為slots的列表將保存密鑰項，而名為data的并行列表將保存數據值。當我們查找一個鍵時，數據列表中相應的位置將保存相關的數據值。我們將使用前面介紹的思想將密鑰列表視為哈希表。注意，哈希表的初始大小被選擇為11。雖然這是任意的，但重要的是大小是一個素數，以便沖突解決算法可以盡可能有效。

Listing 2

class HashTable:def __init__(self):self.size = 11self.slots = [None] * self.sizeself.data = [None] * self.size

hashfunction實現了簡單的余數方法。碰撞解決技術是一種帶有“加1”重影函數的線性探測。put函數（見Listing 3）假設最終會有一個空槽，除非鍵已經存在于自身插槽. 它計算原始哈希值，如果該槽不為空，則迭代rehash函數，直到出現空槽為止。如果非空插槽已經包含密鑰，則舊數據值將替換為新數據值。處理沒有空位的情況是一種練習。

Listing 3

def put(self,key,data):hashvalue = self.hashfunction(key,len(self.slots))if self.slots[hashvalue] == None:self.slots[hashvalue] = keyself.data[hashvalue] = dataelse:if self.slots[hashvalue] == key:self.data[hashvalue] = data #replaceelse:nextslot = self.rehash(hashvalue,len(self.slots))while self.slots[nextslot] != None and \self.slots[nextslot] != key:nextslot = self.rehash(nextslot,len(self.slots))if self.slots[nextslot] == None:self.slots[nextslot]=keyself.data[nextslot]=dataelse:self.data[nextslot] = data #replacedef hashfunction(self,key,size):return key%sizedef rehash(self,oldhash,size):return (oldhash+1)%size

同樣，get函數（參見清單4）首先計算初始哈希值。如果該值不在初始槽中，則使用rehash來定位下一個可能的位置。注意，第15行通過檢查確保沒有返回到初始槽位來保證搜索將終止。如果發生這種情況，我們已經用盡了所有可能的插槽，并且該項目不能出現。

HashTable類的final方法提供了額外的字典功能。我們重載了__getitem__和__setitem__方法，以允許使用[]進行訪問。這意味著一旦創建了哈希表，熟悉的索引操作符就可以使用了。我們把剩下的方法留作練習。

def get(self,key):startslot = self.hashfunction(key,len(self.slots))data = Nonestop = Falsefound = Falseposition = startslotwhile self.slots[position] != None and \not found and not stop:if self.slots[position] == key:found = Truedata = self.data[position]else:position=self.rehash(position,len(self.slots))if position == startslot:stop = Truereturn datadef __getitem__(self,key):return self.get(key)def __setitem__(self,key,data):self.put(key,data)

下面的會話顯示HashTable類的實際操作。首先，我們將創建一個哈希表，并使用整數鍵和字符串數據值存儲一些項。

>>> H=HashTable() >>> H[54]="cat" >>> H[26]="dog" >>> H[93]="lion" >>> H[17]="tiger" >>> H[77]="bird" >>> H[31]="cow" >>> H[44]="goat" >>> H[55]="pig" >>> H[20]="chicken" >>> H.slots [77, 44, 55, 20, 26, 93, 17, None, None, 31, 54] >>> H.data ['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']

接下來我們將訪問和修改哈希表中的一些項。請注意，鍵20的值正在被替換。

>>> H[20] 'chicken' >>> H[17] 'tiger' >>> H[20]='duck' >>> H[20] 'duck' >>> H.data ['bird', 'goat', 'pig', 'duck', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat'] >> print(H[99]) None

完整的哈希表示例可以在ActiveCode 1中找到。

6.5.4.散列分析

我們在前面說過，在最好的情況下，散列將提供O（1）恒定時間搜索技術。然而，由于碰撞，比較的數量通常不是那么簡單。盡管對哈希的完整分析超出了本文的范圍，但我們可以聲明一些眾所周知的結果，這些結果近似于搜索一個項目所需的比較數量。

在分析哈希表的使用時，最重要的信息是負載因子λ。從概念上講，如果λ很小，那么發生碰撞的幾率就更低，這意味著項目更有可能位于它們所屬的插槽中。如果λ很大，意味著表已滿，則會有越來越多的碰撞。這意味著沖突解決更加困難，需要更多的比較才能找到空槽。使用鏈接，增加的碰撞意味著每個鏈上的項目數增加。

和以前一樣，我們會有一個成功和不成功的搜索結果。

總結

以上是生活随笔為你收集整理的6.5.散列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。