Jump to content
  • Advertisement
Sign in to follow this  
PrestoChung

Is this hashing?

This topic is 2915 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was introduced to an example of hashing in
" target=blank>this video
An example of persistent 'random' game is worlds where you have some 'coordinate' system that is used to look-up the content with seeded random numbers.

Is the function that takes the coordinate as the argument considered a 'hash function'? Does that make the coordinate the 'key' or the return of the function the key?

Share this post


Link to post
Share on other sites
Advertisement
That's a long video and you didn't specify any specific spot in the video but I'm going to assume the coordinate is the key. However, generally when I see a hash function being used, its designed to work with a string as a key. The key should be something expected to be unique to itself. The idea is to get a different hash value with each key if possible. If not, there's ways to handle that too. But the less key's which produce the same value, the better.

So yes, the function which takes in the coordinate is likely to be the hash function
Coordinates are likely to be the key
return of the function is likely to be a hash value

From my personal experience, some good hash functions are
SDBM, RS, AP

Here's the actual hash functions for those I mentioned above plus many more

unsigned int RSHash(const std::string& str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = hash * a + str;
a = a * b;
}

return hash;
}
/* End Of RS Hash Function */


unsigned int JSHash(const std::string& str)
{
unsigned int hash = 1315423911;

for(std::size_t i = 0; i < str.length(); i++)
{
hash ^= ((hash << 5) + str + (hash >> 2));
}

return hash;
}
/* End Of JS Hash Function */


unsigned int PJWHash(const std::string& str)
{
unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4);
unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);
unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = (hash << OneEighth) + str;

if((test = hash & HighBits) != 0)
{
hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}

return hash;
}
/* End Of P. J. Weinberger Hash Function */


unsigned int ELFHash(const std::string& str)
{
unsigned int hash = 0;
unsigned int x = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = (hash << 4) + str;
if((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
}
hash &= ~x;
}

return hash;
}
/* End Of ELF Hash Function */


unsigned int BKDRHash(const std::string& str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = (hash * seed) + str;
}

return hash;
}
/* End Of BKDR Hash Function */


unsigned int SDBMHash(const std::string& str)
{
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = str + (hash << 6) + (hash << 16) - hash;
}

return hash;
}
/* End Of SDBM Hash Function */


unsigned int DJBHash(const std::string& str)
{
unsigned int hash = 5381;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = ((hash << 5) + hash) + str;
}

return hash;
}
/* End Of DJB Hash Function */


unsigned int DEKHash(const std::string& str)
{
unsigned int hash = static_cast<unsigned int>(str.length());

for(std::size_t i = 0; i < str.length(); i++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ str;
}

return hash;
}
/* End Of DEK Hash Function */


unsigned int BPHash(const std::string& str)
{
unsigned int hash = 0;
for(std::size_t i = 0; i < str.length(); i++)
{
hash = hash << 7 ^ str;
}

return hash;
}
/* End Of BP Hash Function */


unsigned int FNVHash(const std::string& str)
{
const unsigned int fnv_prime = 0x811C9DC5;
unsigned int hash = 0;
for(std::size_t i = 0; i < str.length(); i++)
{
hash *= fnv_prime;
hash ^= str;
}

return hash;
}
/* End Of FNV Hash Function */


unsigned int APHash(const std::string& str)
{
unsigned int hash = 0xAAAAAAAA;

for(std::size_t i = 0; i < str.length(); i++)
{
hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str * (hash >> 3)) :
(~((hash << 11) + (str ^ (hash >> 5))));
}

return hash;
}
/* End Of AP Hash Function */

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!