Re: Hash Code

From:

"Kenneth P. Turvey" <kt-usenet@squeakydolphin.com>

Newsgroups:

comp.lang.java.programmer

Date:

20 May 2008 20:27:45 GMT

Message-ID:

<48333440$0$2963$ec3e2dad@news.usenetmonster.com>

On Tue, 20 May 2008 15:36:11 -0400, Eric Sosman wrote:

j1mb0jay wrote:

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. [...]

It depends on how you define "best." Think of it as an
ordinary purchase-and-sale transaction: Expanding the table is an
investment of CPU time today in hopes of recouping it and more tomorrow.
For the same table with the same sequence of insertions, deletions, and
searches, the investment could be "good" or "bad" depending on other
circumstances.

[Snip]

I should admit that I've sinned here. I've used the bits of a SHA1 hash
to generate a hash code. Why? Because it was simple to implement and a
very good hash and the code that I was writing was disposable. I just
wanted it to run, I didn't really want to think about it.

That said, I would never do this in code I cared about. It is simply too
expensive and it would be difficult to find a real problem where it would
make sense and a checksum wouldn't.

--
Kenneth P. Turvey <kt-usenet@squeakydolphin.com>