title: Is map lookup in Elixir O(1)?
body: <p>Hash-table-based dict/map structures provide <code>O(1)</code> lookup time. Yet I keep seeing implications that in Elixir, finding a matching function head is faster than looking up something in a map.</p>
  
  <p>For instance, Elixir's <code>String.Unicode</code> <a href="https://github.com/elixir-lang/elixir/blob/5f276918ac6505693c7adca31d95e24d480f0869/lib/elixir/unicode/unicode.ex#L71-L79" rel="noreferrer">compiles a list of unicode characters into many function heads</a>, so that asking "what's the upcase version of é" is answered by finding the function head for <code>upcase</code> that expects "é".</p>
  
  <p>I don't know why this would be faster or more memory efficient than having a single <code>upcase</code> function head that looks up "é" in a map.</p>
  
  <p>Similarly, when showing how to build an I18n library in "Metaprogramming Elixir", Chris McCord gives each translation key its own function head, and says:</p>
  
  <blockquote>
    <p>“By generating function heads for each translation mapping, we again let the Virtual Machine take over for fast lookup.”</p>
  </blockquote>
  
  <p><strong>Do maps in Elixir not provide O(1) lookup?</strong> Is finding a matching function head O(1)? Why opt for compiling a static list to many function heads instead of just storing it in a map?</p>