为什么将地址右移三位作为固定大小散列 table 的散列函数？

Question

我正在关注一篇文章，其中我有一个散列 table，其中包含固定数量的 2048 个篮子。
散列函数采用指针和散列 table 本身，将地址视为位模式，将其右移三位并以散列 table (2048) 的大小为模减少它：

（这里写成宏）：

#define hash(p, t) (((unsigned long)(p) >> 3) & \
                    (sizeof(t) / sizeof((t)[0]) - 1))

然而，这篇文章并没有详细说明为什么将地址右移三位（乍一看似乎有点武断）。我的第一个猜测是，原因是通过切断最后三位来对具有相似地址的组指针进行排序，但我看不出这有什么用，因为为一个应用程序分配的大多数地址无论如何都具有相似的地址；以此为例：

#include <stdio.h>

int main()
{
    
    int i1 = 0, i2 = 0, i3 = 0;
    
    
    printf("%p\n", &i1);
    printf("%p\n", &i2);
    printf("%p\n", &i3);
    
    printf("%lu\n", ((unsigned long)(&i1) >> 3) & 2047); // Provided that the size of the hash table is 2048.
    printf("%lu\n", ((unsigned long)(&i2) >> 3) & 2047);
    printf("%lu", ((unsigned long)(&i3) >> 3) & 2047);

    return 0;
}

此外，我想知道为什么它选择 2048 作为固定大小，这是否与三位移位有关。

作为参考，本文摘自 David P. Hanson 的“C 接口和实现，创建可重用软件的技术”。

Answer 1

虽然它不是由 C 语言标准规定的，但在大多数平台上（其中平台 = 编译器 + 指定的硬件架构），变量 x 被分配在一个地址是其倍数（即被整除） ) sizeof(x).

这是因为许多平台不支持未对齐的 load/store 操作（例如，将 4 字节的值写入未对齐到 4 字节的地址）。

知道 sizeof(long) 最多为 8（同样，在大多数平台上），我们可以进一步预测每个 long 变量地址的最后 3 位将始终为零。

在设计 hash-table 解决方案时，人们通常会力求尽可能减少碰撞。

此处，哈希解决方案取每个地址的最后 11 位。

因此，为了减少冲突次数，我们 shift-right 每个地址增加 3 位，从而用“更随机”的东西替换这 3 个“可预测”的零。

Answer 2

此代码假定将要散列的对象对齐到 8（更精确到 2^(right_shift) ）。否则此哈希函数（或宏）将 return 冲突结果。

#define mylog2(x)  (((x) & 1) ? 0 : ((x) & 2) ? 1 : ((x) & 4) ? 2 : ((x) & 8) ? 3 : ((x) & 16) ? 4 : ((x) & 32) ? 5 : -1)


#define hash(p, t) (((unsigned long)(p) >> mylog2(sizeof(p))) & \
                    (sizeof(t) / sizeof((t)[0]) - 1))

unsigned long h[2048];                    

int main()
{
    
    int i1 = 0, i2 = 0, i3 = 0;
    long l1,l2,l3;
    
    
    printf("sizeof(ix) = %zu\n", sizeof(i1));
    printf("sizeof(lx) = %zu\n", sizeof(l1));
    
    printf("%lu\n", hash(&i1, h)); // Provided that the size of the hash table is 2048.
    printf("%lu\n", hash(&i2, h));
    printf("%lu\n", hash(&i3, h));

    printf("\n%lu\n", hash(&l1, h)); // Provided that the size of the hash table is 2048.
    printf("%lu\n", hash(&l2, h));
    printf("%lu\n", hash(&l3, h));


    return 0;
}

https://godbolt.org/z/zq1zfP

为了使其更可靠，您需要考虑对象的大小：

#define hash1(o, p, t) (((unsigned long)(p) >> mylog2(sizeof(o))) & \
                    (sizeof(t) / sizeof((t)[0]) - 1))

然后它将处理任何大小的数据https://godbolt.org/z/a7dYj9

Answer 3

内存分配必须正确对齐。 IE。硬件可能指定 int 应与 4 字节边界对齐，或者 double 应与 8 字节对齐。这意味着 int 的最后两个地址位必须为零，double.

的三个位

现在，C 允许您定义混合 char、int、long、float 和 double 字段（以及更多).虽然编译器可以添加填充以将字段的偏移量对齐到适当的边界，但整个结构也必须正确对齐到其成员之一使用的最大对齐方式。

malloc() 不知道您要对内存做什么，因此它必须 return 分配最坏情况。这种对齐是平台特有的，但一般不少于8字节对齐。今天更典型的值是 16 字节对齐。

因此，散列算法只是简单地切断了地址的三位，这三位实际上始终为零，因此对于散列值来说还不算毫无价值。这很容易将hash冲突的次数减少8倍。（只截掉3位说明函数是前段时间写的，今天编程应该截掉4位。）

为什么将地址右移三位作为固定大小散列 table 的散列函数？

Why right-shifting an address by three bits as a hash function for a fixed-size hash table?

c

hash

pointers

hashtable