在Python中是否有等价的非唯一集合数据结构？

Question

我有一个非常大的整数列表，里面又包含了很多小列表，我想用“哈希”这个方法来提高搜索速度。每个小列表生成的哈希值需要和里面的整数顺序无关，只和整数的值有关。这让我想到可以用一个（冻结的）集合来做哈希，因为集合可以处理这些情况。

但是，我需要保留每一个整数的值，不管它们是否重复，这就让集合不太适用了。

所以，我只能把列表排序，然后转换成一个元组再进行哈希，这样的做法比较慢，我觉得应该有更好的方法。

如果有人能给我一些更高效的建议，我会非常感激。

Answer 1

创建一个字典来记录计数。（如果你的Python版本足够新，可以使用Counter类来代替。可以从项目列表中构建一个集合，然后进行哈希处理。）

counter = collections.defaultdict(int)
for item in items:
     counter[item] += 1
return hash(frozenset(counter.items()))

不过我不确定这样做是否会比你已经完成的更有效率。

因为这是一个哈希，它不需要表示某些数字是重复的。所以你可以直接使用：

return hash(frozenset(items))

Answer 2

你的数据结构没问题，关键是要找到一种方法来计算一个哈希值，这个哈希值要符合你的要求：整数的顺序不重要，但重复的数字需要被考虑，而且计算速度要快。

那我们可以考虑计算这些数字的乘积吗？这样得到的结果可以很好地作为哈希值。如果你想避免使用会让计算变慢的长整型，可以把结果保持在32位整数范围内。唯一需要注意的是零，但你可以跳过零，这样不会影响哈希值，只是可能会让哈希值的区分度降低。

LIMIT = 999999937 # largest 9-digit prime
def list_hash(l):
    h = 1
    for i in l:
        if i:
            h *= i
            h %= LIMIT
    return h

Answer 3

字典就是一种哈希表。

>>> def bag_random(d, n):
...     x = random.randint(0, n)
...     if x in d:
...             d[x] += 1
...     else:
...             d[x] = 1
... 
>>> a = {}
>>> for i in xrange(10**6):
...     bag_random(a, 100)
... 
>>> a
{0: 9856, 1: 9787, 2: 9944, 3: 9822, 4: 9978, 5: 9915, 6: 9915, 7: 9860, 8: 9926, 9: 9756, 10: 9914, 11: 10030, 12: 10009, 13: 9803, 14: 9918, 15: 10136, 16: 9818, 17: 9868, 18: 9893, 19: 9971, 20: 9998, 21: 9982, 22: 9884, 23: 9806, 24: 9998, 25: 9926, 26: 9977, 27: 10011, 28: 10030, 29: 9899, 30: 9808, 31: 9825, 32: 9980, 33: 9812, 34: 9928, 35: 9827, 36: 9934, 37: 9883, 38: 9913, 39: 9893, 40: 9822, 41: 9714, 42: 9871, 43: 9954, 44: 9989, 45: 9694, 46: 9878, 47: 9984, 48: 9893, 49: 9928, 50: 10093, 51: 9881, 52: 9828, 53: 9660, 54: 9884, 55: 9745, 56: 10048, 57: 9845, 58: 9916, 59: 9933, 60: 9944, 61: 9979, 62: 9992, 63: 9635, 64: 9811, 65: 9900, 66: 9950, 67: 9744, 68: 9829, 69: 10037, 70: 9929, 71: 9811, 72: 9830, 73: 10056, 74: 9957, 75: 9992, 76: 9777, 77: 9942, 78: 9809, 79: 9734, 80: 9855, 81: 10021, 82: 9914, 83: 10009, 84: 10018, 85: 9961, 86: 10036, 87: 9849, 88: 9951, 89: 9770, 90: 9795, 91: 9899, 92: 9975, 93: 9935, 94: 10037, 95: 9992, 96: 9868, 97: 10014, 98: 9689, 99: 9883, 100: 9878}

在一台速度不是特别快的电脑上，大约花了一秒钟的时间。