哪种字符串哈希算法生成 32 位或 64 位有符号整数?

Question

我想将可变长度(6-60个字符长(的字符串哈希为32位有符号整数，以节省PostgreSQL中的磁盘空间。

我不想加密任何数据，哈希函数需要从 Python 中重现和调用。问题是我只能找到产生无符号整数的算法(如CityHash(，因此产生高达2^32而不是2 ^31的值。

这是我到目前为止所拥有的：

import math
from cityhash import CityHash32
string_ = "ALPDAKQKWTGDR"
hashed_string = CityHash32(string_)
print(hashed_string, len(str(hashed_string)))
max_ = int(math.pow(2, 31) - 1)
print(hashed_string > max_)

Answer 1

Ryan在评论中回答了这个问题。只需从哈希结果中减去2147483648 (= 2^31(。

CityHash32(string_) - math.pow(2, 31)

或

CityHash64(string_) - math.pow(2, 63)

Ryan还提到，使用SHA-512并将结果截断为所需的位数将导致比上述方法更少的冲突。

Answer 2

create or replace function int_hash(s text)
returns int as $$
select ('x' || left(md5(s), 8))::bit(32)::int
;
$$ language sql immutable;
select int_hash('1');
int_hash  
------------
-993377736

Answer 3

除了非常低的基数之外，我通常不会使用 32 位哈希，因为它当然比 64 位哈希更大的冲突风险。数据库很容易支持 bigint 8 字节(64 位(整数。请考虑此表以了解一些哈希冲突概率。

如果您使用的是 Python ≥3.6，则绝对不需要为此使用第三方包，也不需要减去偏移量，因为您可以使用shake_128直接生成有符号的 64 位或可变位长度哈希：

import hashlib
from typing import Dict, List

class Int8Hash:
BYTES = 8
BITS = BYTES * 8
BITS_MINUS1 = BITS - 1
MIN = -(2**BITS_MINUS1)
MAX = 2**BITS_MINUS1 - 1
@classmethod
def as_dict(cls, texts: List[str]) -> Dict[int, str]:
return {cls.as_int(text): text for text in texts}  # Intentionally reversed.
@classmethod
def as_int(cls, text: str) -> int:
seed = text.encode()
hash_digest = hashlib.shake_128(seed).digest(cls.BYTES)
hash_int = int.from_bytes(hash_digest, byteorder='big', signed=True)
assert cls.MIN <= hash_int <= cls.MAX
return hash_int
@classmethod
def as_list(cls, texts: List[str]) -> List[int]:
return [cls.as_int(text) for text in texts]

用法：

>>> Int8Hash.as_int('abc')
6377388639837011804
>>> Int8Hash.as_int('xyz')
-1670574255735062145
>>> Int8Hash.as_list(['p', 'q'])
[-539261407052670282, -8666947431442270955]
>>> Int8Hash.as_dict(['i', 'j'])
{8695440610821005873: 'i', 6981288559557589494: 'j'}

若要改为生成 32 位哈希，请将Int8Hash.BYTES设置为 4。

免责声明：我没有编写统计单元测试来验证此实现是否返回均匀分布的整数。