Saturday, January 10, 2009

Back of the envelope computation: how large should be an hash table?

Jon Bentley's More Programming Pearls: Confessions of a Code has a nice chapter about back of the envelope computations. It is amazing how many people are having difficulties with simple math, while they know about algorithms and design patterns. So here is one simple problem:
  • You have a collection of 50Millions words and you want to hash them into an hash table. How large the hash table should be?
More problems to follow.

1 comment:

  1. how do you calculate the size of hashtable here? I am struggling with it. any hints?