# p-fast trie: lexically ordered hash map

DevFeed: [p-fast trie: lexically ordered hash map](<https://devfeed.tech/articles/p-fast-trie-lexically-ordered-hash-map-36219.md>)

Original publisher: [Read original article](<https://dotat.at/@/2025-08-04-p-fast-trie.html>)

Published: 2025-08-04T20:52:21Z

Content type: article

Language: en

Sources: [Tony Finch's blog](<https://devfeed.tech/sources/tony-finch-s-blog.md>)

Topics: [hash](<https://devfeed.tech/topics/hash.md>), [Query (disambiguation)](<https://devfeed.tech/topics/query.md>), [Rust](<https://devfeed.tech/topics/rust.md>)

Tags: [array](<https://devfeed.tech/tags/array.md>), [bits](<https://devfeed.tech/tags/bits.md>), [hash](<https://devfeed.tech/tags/hash.md>), [map](<https://devfeed.tech/tags/map.md>), [maps](<https://devfeed.tech/tags/maps.md>), [query](<https://devfeed.tech/tags/query.md>)

## AI overview

This article sketches the p-fast trie, a proposed lexically ordered hash map that replaces a qp-trie's tree and interior pointers with stratified hash-map levels keyed by prefixes. It describes O(1) exact-match lookups and O(log k) predecessor and successor searches, while noting that the practical benefit is uncertain.

## Source excerpt

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. layout A p-fast trie consists of: Leaf objects, each of which has a name. Each leaf object refers to its successor forming a circular linked list. (The last leaf refers to the first.) Multiple interior nodes refer to each leaf object. A hash map containing every (strict) prefix of every name in the trie. Each prefix maps to a unique interior node. Names are treated as bit strings split into chunks of (say) 6 bits, and prefixes are whole numbers of chunks. An interior node contains a (1<<6) == 64 wide bitmap with a bit set for each chunk where prefix+chunk matches a key. Following the bitmap is a popcount-compressed array of references to the leaf objects that are the closest predecessor of the corresponding prefix+chunk key. Prefixes are strictly shorter than names so that we can avoid having to represent non-values after the end of a name, and so that it's OK if one name is a prefix of another. The size of chunks and bitmaps might change; 6 is a guess that I expect will work OK. For restricted alphabets you can use something like my DNS trie n