Is there an expandable hash table with an open address?

I am using an in-memory key value store used as a realtime service. It should be fast and low. Since the cardinality is not known in advance, the table must grow gradually. I prefer open address hash tables as they are significantly faster than chaining. However, open address hash tables usually require infrequent very slow interruptions during which service is unavailable. This is unacceptable. Expandable hash tables, on the other hand, are usually chain-based and slower than open addresses.

Are there any hash tables out there that are as fast as public addresses (like google dense_hash_map) and don't have big recalculations?

One easy way is to use an array of k small hash tables, so the paraphrasing 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, not the maximum unavailable time. If k small hash tables are used, although the maximum unavailable time is reduced to 1 / k, re-interceptions occur k times more often.

+3


source to share





All Articles