有没有Python中与非唯一集合等价的数据结构？

Question

我有一个非常大的整数列表嵌套列表，希望使用“hash()”来提高搜索速度。每个嵌套列表的结果哈希值需要独立于整数的顺序，仅取决于列表中的值。这建议使用（冻结）集合作为适当的数据结构进行哈希。然而，我需要保留每个整数值，无论是否重复，这是集合无法满足的。

因此，我对列表进行排序，转换为元组并进行哈希，但速度相当慢，我想象中应该有更好的策略。

如果您能提供任何更有效的建议，我将不胜感激。

- Andy

---

为什么需要保留重复项？顺序是否重要，或者您只需要每个整数的正确计数？ - user395760

好的，我只需要每个正确计数。在这种情况下，整数：计数字典似乎是有效的。但我不认为字典是可哈希的。 - Andy

Answer 1

字典就是哈希表。

>>> 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}

在一台不算特别快的桌面电脑上大约需要一秒钟左右。

- msw

---

是的，这可以是一个从字典派生的类，并且还可以添加其他效率。鉴于问题中的最小要求，这可能是最清晰的选择。 - msw

你忽略了结果结构需要被哈希的要求。Python字典等同于Perl哈希，但这并不意味着你可以对Python字典进行哈希！ - Ned Batchelder

同意你不能哈希一个字典，但无法确定这是一项要求还是仅仅是提问者的困惑。 - msw

Answer 2

正如Winston Ewert所建议的那样，使用Counter还有其他好处。你不仅可以自然地拥有你所描述的数据结构（Counter继承自dict，因此具有哈希功能），而且还可以做一些很棒的事情，比如算术运算，这对你的情况可能非常有用。

from collections import Counter
set1 = Counter("hello")
set2 = Counter("hell")

print(set1)
>> Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})

print(set1)
>> Counter({'l': 2, 'h': 1, 'e': 1})

set1 - set2
>> Counter({'o': 1})

- kd88

Answer 3

你的数据结构很好，你需要的是一种计算哈希值的方法，以满足你的要求：整数的顺序不重要，但重复的数字需要被保留，并且需要快速。

那么，如何计算这些数字的乘积呢？得到的结果数字将作为一个很好的哈希值。如果你想避免使用长整型而保持在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

- Ned Batchelder

Answer 4

创建一个计数器字典。（如果你的 Python 版本足够新，你可以使用 Counter 类代替。将 items 列表构造成一个集合并进行哈希处理。）

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

但我不知道它是否比你已经完成的更有效。

由于这是一个哈希，它不需要表示您的一些数字是重复的事实。因此，您可以只使用：

return hash(frozenset(items))

- Winston Ewert