实现固定大小的哈希映射
Implementing a fixed-size hash map
我需要实施针对内存和速度优化的固定大小哈希映射，但我不清楚这意味着什么：这是否意味着我的哈希映射中可以拥有的桶数是固定的？或者我不能通过链表动态分配内存和扩展哈希映射的大小来解决冲突？如果对后一个问题的回答是肯定的，那么想到的第一个冲突解决方法是线性探测——任何人都可以评论其他内存和速度效率更高的方法，或者指出任何资源来开始吗？谢谢！
在没有看到具体要求的情况下，很难解释“针对内存和速度优化的固定大小哈希映射”的含义，因此我将重点关注“针对内存和速度优化”方面。
内存
内存效率很难给出建议，尤其是当散列映射实际上以“固定”大小存在时。一般来说，open-addressing 可以提高内存效率，因为可以单独存储键和值，而不需要指向下一个 and/or 前一个 linked 列表节点的指针。如果您的哈希映射允许调整大小，您需要选择一种冲突解决策略，以便在调整大小之前允许更大的负载 (elements/capacity)。 1/2 是许多哈希映射实现使用的常见负载，但这意味着至少 2x 始终使用必要的内存。冲突解决策略通常需要在速度和内存效率之间取得平衡，特别是针对您的实际 requirements/use 情况进行调整。
速度
从现实世界的角度来看，特别是对于较小的哈希映射或具有普通大小的密钥的哈希映射，优化速度的最重要方面可能是减少 cache-misses。这意味着尽可能多地将执行操作所需的信息放在连续的内存空间中。
我的建议是使用 open-addressing 而不是 chaining 来解决冲突。这将允许更多的内存是连续的，并且每次键比较应该至少减少 1 个缓存未命中。开放寻址将需要某种探测，但与从内存中获取 linked 列表的每个 link 相比，循环遍历多个数组元素检查键比较的成本应该更快。请参阅 此处 以了解 c++ std::vector 与 std::list 的基准测试，对于大多数操作而言，尽管算法复杂，但由于空间局部性，正常连续数组的速度更快。
在探测类型方面，线性探测存在聚类问题。随着碰撞的发生，相邻元素被消耗，导致数组同一部分中的碰撞越来越多，当 table 几乎满时，这变得异常重要。这可以通过重新散列、Robin-Hood hashing (As you are probing to insert, if you reach an element closer to it's ideal slot than the element being inserted, swap the two and try to insert that element instead, A much better description can be seen here) 等来解决。二次探测没有与线性探测相同的聚类问题，但它有其自身的局限性，并非每个数组位置都可以从每个位置到达其他数组位置，因此取决于大小，通常在需要调整大小之前只能填充数组的一半。
数组的大小也会影响性能。最常见的大小是 2 的幂大小和质数大小。 Java: A "prime" number or a "power of two" as HashMap size?
两者都存在争论，但主要性能将取决于使用情况，特别是两个大小的幂通常 非常 对于顺序散列来说很糟糕，但是散列到数组索引的转换可以通过单个 and 操作与相对昂贵的 mod.
值得注意的是，google_dense_hash 是一个非常好的哈希映射，在几乎所有用例中都轻松胜过 c++ 标准库变体，并且使用开放寻址、2 的幂调整大小约定和二次探测。 Malte Skarupke 写了一个优秀的散列 table 在许多情况下击败 google_dense_hash，包括查找。他的实现使用罗宾汉哈希和线性探测，具有探测长度限制。它在 blog post 中得到了很好的描述，还有针对其他哈希 table 的出色基准测试以及对性能提升的描述。
我需要实施针对内存和速度优化的固定大小哈希映射，但我不清楚这意味着什么：这是否意味着我的哈希映射中可以拥有的桶数是固定的？或者我不能通过链表动态分配内存和扩展哈希映射的大小来解决冲突？如果对后一个问题的回答是肯定的，那么想到的第一个冲突解决方法是线性探测——任何人都可以评论其他内存和速度效率更高的方法，或者指出任何资源来开始吗？谢谢！
在没有看到具体要求的情况下，很难解释“针对内存和速度优化的固定大小哈希映射”的含义，因此我将重点关注“针对内存和速度优化”方面。
内存
内存效率很难给出建议，尤其是当散列映射实际上以“固定”大小存在时。一般来说，open-addressing 可以提高内存效率，因为可以单独存储键和值，而不需要指向下一个 and/or 前一个 linked 列表节点的指针。如果您的哈希映射允许调整大小，您需要选择一种冲突解决策略，以便在调整大小之前允许更大的负载 (elements/capacity)。 1/2 是许多哈希映射实现使用的常见负载，但这意味着至少 2x 始终使用必要的内存。冲突解决策略通常需要在速度和内存效率之间取得平衡，特别是针对您的实际 requirements/use 情况进行调整。
速度
从现实世界的角度来看，特别是对于较小的哈希映射或具有普通大小的密钥的哈希映射，优化速度的最重要方面可能是减少 cache-misses。这意味着尽可能多地将执行操作所需的信息放在连续的内存空间中。
我的建议是使用 open-addressing 而不是 chaining 来解决冲突。这将允许更多的内存是连续的，并且每次键比较应该至少减少 1 个缓存未命中。开放寻址将需要某种探测，但与从内存中获取 linked 列表的每个 link 相比，循环遍历多个数组元素检查键比较的成本应该更快。请参阅 此处 以了解 c++ std::vector 与 std::list 的基准测试，对于大多数操作而言，尽管算法复杂，但由于空间局部性，正常连续数组的速度更快。
在探测类型方面，线性探测存在聚类问题。随着碰撞的发生，相邻元素被消耗，导致数组同一部分中的碰撞越来越多，当 table 几乎满时，这变得异常重要。这可以通过重新散列、Robin-Hood hashing (As you are probing to insert, if you reach an element closer to it's ideal slot than the element being inserted, swap the two and try to insert that element instead, A much better description can be seen here) 等来解决。二次探测没有与线性探测相同的聚类问题，但它有其自身的局限性，并非每个数组位置都可以从每个位置到达其他数组位置，因此取决于大小，通常在需要调整大小之前只能填充数组的一半。
数组的大小也会影响性能。最常见的大小是 2 的幂大小和质数大小。 Java: A "prime" number or a "power of two" as HashMap size?
两者都存在争论，但主要性能将取决于使用情况，特别是两个大小的幂通常 非常 对于顺序散列来说很糟糕，但是散列到数组索引的转换可以通过单个 and 操作与相对昂贵的 mod.
值得注意的是，google_dense_hash 是一个非常好的哈希映射，在几乎所有用例中都轻松胜过 c++ 标准库变体，并且使用开放寻址、2 的幂调整大小约定和二次探测。 Malte Skarupke 写了一个优秀的散列 table 在许多情况下击败 google_dense_hash，包括查找。他的实现使用罗宾汉哈希和线性探测，具有探测长度限制。它在 blog post 中得到了很好的描述，还有针对其他哈希 table 的出色基准测试以及对性能提升的描述。