我正在关注一篇文章，其中我有一个固定数量的 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("%pn", &i1);
printf("%pn", &i2);
printf("%pn", &i3);
printf("%lun", ((unsigned long)(&i1) >> 3) & 2047); // Provided that the size of the hash table is 2048.
printf("%lun", ((unsigned long)(&i2) >> 3) & 2047);
printf("%lu", ((unsigned long)(&i3) >> 3) & 2047);
return 0;
}
另外，我想知道为什么它选择 2048 作为固定大小，以及这是否与三位移位有关。
作为参考，本文摘自David P. Hanson的"C Interfaces and Implementations， Techniques for Create reuseable Software"。
内存分配必须正确对齐。 即，硬件可以指定int应与 4 字节边界对齐，或者double应与 8 字节对齐。这意味着int的最后两个地址位必须为零，double的三个位。
现在，C 允许你定义混合char、int、long、float和double字段(以及更多)的复杂结构。虽然编译器可以添加填充以将字段的偏移量与适当的边界对齐，但整个结构也必须正确对齐其成员之一使用的最大对齐方式。
malloc()不知道您将如何处理内存，因此它必须返回与最坏情况对齐的分配。此对齐方式特定于平台，但通常不小于 8 字节对齐。今天更典型的值是 16 字节对齐。
因此，哈希算法只是切断地址的三位，这些位实际上总是零，因此对于哈希值来说一文不值。这很容易将哈希冲突的数量减少 8 倍。(它只切断 3 位的事实表明该函数是不久前编写的。今天，它应该被编程为切断四个位。
此代码假定要散列的对象与 8 对齐(更准确地说是 2^(right_shift))。否则，此哈希函数(或宏)将返回冲突结果。
#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) = %zun", sizeof(i1));
printf("sizeof(lx) = %zun", sizeof(l1));
printf("%lun", hash(&i1, h)); // Provided that the size of the hash table is 2048.
printf("%lun", hash(&i2, h));
printf("%lun", hash(&i3, h));
printf("n%lun", hash(&l1, h)); // Provided that the size of the hash table is 2048.
printf("%lun", hash(&l2, h));
printf("%lun", 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
虽然它不是由 C 语言标准决定的，但在大多数平台上(平台 = 编译器 + 指定的硬件架构)，变量x被分配到一个地址，该地址是sizeof(x)的倍数(即可整除)。
这是因为许多平台不支持未对齐的加载/存储操作(例如，将 4 字节值写入未对齐到 4 字节的地址)。
知道sizeof(long)最多是8(同样，在大多数平台上)，我们可以进一步预测每个long变量地址上的最后 3 位将始终为零。
在设计哈希表解决方案时，通常会尽可能减少冲突。
在这里，哈希解决方案采用每个地址的最后 11 位。
因此，为了减少冲突的次数，我们将每个地址右移 3 位，从而用"更随机"的东西替换这 3 个"可预测"的零。