Index 1.6B Keys with Automata and Rust (2015)
blog.burntsushi.net
blog.burntsushi.net
In my search for interesting problems in the compression space, I ran into quite a lot of genomics research which suggests combining a compression algorithm with a lookup method, because identifying common items between samples reduces both storage and speeds up lookup.
> An FST based data structure as presented in this article does not have this capability. Namely, once it is produced, it cannot be changed.
That is somewhat of a weakness in general for succinct data structures of this sort, which makes it harder to remove data (much easier to maintain a "deleted set" to go with it, but that has problems with a delete + re-add).
You may also enjoy his xsv util [ https://github.com/BurntSushi/xsv ] for wrangling large csv files.
https://itnext.io/v8-deep-dives-understanding-map-internals-...
After looking at it, it doesn't. The "linked list" bit is just that it uses closed addressing (separate chaining), but instead of having a linked list of buckets, all the buckets are part of the array and the links point back into the array.
Raymond Hettinger's naturally ordered hashmap uses a similar "trick" for an open addressed map: a sparse array of hashes, and a separate dense array of actual data.
In both cases, the ordering is preserved through a dense array and the sparse "hash map" indexes into that array, this is as opposed to the older method of ordering (e.g. LinkedHashMap or PHP's own implementation) where the map items would be augmented with a (usually doubly) linked list maintaining the ordering information.
Of note: this order version can still be useful if the ordering information can be manipulated, manipulating ordering in the dense-array version would be expensive and convoluted. That's why even though CPython switched to the "hettinger map" back in 3.6 the OrderedDict collection still uses a doubly linked list to maintain its ordering information.
[0]: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...