在python中使用鏈表中的元組

Question

我的老師希望我們使用元組和鏈表（用於碰撞）在Python中重新創建dict類。其中一種方法用於返回給定密鑰的值。我知道如何在元組中執行此操作（在位置[0]處找到鍵並返回位置[1]），但我不知道如何在碰撞情況下執行此操作。有什麼建議麼？如果需要更多信息，請讓我知道

Answer 1

這聽起來像你有某種散列來得到一個可能性的短名單，所以，你把你的密鑰散列到一個小數字，例如。 0-256（作爲一個例子，它可能散列爲63）。然後，您可以直接在索引63處找到您的數據。因爲您可能有多個項目的散列值爲63，所以您的條目63將包含（鍵值對）列表，您必須逐一搜索 - 實際上，您已將搜索區域縮小了完整列表的255/256。可選地，當特定關鍵點的碰撞超過閾值時，您可以重複該過程 - 這樣您可以獲得mydict [63] [92]，再次以相同的因子減少問題的大小。你可以無限地重複這個。