Hacker News Reader

Comment by ternaryoperator | Hacker News Reader

He seems to overlook a fundamental optimization for open hash tables: ordering the elements in the linked list associated with each bucket. Right now to find an element, he reads the entire linked list if it's not there. By ordering the elements in the list upon insertion, he can greatly improve on that.

View on HN

Wouldn't ordering basically improve lookup performance at the expense of insertion performance? If you don't order the elements, you can just smash the new entry at the end of the list and be done with it.

Of course that might still be a reasonable trade-off to make. Is there experimental (or experiential) support for getting significant improvements from ordering?

ordered insertion can happen in the "middle" of the list. unordered always has to reach the end (to ensure no duplicate) so it's worse for insertion as well.

Good point. For some reason I didn't think about duplicate checking even though it's pretty obvious.

Many (most?) hash tables are write-once, read-many (caches, databases, etc. among others) so optimizing for reading makes a lot of sense.

This is possible, but typically this is not done for generic hash tables because it requires keys to be ordered (i.e. there must be a function that can tell whether one key is less than, greater than, or equal to another) while the current implementation only requires testing for equality.

> it requires keys to be ordered (i.e. there must be a function that can tell whether one key is less than, greater than, or equal to another)

It doesn't, you can order by hash value. However, it's a separate question on whether the hash value is stored with each item or not.

I believe the Compressed Hash-Array Mapped Prefix-tree (CHAMP) [1] is considered the current state of the art in terms of performance, memory efficiency, and memory locality.

I have an implementation here [2] that is used for the HashMap and HashSet types in language-ext. The 'guts' of the implementation is here [3]

[1] https://michael.steindorfer.name/publications/phd-thesis-eff...

[2] https://github.com/louthy/language-ext/blob/main/LanguageExt...

[3] https://github.com/louthy/language-ext/blob/main/LanguageExt...

Is that for immutable/persistent hashmaps, or also for mutable hashmaps?

It can be used for both. With my implementation it's mutable when initially populated (by passing an enumerable of key/value pairs), and then becomes immutable once constructed.

Hashmaps that have string-like keys suitable for indexing a trie are a subset of all hashmaps.

Every hash table implementation I have done I use an RB tree for each bucket. This way if the bucket is loaded with hundreds or thousands of elements, you aren’t penalized too badly.

Reply on news.ycombinator.com