Simple hashing

[Maya]

Hello all,

I'm using MD5 hashing in my application to give unique values to huge
list of items my application receives, originally every item's name was

difficult to use as an id for this item although its unique but because

it had certain characters and variable lengths I ended up using MD5
hashing of the name.


My question: is there a simpler way of doing hashing than MD5 which is
32bit but still guarantee uniqueness for almost 10 billion records?


Thank you.


Maya.

 

[Laura T]

There are many.. but with a guarantee for 10 billion records...
Just an example, a 32 bit hash may generate 2^32 unique hash values.
If you have 30 byte key, you will get 2^240 possibile keys mapped to 2^32
unique has values.
That leaves you about 2^208 possible keys for one hash value.. it's quite
impossible to not have collisions.

You could check FNV hash at http://www.isthe.com/chongo/tech/comp/fnv/
I've used it for a sometime and it's fast and quite simple.
It's good for small strings also, but AFAIK there is collision analysis for
it.

Also a simple CRC32 could be (re)considered. Empiric tests show that a CRC32
with 18M data has
about 38000 collisions. CRC48 almost none. But everything depends on your
data.

Here you can find others hashing functions with examples:

http://eternallyconfuzzled.com/tuts/hashing.html

 

[rossum]

Hello all,

I'm using MD5 hashing in my application to give unique values to huge
list of items my application receives, originally every item's name was

difficult to use as an id for this item although its unique but because

it had certain characters and variable lengths I ended up using MD5
hashing of the name.


My question: is there a simpler way of doing hashing than MD5 which is
32bit but still guarantee uniqueness for almost 10 billion records?


Thank you.


Maya.

You don't say if you are using MD5 for security reasons. Both MD2 and
MD4 are broken in security, but they are both simpler and faster then
MD5.

There are a large number of non-cryptographic hashes around, FNV
(http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash) and others, which
are much simpler and much faster but are not cryptographically secure.
If collision avoidance is important to you then you may need to do a
test to see how collision prone any possible replacement is. FNV has
a number of sizes, including 128 bit and 256 bit. The 256 bit size
should be collision free, even if the 128 bit hash fails the test.

To reiterate, MD2, MD4 and FNV are *not* cryptographically secure. If
security is involved you need to stick with MD5 or upgrade to SHA-1
or better.

rossum

 

[Rick Lones]

Hello all,

I'm using MD5 hashing in my application to give unique values to huge
list of items my application receives, originally every item's name was

difficult to use as an id for this item although its unique but because

it had certain characters and variable lengths I ended up using MD5
hashing of the name.


My question: is there a simpler way of doing hashing than MD5 which is
32bit but still guarantee uniqueness for almost 10 billion records?

This is like saying you want to take the numbers from 1 to 100 and assign each a
unique hash code from 1 to 10 - it can't be done. 32 bits can represent at most
around 4 billion numbers. It would take 34 bits to even count your 10 billion
records. So uniqueness is not even theoretically possible here.

HTH,
-rick-

 

[Fabio]

My question: is there a simpler way of doing hashing than MD5 which is
32bit but still guarantee uniqueness for almost 10 billion records?

There is no guarantee that an hashing algorithm produces unique results.
You can be (really) unluky and get the same MD5 for just only 2 records.

 

[gujarsachin2001]

http://www.fastsum.com/support/md5-checksum-utility-faq/md5-hash.php

 

[Adam Clauss]

My question: is there a simpler way of doing hashing than MD5 which is
32bit but still guarantee uniqueness for almost 10 billion records?

Maya,
Actually - I'm pretty sure an MD5 is actually 128-bit, not 32bit. Most visual representations of it are 32 DIGIT. But those digits
are hexadecimal - hence 128-bit. 2^128 is huge... far higher than 10 billion.

 

[Guest]

You could try using something like this, and just increase the maxSize to a
point where you get a key of sufficient length:

public static string GetUniqueKey()
{
int maxSize = 8;
char[] chars = new char[62];
string a;
a = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
chars = a.ToCharArray();
int size = maxSize;
byte[] data = new byte[1];
RNGCryptoServiceProvider crypto = new RNGCryptoServiceProvider();
crypto.GetNonZeroBytes(data);
size = maxSize;
data = new byte[size];
crypto.GetNonZeroBytes(data);
StringBuilder result = new StringBuilder(size);
foreach (byte b in data)
{ result.Append(chars[b % (chars.Length - 1)]); }
return result.ToString();
}
--Peter

 

[Maya]

Thank you guys, this was very useful to me.

Maya.

You could try using something like this, and just increase the maxSize to a
point where you get a key of sufficient length:

public static string GetUniqueKey()
{
int maxSize = 8;
char[] chars = new char[62];
string a;
a = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
chars = a.ToCharArray();
int size = maxSize;
byte[] data = new byte[1];
RNGCryptoServiceProvider crypto = new RNGCryptoServiceProvider();
crypto.GetNonZeroBytes(data);
size = maxSize;
data = new byte[size];
crypto.GetNonZeroBytes(data);
StringBuilder result = new StringBuilder(size);
foreach (byte b in data)
{ result.Append(chars[b % (chars.Length - 1)]); }
return result.ToString();
}
--Peter
--
Co-founder, Eggheadcafe.com developer portal:
http://www.eggheadcafe.com
UnBlog:
http://petesbloggerama.blogspot.com

Hello all,

I'm using MD5 hashing in my application to give unique values to huge
list of items my application receives, originally every item's name was

difficult to use as an id for this item although its unique but because

it had certain characters and variable lengths I ended up using MD5
hashing of the name.


My question: is there a simpler way of doing hashing than MD5 which is
32bit but still guarantee uniqueness for almost 10 billion records?


Thank you.


Maya.