3.3 Hash Tables

• An extremely effective and practical way of implementing dictionaries.
• O(1) time for search, insert, and delete in the average case.
• O(n) time in the worst case; by careful design, we can make the probability that more than constant time is required to be arbitrarily small.

• Hash Tables
  • Open or External
  • Closed or Internal