5 ms·

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

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.

Delk 5y ago
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?
- ternaryoperator 5y ago
  Many (most?) hash tables are write-once, read-many (caches, databases, etc. among others) so optimizing for reading makes a lot of sense.
- hawk_ 5y ago
  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.
  - Delk 5y ago
    Good point. For some reason I didn't think about duplicate checking even though it's pretty obvious.
sltkr 5y ago
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.
- eqvinox 5y ago
  > 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.
louthy 5y ago
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-efficient-immutable-collections.pdf https://michael.steindorfer.name/publications/phd-thesis-eff... [2] https://github.com/louthy/language-ext/blob/main/LanguageExt.Core/DataTypes/TrieMap/TrieMap.cs https://github.com/louthy/language-ext/blob/main/LanguageExt... [3] https://github.com/louthy/language-ext/blob/main/LanguageExt.Core/DataTypes/TrieMap/TrieMap.cs#L1026 https://github.com/louthy/language-ext/blob/main/LanguageExt...
- loeg 5y ago
  Hashmaps that have string-like keys suitable for indexing a trie are a subset of all hashmaps.
- ufo 5y ago
  Is that for immutable/persistent hashmaps, or also for mutable hashmaps?
  - louthy 5y ago
    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.
nyc_pizzadev 5y ago
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.

Delk 5y ago

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?

ternaryoperator 5y ago
Many (most?) hash tables are write-once, read-many (caches, databases, etc. among others) so optimizing for reading makes a lot of sense.
hawk_ 5y ago
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.
- Delk 5y ago
  Good point. For some reason I didn't think about duplicate checking even though it's pretty obvious.

sltkr 5y ago

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.

eqvinox 5y ago
> 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.

louthy 5y ago

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-efficient-immutable-collections.pdf https://michael.steindorfer.name/publications/phd-thesis-eff... [2] https://github.com/louthy/language-ext/blob/main/LanguageExt.Core/DataTypes/TrieMap/TrieMap.cs https://github.com/louthy/language-ext/blob/main/LanguageExt... [3] https://github.com/louthy/language-ext/blob/main/LanguageExt.Core/DataTypes/TrieMap/TrieMap.cs#L1026 https://github.com/louthy/language-ext/blob/main/LanguageExt...

loeg 5y ago
Hashmaps that have string-like keys suitable for indexing a trie are a subset of all hashmaps.
ufo 5y ago
Is that for immutable/persistent hashmaps, or also for mutable hashmaps?
- louthy 5y ago
  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.

nyc_pizzadev 5y ago

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.