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

Question

我想将可变长度（6-60 个字符长）的字符串散列为 32 位 signed integers 以便在 PostgreSQL 中节省磁盘 space。

我不想加密任何数据，散列函数需要可重现并可从 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

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 2

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

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

或

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

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

Answer 3

我通常不会使用 32 位散列，除非基数非常低，因为它当然比 64 位散列更容易发生冲突。数据库很容易支持 bigint 8 字节（64 位）整数。考虑 this table 一些哈希冲突概率。

如果你使用Python≥3.6，你绝对不需要为此使用第三方包，你也不需要减去偏移量，因为你可以利用shake_128:

直接生成带符号的64位或variable bit-length hash

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。

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

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

Which string hashing algorithm produces 32-bit or 64-bit signed integers?

python

postgresql

hash

hashlib

signed-integer