Hash table

  • Thread starter Thread starter Marty
  • Start date Start date
M

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
 
Marty said:
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.
Click to expand...

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.
 
Thanks Jon,

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

Regards,

Marty
 
Marty said:
Ok, I can handle collisions.
Click to expand...

In that case I suggest you use String.GetHashCode(), which should be
fine.
Where can I look to learn this identity hash algorithm?
Click to expand...

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.
 
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.
Click to expand...

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

Have a nice day! :)

Marty
 
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.
 
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.
 
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
 
Back
Top