Author: techfox9

Hash table notes..

Wednesday, August 26th, 2009 @ 1:58 am


  • 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.

Engineering, Java, JavaUsage, Software


Comments are closed.