Hacker News Reader

It’s usually not the right call to use a hash table like you’re describing. You’re not saving any work (all keys have to be migrated sooner or later) and by doing it like this you incur a non-trivial amount of overhead on most operations.

Hash tables generally work on the assumption that operations are O(1) in the amortized sense, that individual inserts might be expensive because of rehashing, but in aggregate they are very cheap. In practice, this is almost always a fine assumption, and it is how the vast majority of hash tables in all programming languages work.

The kinds of hash tables you are talking about have their uses in places where you have soft real-time constraints, but that is honestly a pretty niche use case.

Agreed this seems like major overkill, but then again so does writing your own hash table from scratch in C. :shrug:

iirc memcached either uses or used to use https://en.wikipedia.org/wiki/Linear_hashing to avoid rehashing induced pauses. it definitely makes sense for that use case but you're correct that it's not the right call for a general purpose hash table implementation.

> Hash tables generally work on the assumption that operations are O(1) in the amortized sense, that individual inserts might be expensive because of rehashing, but in aggregate they are very cheap.

Hash tables aren't O(1) in an amortized sense, they are O(1) in a statistical sense. The O(1) complexity of hash tables is dependent entirely on the size of the underlying array, the method of collision resolution, and the quality of the (pre)hash function in relation to the distribution of data you're storing in the table. Whether you insert 1 item or 1 million items into the table, you're still getting O(1) computational complexity if the table is designed well. If not, you could be getting O(n) complexity in the worst case.

While the fixed cost of hashing is irrelevant in the O(1) nature of hash table operations, it does mean that a hash table in practice could be slower (in terms of wall time) than a linked list for insert/find/remove operations. Despite a linked list being O(n) for those operations, a linked list doesn't have to pay the fixed cost of hashing. So for low values of n, the linked list might be a better choice. I think this is what you mean by "O(1) in the amortized sense" but it's not what we mean when we say the computational complexity of these operations on a hash table is O(1).

What the OP is talking about is an example of amortization of resize(), essentially adding a fixed cost to insert() and remove() so you don't have to pay a huge sum when you call resize(). But that doesn't mean insert() and remove() are no longer O(1).

Amortized cost is a technical term in complexity analysis: https://en.wikipedia.org/wiki/Amortized_analysis

If you use the terminology precisely, the worst case cost of a regular hash table insertion is O(n) because of the potential resize, but its amortized cost is O(1) because that's what it "averages out to".

The progressive rehashing described in the article is very similar to what Redis does [1].

Just thought I'd share a example of a use case where the incremental rehashing logic makes sense.

[1]: https://github.com/redis/redis/blob/unstable/src/dict.c

If your application is not negatively affected by such jitter why not use a garbage collected language?

Maybe you still want fine-grained control over code generation and memory allocation. But it's a valid question to ask.

Programs have different phases and jitter might be relevant only in some of them.

Imagine hash tables used to store configuration data. You don't care about performance of "reload config" operation, but once config is loaded and the worker is handling traffic, read operations must be fast.

I agree. I’m rarely using a hash tables for growing data sets. In my experience, I’ve been more inclined to redesign the algorithm or use a different data structures at the point were a migrating hash table makes sense.

What happens if you have a sequence of puts that triggers an expansion and some keys get migrated, but all of a sudden you get a series of removes, such that you need to perform a shrink to keep memory usage linear?

Do you now end up with three live arrays? You can probably make things even more pathological...

Hash tables are not great for data structures that change dramatically in size. If you have this situation, the best thing to do is to copy one hash table into another and discard the original data structure.

Hash tables do that automatically.

Rehashing is controlled by various tunable strategies: Load factor (0.5-1), growth policy (primed or power2), growth factor (1.5, golden ratio or 2).

Linked list tables don't need to throw away nodes, they can just be relinked. But compaction is always better, because cache dominates. Most rehash do exactly that. Esp. multithreaded.

The best thing to do is to take a good one and don't touch it, unless you want a monster as in perl5. Eg the recent siphash security theater broke performance in all dynamic languages, even the linux kernel. Everything is perl now. You don't want that.

I think parent’s construction works just fine if you disallow removes, so it grows monotonically, regardless of how dramatic the increase in keys, so long as you move over 2 keys for every update to your map.

My comment was a description of a precise “drastic change” where incrementality becomes sophisticated. (Though in part I was hoping for a response which identifies an elegant approach without the complication I mentioned.)

I'm not a particularly good programmer, so I may be missing something here, but I'd think that moving the items should be its own function that happens in between gets and sets, no? Besides adding a decidedly non-read-only operation to what should be read-only, shouldn't the movement happen when you're not trying to do anything with the hash table?

typically rehashing is done during insert. if you were going to do it while not doing anything else with the hash table you'd have to use a background thread, and then you'd have to do some form of synchronization, so there would be significant additional complexity and overhead.

If get() mutates the array internally, does that mean even "read-only" operations aren't thread-safe?

> So on `get` if we're in the process of resizing

Not just get, but set also, right? Otherwise I would think a large group of set operations that overflowed more than once might be problematic to deal with. Or maybe I'm missing something that makes that a non issue?

yes, set also. go's map implementation uses this technique - allocate a new array of buckets and gradually migrate from old to new buckets (i think it does the migration during set and delete only, not get).

You can also allocate a small hash table at first, and reallocate it in a large virtual memory region once it about the size of a page (4k) so you won't have to reallocate it later.

can you do hashtable sharding? like have a hashtable point to another hashtable by using something appended to the key? just a thought on a procrastination filled Friday afternoon.

Of course! This is a distributed hash table. You can have one hashing function determine the shard and another determine the index in the hash table.