如何在 cpp 中创建固定大小（就内存而言）的散列 table？
How to create a fixed size (in terms of memory) hash table in cpp?
我正在处理大量基于某些输入生成浮点数的计算。如果我缓存这些数量，似乎有相当数量的重复调用可以优化。问题是，我不想缓存超过一定数量的内存使用量（即 10GiB）。有没有一种方法可以在我定义哈希映射时定义它，或者在每次将元素添加到映射时即时测试它？
为每个条目存储一个时间戳，并密切关注哈希表的 capacity，当它接近边界值时，刷新旧条目。
实现此目的的一种方法是实施 LRU 缓存 ("least recently used")，它可以让您始终修剪未引用时间最长的元素。对于某些使用模式，这优化了下一个需要的项目仍在缓存中的可能性。
设计 LRU 缓存曾经是一个常见的面试问题（也许现在仍然是），因此有许多 SO 答案等待找到。 This one 看起来比较完整。
但我不会那样做。 10 GiB 是很大的内存，您可以在其中保留很多条目 space。如果您可以消除开销并保留两倍的缓存条目，那么牺牲 LRU 缓存的精度可能是值得的。消除开销还可以累计为您节省足够的周期，以抵消非最佳缓存修剪策略所花费的周期。无论如何，LRU 可能不是您问题的最佳选择。谁知道？
有了好的散列函数和大散列 table，您可以使用另一种策略：只为每个散列值保留一个条目。该解决方案的优点是它几乎是零开销。不需要时间戳，甚至不需要桶列表指针。无需通过链来查看条目是否在缓存中；第一次命中是条目或要替换的条目。在实践中，如果您的条目不是太大，那可以很容易地使您可用的条目数翻倍。
对于稍微更精确的解决方案，您可以为每个哈希值保留两个条目，有点像简化的布谷鸟哈希。同样，没有存储开销（只要每个散列值最终都被使用），而且查找成本只是稍微多一点。 （真的很少，因为两个条目应该在同一个内存缓存行中。）为了获得类似 LRU 行为的东西，在这个变体中，如果你找到的缓存条目是哈希值的第二个条目，你交换这两个条目。 （实际上，在第一个不是您需要的条目之后，您交换了两个条目；然后您使用或替换现在是第一个条目的条目。）
C++ 标准库没有非链式哈希 table，但数据结构非常简单，几乎不需要库支持。图书馆可能拥有的有用的是散列支持。 （请参阅 boost.hash 以获得更多哈希值，如果您的密钥是 std::pair 或 std::tuple，则特别有用。）
除此之外，您真正需要的只是一个键值对数组，它的大小可以根据您要放入缓存的内存量进行调整。初始化这个数组有一个小问题：它需要被初始化为一些东西，这通常是默认键和值构造函数产生的任何东西。但是默认键对应的实际槽要么需要有正确的值（不太可能是默认值），要么需要更改为具有不同哈希值的不同键。
我正在处理大量基于某些输入生成浮点数的计算。如果我缓存这些数量，似乎有相当数量的重复调用可以优化。问题是，我不想缓存超过一定数量的内存使用量（即 10GiB）。有没有一种方法可以在我定义哈希映射时定义它，或者在每次将元素添加到映射时即时测试它？
为每个条目存储一个时间戳，并密切关注哈希表的 capacity，当它接近边界值时，刷新旧条目。
实现此目的的一种方法是实施 LRU 缓存 ("least recently used")，它可以让您始终修剪未引用时间最长的元素。对于某些使用模式，这优化了下一个需要的项目仍在缓存中的可能性。
设计 LRU 缓存曾经是一个常见的面试问题（也许现在仍然是），因此有许多 SO 答案等待找到。 This one 看起来比较完整。
但我不会那样做。 10 GiB 是很大的内存，您可以在其中保留很多条目 space。如果您可以消除开销并保留两倍的缓存条目，那么牺牲 LRU 缓存的精度可能是值得的。消除开销还可以累计为您节省足够的周期，以抵消非最佳缓存修剪策略所花费的周期。无论如何，LRU 可能不是您问题的最佳选择。谁知道？
有了好的散列函数和大散列 table，您可以使用另一种策略：只为每个散列值保留一个条目。该解决方案的优点是它几乎是零开销。不需要时间戳，甚至不需要桶列表指针。无需通过链来查看条目是否在缓存中；第一次命中是条目或要替换的条目。在实践中，如果您的条目不是太大，那可以很容易地使您可用的条目数翻倍。
对于稍微更精确的解决方案，您可以为每个哈希值保留两个条目，有点像简化的布谷鸟哈希。同样，没有存储开销（只要每个散列值最终都被使用），而且查找成本只是稍微多一点。 （真的很少，因为两个条目应该在同一个内存缓存行中。）为了获得类似 LRU 行为的东西，在这个变体中，如果你找到的缓存条目是哈希值的第二个条目，你交换这两个条目。 （实际上，在第一个不是您需要的条目之后，您交换了两个条目；然后您使用或替换现在是第一个条目的条目。）
C++ 标准库没有非链式哈希 table，但数据结构非常简单，几乎不需要库支持。图书馆可能拥有的有用的是散列支持。 （请参阅 boost.hash 以获得更多哈希值，如果您的密钥是 std::pair 或 std::tuple，则特别有用。）
除此之外，您真正需要的只是一个键值对数组，它的大小可以根据您要放入缓存的内存量进行调整。初始化这个数组有一个小问题：它需要被初始化为一些东西，这通常是默认键和值构造函数产生的任何东西。但是默认键对应的实际槽要么需要有正确的值（不太可能是默认值），要么需要更改为具有不同哈希值的不同键。