Python的字典映射使用什麼哈希算法？

我正在搞一個命令行解析器，想知道python dict使用什麼樣的哈希算法？Python的字典映射使用什麼哈希算法？

我設置它的方式，我有一個模式匹配算法，它將標記輸入序列與字典鍵相匹配。某些鍵相對較長（長度爲6或6個字符串的5或6個元組）。我想知道是否有一個長字典密鑰顯着降低密鑰檢索效率的問題。

2012-01-25 Joel Cornett

看看[Objects/dictnotes.txt]（http://hg.python.org/cpython/file/2.7/Objects/dictnotes.txt） – jfs

看看[這個問題]（http://stackoverflow.com/questions/ 2070276 /其中-可以-I-找到 - 源或算法-的-蟒散列函數）。它有一個指向[本頁]的鏈接（http://effbot.org/zone/python-hash.htm），它描述了Python如何散列一些不同的類型，它可能對你有幫助。 – srgerg

它使用的散列依賴於被用作鍵的對象 - 每個類都可以定義自己的__hash __（）方法，並且它爲特定實例返回的值是用於字典的值。

Python本身爲str和tuple類型提供散列實現。快速查看源代碼應該可以揭示這些算法的確切算法。

元組的散列基於其內容的散列。該算法本質上是這（簡體略）：

def hash(tuple): 
    mult = 1000003 
    x = 0x345678 
    for index, item in enumerate(tuple): 
     x = ((x^hash(item)) * mult) & (1<<32) 
     mult += (82520 + (len(tuple)-index)*2) 
    return x + 97531

對於字符串，解釋也超過每個字符迭代，他們用這個（再次聲明，略有簡化）算法相結合：

def hash(string): 
    x = string[0] << 7 
    for chr in string[1:]: 
     x = ((1000003 * x)^chr) & (1<<32) 
    return x

一個更大的問題擔心是避免哈希碰撞。碰撞散列鍵會導致線性搜索，因爲字典試圖找到一個地方來存儲新對象（這現在被認爲是一個安全問題，並且在即將到來的python版本中行爲可能會改變）

來源

2012-01-25 04:56:28

哦，好的。出於某種原因，我認爲Python只是對所有數據類型使用通用的字節碼散列算法。就碰撞哈希鍵而言，我不認爲這將是一個問題，因爲我將擁有的鍵的數量（相對）很小 - 可能是幾千個。請原諒我的沉默，但是如何將散列衝突和線性搜索變成安全問題？ –

@Joel Cornett：這是一個安全問題，因爲散列表使用存儲區來存儲密鑰，並且具有相同散列代碼的密鑰將被散列到同一個存儲區，強制散列表每次搜索時都執行線性搜索密鑰，如果密鑰的數量很大，這可能非常低效（甚至會導致拒絕服務）。如果程序遇到具有散列到相同散列碼的不同密鑰的散列表，則會導致拒絕服務攻擊。 –

如果攻擊者可以控制字典中使用的密鑰，那麼他們可能會插入數百或數千個衝突密鑰，從而使插入操作非常緩慢。在某些情況下，這可能會導致計算機無響應或數據庫變得無法使用 - Dos攻擊 –

Python的字典映射使用什麼哈希算法？

回答

相關問題