Python中非常快速的哈希？

Question

我正在用Python编写类似玩具rsync的工具。像许多类似的工具一样，它将首先使用非常快速的哈希作为rolling hash，然后在找到匹配项后使用SHA256（但后者不在这里：SHA256，MDA5等太慢了）。滚动哈希）。

我目前正在测试各种快速哈希方法：

import os, random, time

block_size = 1024  # 1 KB blocks
total_size = 10*1024*1024  # 10 MB random bytes
s = os.urandom(total_size)

t0 = time.time()
for i in range(len(s)-block_size):
    h = hash(s[i:i+block_size])
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))

我得到：0.8 MB / s ...因此，Python内置的hash(...)函数在这里太慢了。

哪种解决方案可以在标准计算机上实现至少10 MB / s的更快散列？

• 我尝试过

  hash(...)

  但是它并不好（1.1 MB / s）

• 我尝试过

  import zlib
  ...
      h = zlib.adler32(s[i:i+block_size])

  ，它也很慢

• 有趣的事实：即使没有任何哈希函数，循环本身也很慢！

  sum(s[i:i+block_size]) % modulo

  我得到：仅3.0 MB / s！因此，具有循环访问

  t0 = time.time()
  for i in range(len(s)-block_size):
      s[i:i+block_size]

  上滚动块的简单事实已经很慢。

而不是重新发明轮子并编写自己的哈希值或使用自定义Rabin-Karp算法，您会提出什么建议，首先要加快循环速度，然后再将其作为哈希值？

---

编辑：上面的“有趣的事实”慢循环的（部分）解决方案：

s

使用Numba进行了巨大的改进：40.0 MB / s，但此处仍未进行哈希处理。至少我们没有以3 MB / s的速度被阻塞。

Answer 1

您有什么建议，首先要加快循环速度，然后再将其作为哈希值？

增加块大小。块大小越小，每个字节将执行的python越多，执行速度就越慢。

编辑：您的范围的默认步长为1，并且不将

import os, random, time, zlib
from numba import jit

@jit()
def main(s):
    for i in range(len(s)-block_size):
        block = s[i:i+block_size]

total_size = 10*1024*1024  # 10 MB random bytes
block_size = 1024  # 1 KB blocks
s = os.urandom(total_size)
t0 = time.time()
main(s)
print('rolling hashes computed in %.1f sec (%.1f MB/s)' % (time.time()-t0, total_size/1024/1024/(time.time()-t0)))

乘以i，因此，您不是在10 * 1024个不重叠的1k块上进行迭代，而是在1000万个-1024上进行迭代大部分重叠的块