时间戳

首页 > 解决方案 > 为什么将地址右移三位作为固定大小哈希表的哈希函数？

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

问题描述

我正在关注一篇文章，其中我有一个带有固定数量的 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 接口和实现，创建可重用软件的技术”。

标签： cpointershashhashtable

解决方案

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

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

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

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

推荐阅读