title: Best persistent map implementation for prototype object system
body: <p>TLDR: What would be the best persistent unordered map implementation currently available with fast lookup and low memory footprint?</p>
  
  <p>I'm thinking about how best I could implement a prototype object system(à la Javascript or Self) within a functional language(so no hash table). Such a use case implies that lots of objects will be created, so their memory footprint should be small. Lookup should be fast(really the most significant concern). Much of the structures might be shared.</p>
  
  <p>In summary,  </p>
  
  <ul>
  <li>lookup is the most important operation  </li>
  <li>typical size is limited(i.e. in the order of 10^1)  </li>
  <li>Space complexity and memory overhead is important(i.e. minimal memory overhead, minimal space complexity for sizes in the order of 10^1).</li>
  </ul>
  
  <p>For string keys, I know of Tries and variants. Are they the best choice for those requirements?<br>
  For integer indices, I know of Haskell's IntMap(based on PATRICIA trees), but it seems to be optimized for merging. Is there something better for lookup, and given the other constraints?<br>
  Also, for generic keys which are efficiently identifiable(such as interned symbols), is the traditional balanced binary search tree the best there is? </p>
  
  <p>Is there any relevant performance concerns in such a project that I'm forgetting? </p>
  
  <p>Also, let's say I'm implementing this on top of a lisp language, such as Common Lisp, which has interned symbols supporting efficient comparison. Would it be better to use string keys and a string map, symbol keys and a symbol map, or go (presumably efficiently) from symbols to ints and use an int-indexed map? </p>
  
  <p>Thanks!</p>