是否有一个数据结构等价于python中的非唯一集合

Question

我有一个非常大的整数列表，我想用"hash()"来提高搜索速度。每个嵌套列表的结果散列值需要独立于整数的顺序，并且只依赖于列表中的值。这建议将(冻结的)集合作为适合散列的数据结构。但是，我需要保留每个整数值，无论是否重复，这是set的显示障碍。

所以，这让我给列表排序，转换成元组和哈希，这是相当慢的，我想有更好的策略。

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}

在不是特别快的桌面上花了一秒钟左右

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

用计数创建一个字典。(如果你的python版本足够新，你可以使用Counter类代替。用

的项列表和散列构造一个集合

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

但是我不知道它会比你已经做的更有效率。

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

return hash(frozenset(items))

Answer 4

使用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})