3 ms·

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 me

by 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.