首先，如果您非常确定O(N)散列在这里是合理且必要的，并且您只想使用比 更快的算法来加快速度hash(str(x))，请尝试以下操作：
def hash_seq(iterable):
result = hash(type(iterable))
for element in iterable:
result ^= hash(element)
return result
当然，这不适用于可能很深的序列，但有一个明显的方法：
def hash_seq(iterable):
result = hash(type(iterable))
for element in iterable:
try:
result ^= hash(element)
except TypeError:
result ^= hash_seq(element)
return result
我不认为这是一个足够好的哈希算法，因为它会为同一个列表的不同排列返回相同的值。但我很确定没有足够好的哈希算法会更快。至少如果它是用 C 或 Cython 编写的，如果这是你要走的方向，你最终可能会想要这样做。
此外，值得注意的是，这在str(or marshal) 不正确的许多情况下是正确的——例如，如果您list可能有一些可变元素repr涉及它id而不是它的值。但是，它仍然不是在所有情况下都是正确的。特别是，它假设“迭代相同的元素”意味着任何可迭代类型的“相等”，这显然不能保证是真的。假阴性不是什么大问题，但假阳性是（例如，dict具有相同键但不同值的两个 s 可能会虚假地比较相等并共享一个备忘录）。
此外，它不使用额外的空间，而不是使用相当大的乘数的 O(N)。
无论如何，值得先尝试一下，然后才决定是否值得分析它的足够好和调整微优化。
这是浅层实现的一个简单的 Cython 版本：
def test_cy_xor(iterable):
cdef int result = hash(type(iterable))
cdef int h
for element in iterable:
h = hash(element)
result ^= h
return result
通过快速测试，纯 Python 实现非常慢（正如您所料，与 C 循环 in strand相比，所有 Python 循环marshal），但 Cython 版本很容易获胜：
test_str( 3): 0.015475
test_marshal( 3): 0.008852
test_xor( 3): 0.016770
test_cy_xor( 3): 0.004613
test_str(10000): 8.633486
test_marshal(10000): 2.735319
test_xor(10000): 24.895457
test_cy_xor(10000): 0.716340
仅在 Cython 中迭代序列并且什么都不做（实际上只是 N 次调用PyIter_Next和一些引用计数，因此您在本机 C 中不会做得更好）与test_cy_xor. 您可以通过要求实际序列而不是可迭代来使其更快，甚至通过要求 a 来加快速度list，尽管无论哪种方式都可能需要编写显式 C 而不是 Cython 才能获得好处。
无论如何，我们如何解决订购问题？显而易见的 Python 解决方案是 hash(i, element)而不是element，但是所有元组操作都会将 Cython 版本减慢 12 倍。标准解决方案是在每个异或之间乘以某个数字。但是，当您使用它时，值得尝试让这些值很好地分布在短序列、小int元素和其他非常常见的边缘情况下。选择正确的数字很棘手，所以……我只是从tuple. 这是完整的测试。
_hashtest.pyx：
cdef _test_xor(seq):
cdef long result = 0x345678
cdef long mult = 1000003
cdef long h
cdef long l = 0
try:
l = len(seq)
except TypeError:
# NOTE: This probably means very short non-len-able sequences
# will not be spread as well as they should, but I'm not
# sure what else to do.
l = 100
for element in seq:
try:
h = hash(element)
except TypeError:
h = _test_xor(element)
result ^= h
result *= mult
mult += 82520 + l + l
result += 97531
return result
def test_xor(seq):
return _test_xor(seq) ^ hash(type(seq))
哈希测试.py：
import marshal
import random
import timeit
import pyximport
pyximport.install()
import _hashtest
def test_str(seq):
return hash(str(seq))
def test_marshal(seq):
return hash(marshal.dumps(seq))
def test_cy_xor(seq):
return _hashtest.test_xor(seq)
# This one is so slow that I don't bother to test it...
def test_xor(seq):
result = hash(type(seq))
for i, element in enumerate(seq):
try:
result ^= hash((i, element))
except TypeError:
result ^= hash(i, hash_seq(element))
return result
smalltest = [1,2,3]
bigtest = [random.randint(10000, 20000) for _ in range(10000)]
def run():
for seq in smalltest, bigtest:
for f in test_str, test_marshal, test_cy_xor:
print('%16s(%5d): %9f' % (f.func_name, len(seq),
timeit.timeit(lambda: f(seq), number=10000)))
if __name__ == '__main__':
run()
输出：
test_str( 3): 0.014489
test_marshal( 3): 0.008746
test_cy_xor( 3): 0.004686
test_str(10000): 8.563252
test_marshal(10000): 2.744564
test_cy_xor(10000): 0.904398
以下是一些可以加快速度的潜在方法：
- 如果你有很多深度序列，而不是使用
tryaround hash，调用PyObject_Hash并检查 -1。
- 如果你知道你有一个序列（或者，甚至更好，特别是 a
list），而不仅仅是一个可迭代的，PySequence_ITEM(or PyList_GET_ITEM) 可能会比PyIter_Next上面隐式使用的更快。
在任何一种情况下，一旦您开始调用 C API 调用，通常更容易放弃 Cython 并用 C 编写函数。（您仍然可以使用 Cython 围绕该 C 函数编写一个简单的包装器，而不是手动编写扩展模块.) 到那时，只需tuplehash直接借用代码，而不是重新实现相同的算法。
如果您正在寻找一种首先避免这种O(N)情况的方法，那是不可能的。如果您查看tuple.__hash__、frozenset.__hash__和ImmutableSet.__hash__工作方式（最后一个是纯 Python 并且非常易读，顺便说一句），它们都采用O(N). 但是，它们也都缓存哈希值。因此，如果您经常对相同 tuple的哈希（而不是不相同但相等的哈希）进行哈希处理，它会接近恒定时间。（它是，您每次调用的次数O(N/M)在哪里。）Mtuple
如果您可以假设您的list对象在调用之间永远不会发生变化，那么您显然可以做同样的事情，例如，将映射dict作为外部缓存。但总的来说，这显然不是一个合理的假设。（如果你的对象永远不会发生变异，那么只切换到对象而不用担心所有这些复杂性会更容易。）idhashlisttuple
但是您可以将您的list对象包装在一个添加缓存哈希值成员（或插槽）的子类中，并在收到变异调用（、、、等）时使append缓存__setitem__无效__delitem__。然后你hash_seq可以检查一下。
tuple最终结果与s: amortized具有相同的正确性和性能O(N/M)，除了 fortuple M是您调用每个相同的次数tuple，而 forlist它是您调用每个相同的次数list而不会在两者之间发生变化的次数。