jonnifyelixir
F4 / F4.05 / indexing

F4.05 · part 2 of 3

Hash-prefix indexing

A flat table reduced the whole hash to one slot with a single modulo. A trie reads the hash in pieces: five bits choose a slot at the root, the next five choose a slot in that child, and so on down. Each five-bit chunk picks one of 32 slots, so a key’s path is its hash, read five bits at a time, until it reaches a leaf.

Descending on the registry key "/elixir/algorithms/maps", whose phash2 is the same 48721903 from F4.04. Select a level to see which bits it reads.

Five bits at a time Advanced: depth and collisions

Five bits at a time

The hash is a fixed integer; the trie consumes it in five-bit chunks from the low end. Level 0 reads bits 0–4, level 1 reads bits 5–9, and so on, each chunk naming a slot in the current node. A lookup repeats the same chunking and follows the same path. Select a level.

The level · select one

phash2("/elixir/algorithms/maps") = 48721903 5-BIT CHUNKS OF THE HASH (low bits first) bits 0–4 15 bits 5–9 31 bits 10–14 27 root · slot 15 node · slot 31 node · slot 27 leaf => %Page{} depth ≈ log₃₂ n 5 hash bits per level 32 = 2⁵ slots per node level 0 reads bits 0–4 = 15 — the root slot 

      

      
role: a hash chunk to a slot

      
result: level 0 → slot 15

    

    
A key’s path is its hash, read five bits per level. Because each step is a constant-time slot
      pick and the tree is about four levels deep for millions of keys, the whole descent is treated as O(1).

  


  

    
Advanced: depth and collisions

    

      
Five bits per level means a node has 32 slots and the depth is about log₃₂ n:
        roughly four levels for millions of keys, six for a 32-bit hash spread fully. Two different keys can share a
        path for a while — their hashes agree in the low bits — and they split at the first level whose
        chunk differs. Two keys with the same full hash are a true collision; the trie keeps them together in
        a small collision node at the bottom, searched directly, which stays cheap because it is rare. As before, a
        map with at most 32 keys skips the tree and stays a flat sorted array; it grows into a trie only when it must.

      
Any term can be a key, so the course’s branded Snowflake ids index the same way: a
        PGE id hashes to an integer and walks the tree by five-bit chunks, the same way a
        route string does. That is what lets the page registry key its entries on a stable, cross-runtime id and still
        get the trie’s shallow lookup.

    

    
import Bitwise

# the slot at a given level = a five-bit chunk of the hash
def slot_at(hash, level) do
  (hash >>> (5 * level)) &&& 0b11111   # 0b11111 = 31, a 5-bit mask
end

# slot_at(48721903, 0) = 15 · slot_at(48721903, 1) = 31 · slot_at(48721903, 2) = 27
# descend root -> 15 -> 31 -> 27 -> leaf; depth grows as log32 n

    

      

        
F4.04 · one chunk, one flat slot

        
A single modulo turns the hash into one index in one table.

      

      
      

        
F4.05.2 · many chunks, a path

        
Five bits per level walk the hash down the tree until they reach a leaf.

      

    

    
Next: structural sharing — what
      happens to this path when you insert a key, and why the old map survives unchanged.

  


  

    
References

    
Primary sources for this lesson, and where it connects in the course.

    

      
Sources

      
      
Related in this course