p-fast trie: lexically ordered hash map

https://dotat.at/@/2025-08-04-p-fast-trie.html

Here's a sketch of an idea that might or might not be a good idea. Dunno if it's similar to something already described in the literature -- if you know of something, please let me know via the links in the footer!

The gist is to throw away the tree and interior pointers from a qp-trie. Instead, the p-fast trie is stored using a hash map organized into stratified levels, where each level corresponds to a prefix of the key.

Exact-match lookups are normal O(1) hash map lookups. Predecessor / successor searches use binary chop on the length of the key. Where a qp-trie search is O(k), where k is the length of the key, a p-fast trie search is O(log k).

This smaller O(log k) bound is why I call it a "p-fast trie" by analogy with the x-fast trie, which has O(log log N) query time. (The "p" is for popcount.) I'm not sure if this asymptotic improvement is likely to be effective in practice; see my thoughts towards the end of this note.

( Read more... )