0

I read in an article which says:

It is a common practice to recommend a prime number to be the size of a hash table. This way, a funnel will occur only if the keys are multiples of the prime number.

Here, why should a prime number be used for the initial size, and what is funnelling?

Rekha
  • 1,403
  • 3
  • 12
  • 21

2 Answers2

2

Long answer: here

Short answer:
A funnel occurs when 2+ keys get hashed to the same value because of an error with the underlying hashing function. Like this:

Map<String,Object> myMap = new HashMap<String,Object>();
Thing thing1, thing2;
thing1 = new Thing();
thing2 = new Thing();

myMap.put("ab", thing1);
myMap.put("ba", thing2);

If there is an inherent flaw in the hashing function used by HashMap<K,V>, a "funnel" could occur where the keys ab and ba both map to, say, thing1.

Think of a funnel as an actual funnel: multiple inputs get funneled into the same place.

Edit
If a hash function is flawed and does contain funnels, then a way to minimize their occurrence is to set the size of the table to being a prime number.

This is because, in terms of being a "class" (category) of numbers, prime numbers have the least amount of factors. According to that article, funnels occur when a given key is a factor or multiple of the size of the table. So if we set the table size to 100 (not a prime number), we introduce the possibility of funneling when the provided key is any factor of 100: 1, 2, 4, 5, 10, ..., 100, 200, 300, etc.

But if we make the size of the table to a prime, say, 101... then the only possibility of a funnel occurs at: 1, 101, 202, 302, etc. We've greatly reduced the possibility of a funnel.

IAmYourFaja
  • 55,468
  • 181
  • 466
  • 756
  • i liked the first part of your answer....but link is too complex to understand....can you explain it... – Rekha Dec 20 '11 at 18:21
  • Please see my edit explaining primes. Also the article is (probably) graduate level, and I'm just mere JEE developer with a bachelors degree! My original explanation of what a funnel is and how it occurs should be enough to give you the general idea though. Good luck! – IAmYourFaja Dec 20 '11 at 18:45
  • What is the difference between a funnel and a collision? Aren't collisions inevitable in hashing systems (but can be made improbable). – emory Dec 20 '11 at 20:31
0

I think to protect the keys to sit in proper place Hash table and you can look into funnelling http://burtleburtle.net/bob/hash/evahash.html#funneling

Ramakanth77
  • 99
  • 4