假设我们有一个使用链表(链表)来解决哈希冲突的哈希表。每个哈希表槽都有一个指向链表第一个节点的指针字段。该指针将占用 4 或 8 个字节，具体取决于 x86 或 x64 操作系统。
对于一些具有百万槽的大型哈希表，指针会消耗大量的内存资源。对于硬件实现，我们可以在 FPGA 上自定义指针/地址宽度以节省内存。我的问题是，对于软件实现，是否还有任何方法可以将指针大小减小到 3 个字节？
最佳答案
如果您首先不以这种方式实现哈希表，则可以将溢出列表的指针大小开销减少到 0 字节。
实现哈希表实际上没有任何缺点，如果表的一个槽已经包含一个值，您可以应用“某种策略”来找到另一个空槽。如果您在编写时这样做，您的读取功能需要执行模拟步骤以找到正确的读取位置。
这种方法实际上并不比外部溢出列表更差，因为在有那些溢出列表的情况下，您所做的是在溢出列表内执行线性搜索。使用您执行的就地哈希表 - 根据所选策略，也类似于线性探测。
这样做的一个想法是使用一组哈希键而不是一个。 (一般为2，则称为Double hashing)。如果你写入并且表的位置已经被占用，你使用你的集合中的下一个散列键并重试，直到你的散列键用完或直到你找到一个空位。使用 N 个哈希键，您可以执行 N 个步骤。
对于读取，在这种情况下，您尝试找到条目，以与写入相同的顺序应用哈希键集，并探测是否这是您需要的条目，就像您探测的方式一样你的溢出列表。
由于哈希表只有在填充率较低时才“有意义”，因此该策略实际上节省了溢出列表实现所需的大量内存。
关于c++ - 如何减少哈希表槽中的指针/地址宽度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29762369/