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
+ 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
7 Replies

 P: n/a Marty 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 - 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 wrote:Does anyone has to face the problem of hashing a string of 12 charactersAND avoid any collision?I'm looking for some algorithm who could return a good (small) hashvalue 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 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 - 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" 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 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.