Python: "Hash"嵌套列表

Question

我有一本字典master，其中包含大约 50000 到 100000 个唯一列表，这些列表可以是简单列表，也可以是列表列表。每个列表都分配给一个特定的 ID(这是字典的键):

master = {12: [1, 2, 4], 21: [[1, 2, 3], [5, 6, 7, 9]], ...} # len(master) is several ten thousands

现在我有几百个字典，其中又包含大约 10000 个列表(与上面相同:可以嵌套)。这些命令之一的示例:

a = {'key1': [6, 9, 3, 1], 'key2': [[1, 2, 3], [5, 6, 7, 9]], 'key3': [7], ...}

我想针对我的 master 交叉引用每个字典的数据，即，我不想将每个列表保存在 a 中，而是只想存储master 的 ID(如果列表存在于 master 中)。

=> a = {'key1': [6, 9, 3, 1], 'key2': 21, 'key3': [7], ...}

我可以通过循环 a 中的所有值和 master 的所有值并尝试匹配列表(通过对它们进行排序)来做到这一点，但这需要年龄。

现在我想知道你会如何解决这个问题？我想到将 master 中的每个列表“散列”为一个唯一的字符串，并将其存储为新的 master_inverse 引用字典的键，例如:

master_inverse = {hash([1,2,4]): 12, hash([[1, 2, 3], [5, 6, 7, 9]]): 21}

那么以后查找就很简单了:

for k, v in a.items():
  h = hash(v)
  if h in master_inverse:
    a[k] = master_inverse[h]

你有更好的主意吗？这样的哈希值会是什么样子？是否已经有一个快速且独特的内置方法？

编辑:不知道为什么我没有立即想出这种方法:您认为使用 pickle 或 repr() 任何单个列表的 m5 哈希怎么样？

类似这样的事情:

import hashlib
def myHash(str):
  return hashlib.md5(repr(str)).hexdigest()

master_inverse = {myHash(v): k for k, v in master.items()}

for k, v in a.items(): 
   h = myHash(v)
   if h in master_inverse:   
     a[k] = master_inverse[h]

编辑2:我对其进行了测试:根据我的 master_inverse 检查一百个字典中的一个(在我的示例中 a，a 包含我的基准大约 20k 值)非常快，没想到:0.08秒。所以我想我可以忍受这一点。

Answer 1

MD5 方法可以工作，但在使用 MD5 哈希时，您需要注意缓存冲突的可能性非常小(请参阅 How many random elements before MD5 produces collisions? 了解更多详细信息)。

如果您需要绝对确保程序正常工作，您可以将列表转换为元组并创建字典，其中键是您创建的元组，值是主字典中的键(与master_inverse相同，但使用完整值而不是 MD5 哈希值)。

有关如何使用元组作为字典键的更多信息:http://www.developer.com/lang/other/article.php/630941/Learn-to-Program-using-Python-Using-Tuples-as-Keys.htm .