Skip to main content
gamedev.net
🔒 Locked

String hash code efficiency

Started by ClementLuminy Dec 9, 2008 at 2:54 PM 9 replies 2.4k views
Original Post
ClementLuminy
ClementLuminy
Hi ! I was discussing a few weeks ago with a friend of mine about how to minimize string memory allocation/de-allocation at run-time ( during a game main loop for exemple ) He told me that the solution he was using at his previous company was to compute a CRC or an Hash-Code from the string and to use this code to work with those string as often as possible ( identification, comparation and so on )... After a few thaught at the corner of my desk i decided to go that way and to use a similar approach in my engine. So i google for some time and found the following hash function for string: StringHash CString::GetHashCode() const { Int32 hash = 0; for (Int32 i = 0; i < m_Lenght; i++) { hash = hash * 31 + m_Buffer; } return hash; } Actually everything work fine, but i still have one question left : What is the percentage of chance to get the same code for two different strings ?? The strings that i'm using are mainly resources identifier, so the string length will not exceed 20 characters ... Thanks Clement Vidal
Sneftel
Sneftel
Quote:
Original post by ClementLuminy
What is the percentage of chance to get the same code for two different strings ??
It depends on how many you're hashing. See here for details and equations.
rozz666
rozz666
100%

Assuming 20 character long identifiers that consist of letters, digits, _ and / then 309485009821345068724781056 identifiers will get the same code (on average).
ClementLuminy
ClementLuminy
So it's absolutly not a good solution to use such a method apprently ...

Do you think the problem can come from my hash function ??
Is there any better for those kind of string ?

Do you know any other approach to reduce memory allocation/deallocation of string at runtime?

Thanks
Antheus
Antheus
Quote:
Original post by ClementLuminy
What is the percentage of chance to get the same code for two different strings ??

The strings that i'm using are mainly resources identifier, so the string length will not exceed 20 characters ...


Entropy of the crc is 32 bits.

As such, it can represent 2^32 unique values.

Entropy of all strings could be 8*20, but if you consider a alphanumeric alphabet, it's somewhere around 6 bits per character, so 120 bits. To be guaranteed unique crcs, you'd need 128 bit crc (or just forget the crc and just use the string as key).

Hash collisions shouldn't be a problem for small sets (tens of thousands of filenames). But when they do happen, you will need to modify the filenames.
Anon Mike
Anon Mike
The thing about string hashes is that you use them to check if two strings are not equal. It's guaranteed that if the hashes are different than so are the strings.

For testing for equality you first test for inequality with the hash (since it's super fast), then if that fails fall back to the full check.
-Mike
return0
return0
If this is for resources (i.e. 100% known keys) you should be able to perfectly hash them (worst cast O(1) lookup).

http://en.wikipedia.org/wiki/Perfect_hash_function
alvaro
alvaro
CRCs make for very good hash functions. They are fast to evaluate and they produce few collisions, compared with many other methods. They are also recommended by Donald Knuth, in case you like arguments from authority. ;)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.