處理哈希衝突

我有一堆在Python字典的，每片含詞典的用戶信息例如：處理哈希衝突

NewUserDict={'name': 'John', 'age':27}

我收集較大的字典容器之內的所有這些用戶信息的詞典，使用的哈希值每個字典作爲密鑰（Hashing a dictionary?）。

將新的唯一用戶添加到字典時，處理散列衝突的最佳方法是什麼？我要手動的字典與碰撞的散列值進行比較，並且只需添加一些隨機數到最近的哈希值，例如：

if new_hash in larger_dictionary: 
    if larger_dictionary[new_hash] != NewUserDict: 
     new_hash = new_hash + somerandomnumber

什麼是處理這個標準呢？另外，我怎麼知道我是否應該首先擔心碰撞？使用

來源

2017-02-07 wenhoo

咦？你是否正在實施哈希映射？ –

通常，您將使用用戶記錄中最獨特的元素。這通常意味着系統通常具有每個記錄（用戶）的用戶名或唯一ID，這保證是唯一的。用戶名或ID將成爲記錄的唯一密鑰。由於這是由系統本身強制執行的，例如通過數據庫表中的自動增量鍵，所以可以確定沒有衝突。因此

獨特的關鍵應該是在地圖的關鍵，讓你找到用戶的記錄。但是，如果由於某些原因，您無法訪問這樣一個唯一的保證密鑰，那麼您肯定可以根據記錄創建一個哈希（如您所描述的），並使用任意數量的散列表算法來存儲可能具有衝突鍵的元素。在這種情況下，你不會避免碰撞，但你只需處理它。

一個快速和常用的算法是這樣的：在記錄上使用散列來創建一個鍵，就像你已經做的那樣。此密鑰可能不是唯一的。現在在密鑰指示的位置存儲記錄列表。我們稱之爲「桶」。要存儲新元素，請對其進行散列，然後將其附加到存儲在該位置的列表（將其添加到存儲區）。要查找元素，請對其進行哈希處理，找到該條目，然後依次搜索該位置處的列表/存儲桶以查找所需的條目。

下面是一個例子：

mymap[123] = [ {'name':'John','age':27}, {'name':'Bob','age':19} ] 
mymap[678] = [ {'name':'Frank','age':29} ]

在這個例子中，你有你的哈希表（通過字典來實現）。您有散列鍵值678，其中一個條目存儲在存儲區中。然後你有散列鍵值123，但是有衝突：'John'和'Bob'條目都有這個散列值。無論如何，你會發現存儲在mymap [123]中的bucket並遍歷它來查找值。

這是一個靈活且非常常見的哈希映射實現，它不需要重新分配或其他複雜操作。它在很多地方都有描述，例如：https://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html（在第8.3.1章）。

當您發生大量衝突時（每個桶的列表變得非常長時），性能通常只會成爲問題。用一個好的散列函數可以避免某些事情。

但是：例如，數據庫強制執行的記錄的真正唯一ID可能仍然是首選方法。

來源

2017-02-08 00:15:40 jbrendel

關於唯一用戶ID的好處。 – user2357112

這正好解決了我的問題。我想對記錄進行散列以創建密鑰，即''dict [hash] = record''，這樣當我添加一條新記錄時，我可以快速檢查是否存在重複項，如果是dict中的hash。如所提供的參考文獻中所述。你的建議應該適合我，謝謝！ – wenhoo

每個字典的哈希值作爲關鍵

你沒有使用字典的哈希值。字典不具有散列值。從鏈接，它看起來像你使用

hash(frozenset(my_dict.items()))

在這種情況下，你應該不是僅僅是使用

frozenset(my_dict.items())

直接的關鍵。然後由正常的字典衝突處理爲您處理散列衝突。

一般來說，你不應該使用散列作爲字典鍵，因爲這樣做會破壞衝突解決方案。你應該使用哈希值作爲密鑰。

來源

2017-02-07 23:54:25 user2357112

通常，當多個鍵散列到同一個存儲桶時發生衝突。在這種情況下，我們需要確保我們能夠區分這些鍵。

Chaining collision resolution是用於散列表衝突解決的流行技術之一。例如，兩個字符串「歡迎使用stackoverflow」和「如何贏得聲譽？」分別產生散列碼100和200。假設總陣列大小爲10，它們都會在同一個桶中（100％10和200％10）結束。另一種方法是Open Addressing在散列時解決衝突。

您可以閱讀Python Dictionary Implementations這篇文章，其中討論了處理衝突，因爲python字典是使用散列表實現的。

來源

2017-02-07 23:57:33

處理哈希衝突

回答

相關問題