On Tue, 20 May 2008 18:14:11 +0000, Kenneth P. Turvey wrote:
On Tue, 20 May 2008 18:48:15 +0100, j1mb0jay wrote:
Would this mean there would be no collisions thus keeping the time
complexity of the search method down to O(1). In turn meaning the hash
table could be an array of Key Value pairs rather than a array of
linked lists.
No. There could still be collisions. In addition, the time it would
take to calculate a hash would be significant, meaning the performance
of the algorithm would degrade.
Just to be clear, if you are trying to map something with
2,000,000,000,000 possible values to a hash table with 200 entries,
there is simply no way to avoid collisions. Sometimes the data will
simply collide.
I understand that this would be the case but I have to say that i was
told as part of the module that re-hashing the whole table into a new
table with a higher table size is the best option. This is of course
expensive in terms of CPU time. I think the java hash map does that at
0.75 (when 75% of the table is full) by default.
Yes i understand that the hash it self would also be intensive if using
SHA512 but this number is 16 times bigger than the output of a
String.hashCode() function.