c - 为什么将地址右移三位作为固定大小哈希表的哈希函数？

Question

我正在关注一篇文章，其中我有一个包含固定数量 2048 个篮子的哈希表。
哈希函数采用指针和哈希表本身，将地址视为位模式，将其右移三位并以哈希表的大小为模(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 接口(interface)和实现，创建可重用软件的技术”。

Answer 1

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

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

malloc() 不知道你要对内存做什么，所以它必须返回一个为最坏情况对齐的分配。这种对齐是特定于平台的，但通常不少于 8 字节对齐。今天更典型的值是 16 字节对齐。

因此，哈希算法只是简单地截断了地址的三个位，这些位实际上总是为零，因此对于哈希值来说并不是毫无值(value)的。这很容易将哈希冲突的数量减少了 8 倍。(它只截断 3 位的事实表明该函数是不久前编写的。今天应该将其编程为截断 4 位。)