itech9

From http://techinterviewcoach.com/blog/?p=30#more-30

• Hash tables are backed by arrays.
• A hash function is used to map the keys to an index within the backing array.
• Put, Get, Delete operations all run in constant ( O(1) ) time.
• Hash function determines performance.
• Even with the best hash function, collisions can occur.
• Main advantage of HTs over other data structures is speed.
• Growing HTs need to be rehashed but the cost is amortized by constant cost of ‘put’.
• Should not use HTs for small data sets, but everybody does.
• Rehashing should occur when the load factor (occupied array slots / array size) reaches over .75.