CARP哈希在Python

Question

我试图如下面的IETF草案描述实现在Python CARP散列：

http://tools.ietf.org/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）+炭;

Becaues会员名称通常彼此相似，它们的散列 值是通过以下 附加操作跨越哈希空间进一步传播：

MemberProxy_Hash + = MemberProxy_Hash * 0x62531965; MemberProxy_Hash = _rotl（MemberProxy_Hash，21）;

3.2。散列组合

散列由第一个排除或（XOR）URL散列合并，然后乘以 机器名称，然后乘以常数并执行 按位旋转。

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

Combined_Hash =（URL_hash^MemberProxy_Hash）; Combined_Hash + = Combined_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 

Answer 1

不要打扰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将是一个相当大的数字。

顺便说一句，以上不会是一个很好的散列函数。 rotl中的rot表示轮转，不轮班。

你需要

# 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 

Answer 2

我下面的作品，虽然也许有点unpythonic：

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) 

的问题是，数字正在寻找更多的比特被迫而不是更少。