jonnifyelixir
F4 / F4.04 / hashing

F4.04 · part 3 of 3

Hashing & collisions

Both a map lookup and a set membership test rest on the same trick: a hash function turns a key into an integer, the integer picks a slot, and the value lives there — no scanning, so the cost does not grow with the collection. When two keys pick the same slot, that is a collision, resolved in place. Elixir’s term hash is :erlang.phash2.

Hashing the route "/elixir/algorithms/maps" to a slot, and watching a second key collide with it. Select a step.

Key, hash, slot Advanced: the 32-way HAMT

Key, hash, slot

The key is hashed to a large integer; reducing that modulo the number of slots gives an index. Lookups repeat the computation and go straight to the slot. Two distinct keys can land together — both are kept and the slot is searched, which stays cheap as long as collisions are rare. Step through it.

The step · select one

"/elixir/algorithms/maps" "/elixir/algorithms/sorting" → phash2 term hash → 48721903 rem 8 BUCKETS [0] [1] [2] [3] [4] [5] [6] [7] phash2 maps the key to an integer 

      

      
role: any term to an integer

      
result: 48721903

    

    
Hash, reduce, place: the same three steps on every read and write, independent of how many keys
      exist. Collisions are inevitable once there are more keys than slots, so a real implementation grows the table
      and keeps the average bucket short — which is where the HAMT comes in.

  


  

    
Advanced: the 32-way HAMT

    

      
A single modulo table would need resizing and could degrade if many keys collide. Elixir instead stores a
        large map as a hash array mapped trie: a tree that consumes the key’s hash a few bits
        at a time, branching up to 32 ways at each level. Five bits choose one of 32 children, the next five choose
        the next, and so on, so the depth is about log₃₂ n — roughly
        four levels for millions of keys, which is why lookup is treated as O(1). Small maps skip the tree and stay a
        flat sorted array until they outgrow 32 keys.

      
Any term can be a key, so the course’s branded Snowflake ids work directly: a 64-bit integer rendered
        as base62 with a namespace prefix, it hashes like any other key, and it stays stable as a pivot across the
        BEAM, Node, and Go runtimes that share the queue. That persistent 32-way trie is the whole of F4.05.

    


    

      
A map as a 32-way trie on the key’s hash

      
        ROOT · 32 slots
        
          
          
          
          
          … (32)
        
        5
        
        
        bits 0–4 of hash

        NODE · 32 slots
        
          
          
          
          … (32)
        
        9
        
        
        bits 5–9 of hash

        
        leaf: "/elixir/algorithms/maps" => %Page{}

        
        depth ≈ log₃₂ n
        5 hash bits per level
        32 = 2⁵ children per node
        ~4 levels for millions of keys
        so lookup is treated as O(1)
        small map (≤32): flat array
        F4.05 builds this trie
      
    


    
:erlang.phash2("/elixir/algorithms/maps")     # => 48721903   (a term hash)
:erlang.phash2("/elixir/algorithms/maps", 8)  # => 7          (bounded to one of 8 slots)

# a branded Snowflake id is a term like any other — it hashes and keys the same
%{} |> Map.put("PGE0NbWMtkolM0", page)  # PGE = page namespace

# small map (<= 32 keys): flat sorted array
# large map: a 32-way HAMT keyed by chunks of the hash, depth ~ log32 n

    

      

        
F4.04 · a good hash spreads keys across slots

        
The hash sends each key to a slot; collisions stay rare.

      

      
      

        
F4.05 · the 32-way HAMT

        
Elixir stores the entries in a persistent hash array mapped trie — the chapter spine.

      

    

    
That completes F4.04: a map looks up a value by key, a set tests membership, and a hash makes
      both constant-time. Next module: F4.05 — Hash Array Mapped Tries (HAMT),
      which builds the 32-way trie sketched above — the start of the persistent-map spine that leads to CHAMP
      and the branded-CHAMP map.

  


  

    
References

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

    

      
Sources

      
      
Related in this course