2

我想将可变长度（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_)
4

3 回答 3

2

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

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

或者

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

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

于 2017-07-25T18:13:04.457 回答
0 
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
于 2017-07-24T12:27:49.353 回答
0

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

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

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。

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

于 2019-03-30T17:15:32.807 回答