Hash table

[Marty]

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

[Jon Skeet [C# MVP]]

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

[Marty]

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.

[Jon Skeet [C# MVP]]

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

[Marty]

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

[Hal Rosser]

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

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

[Marty]

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.