You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

如何对64位整数列表哈希,使元素取模长度后得唯一索引

位打乱实现哈希表唯一索引的思路困境与求助

我的需求是:对给定的64位整数列表进行位打乱处理,使得每个元素对列表长度取模后,能得到0到长度-1范围内的唯一索引,以此实现哈希表*O(1)*的查找时间复杂度。

最初我想用deltaSwap函数(我多年来一直青睐这个来自棋类编程领域的函数),通过一组特定的mask和delta值对,经过若干次迭代来实现这个效果:

/**
 * swap any none overlapping pairs of bits
 *   that are delta places apart
 * @param b any bitboard
 * @param mask has a 1 on the least significant position
 *             for each pair supposed to be swapped
 * @param delta of pairwise swapped bits
 * @return bitboard b with bits swapped
 */
U64 deltaSwap(U64 b, U64 mask, int delta) {
   U64 x = (b ^ (b >> delta)) & mask;
   return   x ^ (x << delta)  ^ b;
}

但大量实验后我意识到,64位的排列数是64!,这个数值极大,想用有限的mask和delta对来表示所需的位打乱模式几乎不可能。

后来我认为,或许只需打乱低32位(甚至更低位,因为实际应用场景是内存地址),但排列数依然庞大,我最初认为用少量delta值及对应mask作为哈希种子的想法显然不切实际。

为完整说明,我附上生成上述mask列表(含空操作mask共64个)的函数:

uint64_t getMask( int d )
{
    static const uint64_t m[6] = {
        0x5555555555555555,
        0x3333333333333333,
        0x0f0f0f0f0f0f0f0f,
        0x00ff00ff00ff00ff,
        0x0000ffff0000ffff,
        0x00000000ffffffff
    };
    uint64_t t = 0xffffffffffffffffULL;
    for( int i = 0, j = d; i < 6 && j; ++i, j >>= 1 )
        if( j&1 ) t &= m[i];
    //if( ( d&64 )  && ( ( ( d-1 )&d )^64) ) t <<= ((~d)+1)&d;
    /*
    an additional set of "sister masks", where the accompanying delta must be
    d-2*LSB, or d-2*((-d)&d), stripping the top bit also, ^64, naturally.
    can be achieved including this conditional and increasing the upper bound to 127.
    When d is a power of 2, for range 64:127, the mask will be a repeat of d^64.
    */
    return  t;
}

我曾误以为6次迭代就能实现目标,但显然这是错误的。这个思路源于我对位棋盘及其n维旋转对称性的长期研究。

经过反复思考,我仍不确定是否能在不单独打乱每一位的情况下实现需求,且怀疑当前方法完全错误,但想不到其他思路,因此希望能得到相关建议。

内容的提问来源于stack exchange,提问作者Zacariaz

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.07.07 12:10:56