如何对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
相关产品推荐
相关产品推荐

