Ideal Hash Trees
📜 Abstract
Hash Trees with nearly ideal characteristics are described. These Hash Trees require no initial root hash table yet are faster and use significantly less space than chained or double hash trees. Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches. Array Mapped Tries(AMT), first described in Fast and Space Efficient Trie Searches, Bagwell [2000], form the underlying data structure. The concept is then applied to external disk or distributed storage to obtain an algorithm that achieves single access searches, close to single access inserts and greater than 80 percent disk block load factors. Comparisons are made with Linear Hashing, Litwin, Neimat, and Schneider [1993] and B-Trees, R.Bayer and E.M.McCreight [1972]. In addition two further applications of AMTs are briefly described, namely, Class/Selector dispatch tables and IP Routing tables. Each of the algorithms has a performance and space usage that is comparable to contemporary implementations but simpler.
✨ Summary
Technical contribution
The paper introduces Hash Array Mapped Tries (HAMTs), combining hashing with Array Mapped Tries. A key is hashed, and successive groups of hash bits select levels of a trie. Each trie node uses a bitmap to identify occupied positions and a compact array containing only the corresponding non-empty entries. This avoids allocating a full array of pointers at every node while preserving direct indexing and good cache locality. With a 32-way branching factor, five hash bits are consumed at each level, and population-count operations locate entries in the compact arrays.
The proposed in-memory structure supports search, insertion, and deletion. Collisions are resolved by extending the trie with additional levels; if the available hash bits are exhausted, the key is rehashed using the trie level. Lazy resizing of the root table reduces the growth cost, while pooled allocation and incremental defragmentation control memory overhead. The paper reports near-constant measured operation times over key sets ranging from thousands to millions of entries, with space usage dependent on the root-table resize factor. It also describes a fallback using the complete key to guarantee a bound proportional to key length when hash differentiation takes unusually long.
The paper further proposes Partition Hashing for external and distributed storage. Buckets are divided according to hash-order partition points, and neighboring buckets can share records before a split is required. Simulations report one-access searches, approximately 1.1 accesses per insertion at load factors above 80 percent, and higher load factors when additional insertion accesses are accepted. The same partition-table approach is extended to distributed files, ordered storage, IP routing, and class-selector method dispatch.
Influence on later research and industry
HAMT became a foundational design for persistent associative maps and sets. Later implementations adapted Bagwell’s mutable structure using path copying and structural sharing; this approach is used in Clojure’s persistent hash maps and in persistent collection implementations associated with Scala. (en.wikipedia.org)
Subsequent research refined the representation for immutable JVM collections. The CHAMP structure, described as a compressed hash-array mapped prefix tree, targets lower memory use and faster iteration and equality operations; Scala’s immutable HashMap identifies itself as a CHAMP implementation and cites that work. (ir.cwi.nl)
The HAMT design has also been incorporated into systems-oriented software. The IPLD HashMap specification uses a HAMT-based layout and combines it with CHAMP mutation and canonicalization rules for content-addressed storage. CPython’s source includes an internal HAMT implementation for immutable dictionary operations. (ipld.io)
Thus, the paper’s principal lasting impact is the use of bitmap-compressed hash tries as a practical implementation technique for memory-efficient, persistent, and distributed associative collections.