我需要（并且找不到）MurmurHash的纯python（无c ++）实现，而且我自己写得太新手了。速度或内存使用对我的项目无关紧要。
我在这里找到了一个尝试，但它仅限于 31 位散列，我真的需要 64 位散列。
问问题
14544 次
5 回答
11
这是未经测试的（对不起！），但这是我想出的一个版本。Python 允许使用任意大的整数，因此我为前 8 个字节（或 64 位）创建了一个掩码，然后我将其（通过按位与）应用于所有可能产生大于 64 位整数的算术结果。也许其他人可以评论一般方法和字节序等可能存在的问题。
def bytes_to_long(bytes):
assert len(bytes) == 8
return sum((b << (k * 8) for k, b in enumerate(bytes)))
def murmur(data, seed):
m = 0xc6a4a7935bd1e995
r = 47
MASK = 2 ** 64 - 1
data_as_bytes = bytearray(data)
h = seed ^ ((m * len(data_as_bytes)) & MASK)
for ll in range(0, len(data_as_bytes), 8):
k = bytes_to_long(data_as_bytes[ll:ll + 8])
k = (k * m) & MASK
k = k ^ ((k >> r) & MASK)
k = (k * m) & MASK
h = (h ^ k)
h = (h * m) & MASK
l = len(data_as_bytes) & 7
if l >= 7:
h = (h ^ (data_as_bytes[6] << 48))
if l >= 6:
h = (h ^ (data_as_bytes[5] << 40))
if l >= 5:
h = (h ^ (data_as_bytes[4] << 32))
if l >= 4:
h = (h ^ (data_as_bytes[3] << 24))
if l >= 3:
h = (h ^ (data_as_bytes[4] << 16))
if l >= 2:
h = (h ^ (data_as_bytes[4] << 8))
if l >= 1:
h = (h ^ data_as_bytes[4])
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
return h
于 2013-04-02T01:50:11.860 回答
8
修复 Nikolas 版本中的错误
def bytes_to_long(bytes):
assert len(bytes) == 8
return sum((b << (k * 8) for k, b in enumerate(bytes)))
def murmur64(data, seed = 19820125):
m = 0xc6a4a7935bd1e995
r = 47
MASK = 2 ** 64 - 1
data_as_bytes = bytearray(data)
h = seed ^ ((m * len(data_as_bytes)) & MASK)
off = len(data_as_bytes)/8*8
for ll in range(0, off, 8):
k = bytes_to_long(data_as_bytes[ll:ll + 8])
k = (k * m) & MASK
k = k ^ ((k >> r) & MASK)
k = (k * m) & MASK
h = (h ^ k)
h = (h * m) & MASK
l = len(data_as_bytes) & 7
if l >= 7:
h = (h ^ (data_as_bytes[off+6] << 48))
if l >= 6:
h = (h ^ (data_as_bytes[off+5] << 40))
if l >= 5:
h = (h ^ (data_as_bytes[off+4] << 32))
if l >= 4:
h = (h ^ (data_as_bytes[off+3] << 24))
if l >= 3:
h = (h ^ (data_as_bytes[off+2] << 16))
if l >= 2:
h = (h ^ (data_as_bytes[off+1] << 8))
if l >= 1:
h = (h ^ data_as_bytes[off])
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
h = (h * m) & MASK
h = h ^ ((h >> r) & MASK)
return h
于 2015-01-29T05:51:29.007 回答
6
这是 MurmurHash3 32 的纯 Python 实现，它只对字符串进行哈希处理，但可以很容易地改用字节数组。这是该算法的Java 版本的一个端口。
def murmur3_x86_32(data, seed = 0):
c1 = 0xcc9e2d51
c2 = 0x1b873593
length = len(data)
h1 = seed
roundedEnd = (length & 0xfffffffc) # round down to 4 byte block
for i in range(0, roundedEnd, 4):
# little endian load order
k1 = (ord(data[i]) & 0xff) | ((ord(data[i + 1]) & 0xff) << 8) | \
((ord(data[i + 2]) & 0xff) << 16) | (ord(data[i + 3]) << 24)
k1 *= c1
k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17) # ROTL32(k1,15)
k1 *= c2
h1 ^= k1
h1 = (h1 << 13) | ((h1 & 0xffffffff) >> 19) # ROTL32(h1,13)
h1 = h1 * 5 + 0xe6546b64
# tail
k1 = 0
val = length & 0x03
if val == 3:
k1 = (ord(data[roundedEnd + 2]) & 0xff) << 16
# fallthrough
if val in [2, 3]:
k1 |= (ord(data[roundedEnd + 1]) & 0xff) << 8
# fallthrough
if val in [1, 2, 3]:
k1 |= ord(data[roundedEnd]) & 0xff
k1 *= c1
k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17) # ROTL32(k1,15)
k1 *= c2
h1 ^= k1
# finalization
h1 ^= length
# fmix(h1)
h1 ^= ((h1 & 0xffffffff) >> 16)
h1 *= 0x85ebca6b
h1 ^= ((h1 & 0xffffffff) >> 13)
h1 *= 0xc2b2ae35
h1 ^= ((h1 & 0xffffffff) >> 16)
return h1 & 0xffffffff
于 2014-05-30T14:53:22.367 回答
6
MurmurHash3 的另一个纯 python 实现，完全兼容并可以被 mmh3 包装器替换，但仍仅限于 32 位 Murmur3： https ://github.com/wc-duck/pymmh3
于 2015-02-27T14:27:59.300 回答
1
我建议更改bytes_to_long函数，以便可以使用少于 8 个字节的值：
def bytes_to_long(bytes):
length = len(bytes)
if length < 8:
extra = 8 - length
bytes = b'\000' * extra + bytes
assert len(bytes) == 8
return sum((b << (k * 8) for k, b in enumerate(bytes)))
这将填充bytearrayNull 字节，以便断言仍然可以按预期工作（您现在可以将其删除），但允许转换较小的值。
于 2018-05-22T10:03:34.130 回答