• Both chaining and open addressing asssume uniform hashing

chaining

  • unsuccessful search (search到chain的最後面)
  • successful search(找chain中排在前面的個數)

Open addressing

  • unsuccessful search
  • insert 的cost(insert最壞就是unsuccessful search)
  • successful search