Friday, 18 April 2008

Inserting and searching in a Hashtable.

You will be having good knowledge of Data Structors if you can tell:
Which operation takes more time ? put(key,val) or get(key) ?

Think!!
Most of you will think put operation will take more time. Thinking like during put() operation JVM has to calculate the hashCode() and check for equals method. Again Hashtable does not allow duplicates so it will check that too. I was asked this question and I replied in the same way. But I didn't get the correct answer so I was not satisfied I started poll on 2 communities on JavaGuru they moderator deleted the pole :( And on another Java Community till today I got 46 polls.

get(key); 9 Votes (19%)
put(key,val); 21 Votes (45%)
Both take equal time: 16 Votes (34%)

Well I was quite puzzled by this. So I decided to do some R & D on this so what I did is :

I did for a put operation i got 1200 neno seconds more (When i did for 1000 Strings).
For one operation on String

T(put) = T(get) + 1200 neno Seconds.

When i did it for Integer wrappers i got :
T(get) = T(put) + 500 neno Seconds.

But I could not generalize.
Again I did for my userdefined class object i got almost same time for puttign and getting.
And I got

T(get) nearly = T(put)


Recently I read few things in Kathy Sierra book and another Data Structor book that :
Time taken by both the operations will depend on the hashCode() that is generated.
If hashCode is poor then get() operation will take time as the search will become almost sequential.

Both need to find the "bucket" that is appropriate for the hash of the key.
If the hash code was poor, the put would take less time as the get would have to do a linear search through the whole bucket.
But Hashtable generates 'decent code' and not poor code.

No comments: