title: Why is python's dict implemented as hash table whereas std::map is tree-based?
body: <p>Why one languages uses tree and another uses hash table for seemingly similar data structure?</p>
  
  <p>c++'s map vs python's dict</p>
  
  <p>A related question is about performance of hash table.<br>
  Please comment on my understanding of hash table below.  </p>
  
  <p>A tree is guaranteed to have O(log n).<br>
  Whereas hash table has no guarantee unless inputs are previously known because of possible collisions.<br>
  I tend to think hash table's performance would become close to O(n) as problem size gets bigger.<br>
  Because I haven't heard of a hash function that dynamically adjust its table size as problem size grows.   </p>
  
  <p>Hence, hash table is only useful for certain range of problem size, and that's why most DB uses tree than hash table.</p>