By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
444,041 Members | 1,056 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 444,041 IT Pros & Developers. It's quick & easy.

Hash table

P: n/a
Hello,

Does anyone has to face the problem of hashing a string of 12 characters
AND avoid any collision?

I'm looking for some algorithm who could return a good (small) hash
value for any string of 12 characters.

Do you have any idea?

Marty
Nov 21 '05 #1
Share this Question
Share on Google+
7 Replies


P: n/a
Marty <re***@to.forum> wrote:
Does anyone has to face the problem of hashing a string of 12 characters
AND avoid any collision?

I'm looking for some algorithm who could return a good (small) hash
value for any string of 12 characters.


For 12 characters to have a non-colliding hash, you'll need more than
24 bytes of hash. There are various ways of making it non-colliding -
an identity hash would do, to start with, if your one goal is to avoid
collisions. You obviously can't have a shorter hash and have no
collisions - there are too many strings and not enough possible hash
values! The point of a hash is usually to take a large amount of data
and hash it into a smaller value which is *unlikely* to collide with
that created by a different chunk of source data - but once you specify
that collisions mustn't occur at all, hashing just doesn't work as a
concept.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 21 '05 #2

P: n/a
Thanks Jon,

Ok, I can handle collisions. Where can I look to learn this identity
hash algorithm?

Regards,

Marty
Jon Skeet [C# MVP] wrote:
Marty <re***@to.forum> wrote:
Does anyone has to face the problem of hashing a string of 12 characters
AND avoid any collision?

I'm looking for some algorithm who could return a good (small) hash
value for any string of 12 characters.

For 12 characters to have a non-colliding hash, you'll need more than
24 bytes of hash. There are various ways of making it non-colliding -
an identity hash would do, to start with, if your one goal is to avoid
collisions. You obviously can't have a shorter hash and have no
collisions - there are too many strings and not enough possible hash
values! The point of a hash is usually to take a large amount of data
and hash it into a smaller value which is *unlikely* to collide with
that created by a different chunk of source data - but once you specify
that collisions mustn't occur at all, hashing just doesn't work as a
concept.

Nov 21 '05 #3

P: n/a
Marty <re***@to.forum> wrote:
Ok, I can handle collisions.
In that case I suggest you use String.GetHashCode(), which should be
fine.
Where can I look to learn this identity hash algorithm?


That was sort of a joke. It's a "hash algorithm" which doesn't change
the data at all - your 12 characters end up as 24 bytes, maybe with a
25th being the length (and 0 padding if the length is less than 12
characters). It's not useful as a hash algorithm, trust me.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too
Nov 21 '05 #4

P: n/a
That was sort of a joke. It's a "hash algorithm" which doesn't change
the data at all - your 12 characters end up as 24 bytes, maybe with a
25th being the length (and 0 padding if the length is less than 12
characters). It's not useful as a hash algorithm, trust me.


Ok I see, as you said it is not useful. I'll go ahead with the
string.getHash ...

Have a nice day! :)

Marty

Nov 21 '05 #5

P: n/a
From what I recall, make your hash table size like this:
find the lowest prime number greater than 2*n (where n is number of
elements)
Then use quadratic collision handling.

"Marty" <re***@to.forum> wrote in message
news:oX6Vc.39819$fz2.1697@edtnps89...
Hello,

Does anyone has to face the problem of hashing a string of 12 characters
AND avoid any collision?

I'm looking for some algorithm who could return a good (small) hash
value for any string of 12 characters.

Do you have any idea?

Marty

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.732 / Virus Database: 486 - Release Date: 7/29/2004
Nov 21 '05 #6

P: n/a
Tom
If you can't have a collision at all you need a different algorythim.
Use a LMV or a CRC32 Checksum if the default GetHashCode is not good
enough. Otherwise use a MD5 or SHA has if you are parnoid about
collsions. However they still can happen so you still need to take
that into consideration.
Nov 21 '05 #7

P: n/a
Finally I've handled the collisions. I've been using the getHashCode
wich I applied another transformation wich give me a small hash key.

I'm curious about the algorithm that you specified, I'll have a look.

Thanks you!
Marty

Tom wrote:
If you can't have a collision at all you need a different algorythim.
Use a LMV or a CRC32 Checksum if the default GetHashCode is not good
enough. Otherwise use a MD5 or SHA has if you are parnoid about
collsions. However they still can happen so you still need to take
that into consideration.

Nov 21 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.