Hash table lengths and prime numbers

This has been bugging me for some time now...
The first thing you do when inserting/retreiving from hash table is to calculate the hashCode for the given key and then find the correct bucket by trimming the hashCode to the size of the hashTable by doing hashCode % table_length. Here are 2 statements that you most probably have read somewhere

• If you use a power of 2 for table_length, finding (hashCode(key) % 2^n ) is as simple and quick as (hashCode(key) & (2^n -1)). But if your function to calculate hashCode for a given key isn't good, you will suffer from clustering of many keys in a few hash buckets.

• If you use prime numbers for table_length, hashCodes calculated could map into the different hash buckets even if you have a slightly stupid hashCode function.

Ok, but why? Today I think I found out why...if u think I'm wrong put in a comment, at least for the sake of others reading this blog.

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, where m = table_length/GreatestCommonFactor(table_length, x). (It is trivial to verify/derive this). Now you can do one of the following to avoid clustering

• Make sure that you don't generate too many hashCodes that are multiples of another hashCode like in {x, 2x, 3x, 4x, 5x, 6x...}.But this may be kind of difficult because you have to come up with a perfect hashCode function.

• Or simply make m equal to the table_length by making GreatestCommonFactor(table_length, x) equal to 1, i.e by making table_length coprime with x. And if x can be just about any number then make sure that table_length is a prime number.

Update:
"Wangchun Li" pointed outed out in the comments to "CLRS theorem 31.20". Need to take a look at it.

Brahmagiri trek

Five of us kunta, subbu, dinga, biter and myself left for brahmagiri last friday afternoon with banglaore still limping back to normalcy after the riots. We had intially planned a overnight camp @ tadiandamol which didn't workout...for good as there were thunderstorms that night and we planned to carry only sleeping bags...no tents.
First stop @ Balmuri (we accidentally discovered we were close to this place) ...amazing place to enjoy water...and guess what... yours truly saved someone who was about to drown in filmi style (must confess he wasn't too far from safety although his family was panicky)...learned a lesson or 2 myself.

Evening@Balmuri...Every cloud has a silver lining



Halt for the night @ hunsur...almost zero sleep...woke up @4 in the morning and headed towards nagarhole.

Well if the forest dept wishes you a wild journey then you know what to expect right


Sunrise in nagarhole national park


Kunta @ the elephant camp


As Dinga said Deers in nagarhole are as common as dogs in bangalore


Drive thru' nagarhole


Start of trek near iruppu falls


Nice prose


The last mile before reaching the narimale camp at the top


Leech bite on my leg. Bloody leeches (no pun intended) have both a local anasthetic and anti-clogging agent in their saliva


Mahishaasura


Caves a top brahmagiri


A lone banana tree @ kerala-karnataka border


Bussss naga


A very good morning after a chilly night spent in fear of rats, leeches and tolerating subbu's innovative ways of snoring







Dinga's flying high


Blown away


Washing the dishes after cooking MTR puliyogare, noodles and bisibelebath using dry wood from the forest and water from streams


Mission Complete


Driving back to blr on the truly amazing mysore road


Me and kunta near a paddy field in mandya i guess

HOLI

The festival of colors is here...if u don't believe me..come down to bangalore... The Trees in bangalore have begin to shed their leaves and fill themselves completely with flowers in yellow, red, magenta, purple...i have put a task upon myself to capture all of them digitally and post it here as soon as possible. You must see to believe that some of these trees have no leaves at all and look like trees of gold with all the thick blooms of yellow. One week later... Finally got up at 5:30am in the morning to make time in my busy schedule and took some snaps. Looking at these trees,its pretty obvious when you look around that its a new beginning and it teases you to wear a fresh look - no wonder march was the beginning of new year and still is so in india. Making a resolution at this moment and fulfilling it is so much easier... There are about 4000 such trees of gold in bangalore according to deccan herald. Altough all of them look similar, there must be atleast 3 varieties of them when u take a closer look at the flowers. and one of them is supposed to be tabebuia argentia What are you doing here reading this blog...get ur bum off that chair...remove ur shoes and welcome the spring with 'wind in ur hair and sand at ur feet'. One more week later....