Python字典哈希查找如何工作？

Python字典查找算法如何在內部工作？Python字典哈希查找如何工作？

mydi['foo']

如果詞典有1,000,000個詞，是否執行樹搜索？根據關鍵字符串的長度或字典的大小，我會期望性能嗎？也許把所有內容填充到字典中與爲500萬字符串編寫樹搜索索引一樣好？

來源

2011-07-07 shigeta

雖然我可以看到python字典如何工作，如下所述，散列通常比這更豐富。可以想象，這個簡單的查找將花費很長時間，一個大字典。 Perl散列使用一個基本上是索引的系統，通過將密鑰的每個字符散列元素進行池化。 – shigeta

請參閱http://www.perl.com/pub/2002/10/01/hashes.html – shigeta

下面是一些僞代碼更接近實際發生的情況。想象一下，字典中有一個data屬性，其中包含鍵值對和size這是分配的單元數。

def lookup(d, key): 
    perturb = j = hash(key) 
    while True: 
     cell = d.data[j % d.size] 
     if cell.key is EMPTY: 
      raise IndexError 
     if cell.key is not DELETED and (cell.key is key or cell.key == key): 
      return cell.value 
     j = (5 * j) + 1 + perturb 
     perturb >>= PERTURB

的perturb值確保解決散列衝突時的哈希碼的所有位被最終用於但一旦它已經劣化到0 (5*j)+1最終將觸摸的所有單元在表格中。

size總是比實際使用的單元格數量大得多，所以當密鑰不存在（並且通常應該很快地命中一個）時，散列可以保證最終擊中空單元格。還有一個鍵的刪除值，用於指示不應該終止搜索但目前未使用的單元格。

至於你關於密鑰字符串長度的問題，散列字符串將查看字符串中的所有字符，但字符串也有一個字段用於存儲計算出來的散列。因此，如果每次使用不同的字符串進行查找時，字符串長度可能有方向性，但是如果您有一組固定的密鑰並重復使用相同的字符串，則哈希將在第一次使用後不會重新計算。由於大多數名稱查找涉及字典，並且每個變量或屬性名稱的單個副本都存儲在內部，因此Python可以從中受益，因此每次訪問屬性x.y時都會有字典查找，但不是對哈希函數的調用。

來源

2011-07-07 07:39:34 Duncan

我給你的複選標記是最直接的答案，而不是鏈接，即使每個人都基本上說了同樣的事情。 – shigeta

正如您在標題中提到的，字典是散列表。不使用樹搜索。不管字典的大小如何，查找關鍵字都是一個幾乎不變的時間操作。

您可能會發現這個問題的答案有幫助：How are Python's Built In Dictionaries Implemented

來源

2011-07-07 02:47:28

+1，但不是說「幾乎不變」，爲什麼不「攤銷常量」呢？最壞的情況時間是不變的？ –

@尼爾它是最糟糕的情況下線性時間，如果你得到一組輸入，以某種方式與每一個單一的輸入衝突。然而，即使是對手也無法這樣做，因爲通用哈希解決了這個問題。 – bdares

「幾乎不變」是「攤銷常數」的英語！ :) –

哈希查找不使用樹木。他們使用一個哈希表，他們需要不斷的查找時間。他們將會佔用更多的空間（平均而言我相信是樹的兩倍），但查找和插入時間都是贏的。

過於簡單化，把你的密鑰的MD5和國防部與你有地址的數量，而這也正是您保存或查找檢索鍵。無論這個集合有多大都沒關係，只要你沒有顯着的碰撞，它總是會花費相同的時間，這是一個好的散列可以避免的。

來源

2011-07-07 02:47:57 bdares

我想這對於理智的字典大小來說更簡單。我想我會建立我自己的樹搜索...畢竟，如果是這種情況，對照哈希查找可能會使我看起來不錯。 – shigeta

@shigeta你真正的問題似乎是你試圖使用內存空間數據結構實現某些可能不適合內存的東西。我建議你使用DBMS。 – bdares

@shigeta：你爲什麼要建立自己的樹搜索？你似乎暗示你的樹會比字典快，但這不太可能。即使使用5Mb字符串，每個字符串也只被散列一次。 –

這裏有一個很好的解釋：從上面的鏈接http://wiki.python.org/moin/DictionaryKeys

僞代碼：

def lookup(d, key): 
    '''dictionary lookup is done in three steps: 
     1. A hash value of the key is computed using a hash function. 

     2. The hash value addresses a location in d.data which is 
      supposed to be an array of "buckets" or "collision lists" 
      which contain the (key,value) pairs. 

     3. The collision list addressed by the hash value is searched 
      sequentially until a pair is found with pair[0] == key. The 
      return value of the lookup is then pair[1]. 
    ''' 
    h = hash(key)     # step 1 
    cl = d.data[h]     # step 2 
    for pair in cl:    # step 3 
     if key == pair[0]: 
      return pair[1] 
    else: 
     raise KeyError, "Key %s not found." % key

來源

2011-07-07 02:48:10 Acorn

看起來像很多工作，但對於大多數應用程序來說它似乎足夠好。這些鍵並不是真正的排序，就像你可能想從一個排序後的索引那樣排序。謝謝這是一個有用的。 – shigeta

請注意，此Python代碼不會像Python字典一樣處理衝突。哈希表實現可以在處理碰撞的方式上有所不同。 –

答1：不，樹形檢索：內部工作在這個video

答案2解釋如果在字典中有一百萬條記錄，則不會完成。

答3：因爲可能有關鍵的碰撞，你會期望在字典的大小方面的性能，而不是在鑰匙串的長度方面。

回答4：考慮字典作爲數組（連續的存儲單元），但有可能是未使用的陣列內的塊。因此，與樹相比，字典傾向於浪費大量的內存空間。但是，爲了獲得更好的運行時性能，詞典可能比樹更好。關鍵衝突有時會降低性能。你應該閱讀一致的散列。

來源

2011-07-07 06:07:18 ajmartin

Python字典哈希查找如何工作？

回答

相關問題