我正在内存中实现一个键值存储，用作实时服务。它需要快速且低延迟。因为事先不知道元素的数量，所以表应该逐渐增长。我更喜欢开放地址哈希表，因为它们比链接哈希表快得多。但是，开放地址哈希表通常需要偶尔非常缓慢的重新哈希，在此期间服务不可用。这是不可接受的。另一方面，可扩展哈希表通常基于链接，并且比开放地址的要慢。
是否有任何哈希表与开放地址的哈希表一样快（如谷歌的dense_hash_map）并且没有大的重新哈希开销？
一种简单的方法是使用由 k 个小哈希表组成的数组，这样可以将 rehash 开销降低到 1/k。但是，这对我来说没有意义，因为我需要减少总不可用时间而不是最大不可用时间。如果使用 k 个小哈希表，虽然最大不可用时间减少到 1/k，但重新哈希的发生频率会增加 k 次。