1

我正在尝试在 Python 中实现 CARP 哈希，如以下 IETF 草案中所述：

https://datatracker.ietf.org/doc/html/draft-vinod-carp-v1-03#section-3.1

具体来说：

3.1。哈希函数

散列函数基于以零结尾的 ASCII 输入字符串输出 32 位无符号整数。URL 的机器名称和域名、协议以及每个成员代理的机器名称应以小写形式计算，因为 URL 的该部分不区分大小写。

由于此应用程序不需要不可逆性和强大的加密功能，因此使用了一个非常简单且快速的基于按位左旋转运算符的散列函数。

对于（URL 中的每个字符）： URL_Hash += _rotl(URL_Hash, 19) + char ；

成员代理哈希以类似的方式计算：

对于（MemberProxyName 中的每个字符）： MemberProxy_Hash += _rotl(MemberProxy_Hash, 19) + char ；

由于成员名称通常彼此相似，因此它们的哈希值通过以下附加操作进一步分布在哈希空间中：

MemberProxy_Hash += MemberProxy_Hash * 0x62531965 ; MemberProxy_Hash = _rotl (MemberProxy_Hash, 21) ;

3.2. 哈希组合

哈希通过首先异或 (XOR) URL 哈希与机器名称组合，然后乘以常数并执行按位旋转。

所有最终值和中间值都是 32 位无符号整数。

Combined_Hash = (URL_hash ^ MemberProxy_Hash) ; 组合哈希 += 组合哈希 * 0x62531965 ; Combined_Hash = _rotl(Combined_Hash, 21) ;

我尝试使用 numpy 创建 32 位无符号整数。第一个问题是在实现左位移时出现的。Numpy 自动将结果重新转换为 64 位无符号整数。对于任何会溢出 32 位的算术都是一样的。

例如：

from numpy import uint32

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = uint32()
    for char in data:
        hashed += hashed << 19 + ord(char)
    return hashed

x = key_hash("testkey")
print type(x)

回报：

输入“numpy.int64”

关于如何将这一切限制为 32 位空间的任何提示？此外，我对规范如何执行其中一些操作（如“MemberProxy_Hash += MemberProxy_Hash * 0x62531965”）在计算哈希时将永远适合 32 位感到有些困惑。

编辑：

根据反馈，听起来正确的解决方案是：

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        hashed += ((hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF
    return hashed


def server_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        hashed += ((hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF
    hashed += (hashed * 0x62531965) & 0xFFFFFFFF
    hashed = ((hashed << 21) + (hashed >> 11)) & 0xFFFFFFFF
    return hashed


def hash_combination(key_hash, server_hash):
    # hash should be a 32-bit unsigned integer
    combined_hash = (key_hash ^ server_hash) & 0xFFFFFFFF
    combined_hash += (combined_hash * 0x62531965) & 0xFFFFFFFF
    return combined_hash

编辑＃2：

另一个固定版本。

def rotate_left(x, n, maxbit=32):
    # assumes 32 bit
    x = x & (2 ** maxbit - 1)
    return ((x << n) | (x >> (maxbit - n)))


def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        hashed = (hashed + rotate_left(hashed, 19) + ord(char))
    return hashed


def server_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        hashed = (hashed + rotate_left(hashed, 19) + ord(char))
    hashed = hashed + hashed * 0x62531965
    hashed = rotate_left(hashed, 21)
    return hashed


def hash_combination(key_hash, server_hash):
    # hash should be a 32-bit unsigned integer
    combined_hash = key_hash ^ server_hash
    combined_hash = combined_hash + combined_hash * 0x62531965
    return combined_hash & 0xFFFFFFFF
4

2 回答 2

2

不要为 numpy uint32 烦恼。只需使用标准 Python int。result &= 0xFFFFFFFF通过删除不需要的高位位来限制操作的结果。

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        # hashed += ((hashed << 19) + ord(char)) & 0xFFFFFFFF
        # the above is wrong; it's not masking the final addition.
        hashed = (hashed + (hashed << 19) + ord(char)) & 0xFFFFFFFF
    return hashed

你可以只做一个最终的掩码，但在长输入时会相当慢，因为中间hashed值会是一个相当大的数字。

顺便说一句，上面不是一个很好的哈希函数。rotinrotl表示旋转，而不是移位。

你需要

# hashed += ((hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF
# the above is wrong; it's not masking the final addition.
hashed = (hashed + (hashed << 19) + (hashed >> 13) + ord(char)) & 0xFFFFFFFF

编辑……比较；这段代码：

def rotate_left(x, n, maxbit=32):
    # assumes 32 bit
    x = x & (2 ** maxbit - 1)
    return ((x << n) | (x >> (maxbit - n)))

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = 0
    for char in data:
        hashed = (hashed + rotate_left(hashed, 19) + ord(char))
    return hashed

def khash(data):
    h = 0
    for c in data:
        assert 0 <= h <= 0xFFFFFFFF
        h = (h + (h << 19) + (h >> 13) + ord(c)) & 0xFFFFFFFF
    assert 0 <= h <= 0xFFFFFFFF
    return h

guff = "twas brillig and the slithy toves did whatever"
print "yours: %08X" % key_hash(guff)
print "mine : %08X" % khash(guff)

产生：

yours: A20352DB4214FD
mine : DB4214FD
于 2012-05-19T00:38:40.360 回答
1

以下对我有用，虽然可能有点不合时宜：

from numpy import uint32

def key_hash(data):
    # hash should be a 32-bit unsigned integer
    hashed = uint32()
    for char in data:
        hashed += hashed << uint32(19) + uint32(ord(char))
    return hashed

x = key_hash("testkey")
print type(x)

问题是数字被强制指向更多而不是更少。

于 2012-05-19T00:38:06.337 回答