"that most engineers need to know that a hash table is O(c) lookup" O(1) is a leaky abstraction [1]. It's O(1) amortized assuming you have enough buckets and a

"that most engineers need to know that a hash table is O(c) lookup" O(1) is a leaky abstraction [1]. It's O(1) amortized assuming you have enough buckets and a good hashing algorithm that minimizes collisions. I think that distinction important to keep in your head, and good to mention/look for in interviews, since those details matter when things go awry. [1] http://www.joelonsoftware.com/articles/LeakyAbstractions.html http://www.joelonsoftware.com/articles/LeakyAbstractions.htm...