I'm implementing a key-value store in memory used as a real-time service. It needs to be fast and low latency. Because the number of elements is not known in advance, the table should grow gradually. I prefer open-address hash tables since they are significantly faster than chaining ones. However, open-address hash tables typically require occasional very slow rehashs, during which the service is unavailable. This is not acceptable. On the other hand, extensible hash tables are typically based on chaining, and are slower than open address ones.
Are there any hash tables that are as fast as open address ones (like google's dense_hash_map) and do not have large rehash overhead?
One simple way is to use an array of k small hash tables, so the rehash overhead can be reduced to 1/k. However, this doesn't make sense in my case, because I need to reduce the total unavailable time rather than the max unavailable time. If k small hash tables are used, although the max unavailable time is reduced to 1/k, the rehashs occur k times more often.