Created
September 21, 2011 20:21
-
-
Save sebclaeys/1233176 to your computer and use it in GitHub Desktop.
Majors hash function implementation in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "hash.hh" | |
HashFunc::HashFunc () | |
{ | |
} | |
HashFunc::~HashFunc () | |
{ | |
} | |
uint | |
HashFunc::ELFHash(const char* str, uint len) | |
{ | |
return this->ELFHash(str, len, 0); | |
} | |
uint | |
HashFunc::ELFHash(const char* str, uint len, uint hash) | |
{ | |
uint x = 0; | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = (hash << 4) + (*str); | |
if((x = hash & 0xF0000000L) != 0) | |
{ | |
hash ^= (x >> 24); | |
} | |
hash &= ~x; | |
} | |
return hash; | |
} | |
uint | |
HashFunc::RSHash(const char* str, uint len) | |
{ | |
return this->RSHash(str, len, 0); | |
} | |
uint | |
HashFunc::RSHash(const char* str, uint len, uint hash) | |
{ | |
uint b = 378551; | |
uint a = 63689; | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = hash * a + (*str); | |
a = a * b; | |
} | |
return hash; | |
} | |
/* End Of RS Hash Function */ | |
uint | |
HashFunc::JSHash(const char* str, uint len) | |
{ | |
return this->JSHash(str, len, 1315423911); | |
} | |
uint | |
HashFunc::JSHash(const char* str, uint len, uint hash) | |
{ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash ^= ((hash << 5) + (*str) + (hash >> 2)); | |
} | |
return hash; | |
} | |
/* End Of JS Hash Function */ | |
uint | |
HashFunc::PJWHash(const char* str, uint len) | |
{ | |
return this->PJWHash(str, len, 0); | |
} | |
uint | |
HashFunc::PJWHash(const char* str, uint len, uint hash) | |
{ | |
const uint BitsInUnsignedInt = (uint)(sizeof(uint) * 8); | |
const uint ThreeQuarters = (uint)((BitsInUnsignedInt * 3) / 4); | |
const uint OneEighth = (uint)(BitsInUnsignedInt / 8); | |
const uint HighBits = (uint)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); | |
uint test = 0; | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = (hash << OneEighth) + (*str); | |
if((test = hash & HighBits) != 0) | |
{ | |
hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits)); | |
} | |
} | |
return hash; | |
} | |
/* End Of P. J. Weinberger Hash Function */ | |
uint | |
HashFunc::BKDRHash(const char* str, uint len) | |
{ | |
return this->BKDRHash(str, len, 0); | |
} | |
uint | |
HashFunc::BKDRHash(const char* str, uint len, uint hash) | |
{ | |
uint seed = 131; /* 31 131 1313 13131 131313 etc.. */ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = (hash * seed) + (*str); | |
} | |
return hash; | |
} | |
/* End Of BKDR Hash Function */ | |
uint | |
HashFunc::SDBMHash(const char* str, uint len) | |
{ | |
return this->SDBMHash(str, len, 0); | |
} | |
uint | |
HashFunc::SDBMHash(const char* str, uint len, uint hash) | |
{ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = (*str) + (hash << 6) + (hash << 16) - hash; | |
} | |
return hash; | |
} | |
/* End Of SDBM Hash Function */ | |
uint | |
HashFunc::DJBHash(const char* str, uint len) | |
{ | |
return this->DJBHash(str, len, 5381); | |
} | |
uint | |
HashFunc::DJBHash(const char* str, uint len, uint hash) | |
{ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = ((hash << 5) + hash) + (*str); | |
} | |
return hash; | |
} | |
/* End Of DJB Hash Function */ | |
uint | |
HashFunc::DEKHash(const char* str, uint len) | |
{ | |
return this->DEKHash(str, len, len); | |
} | |
uint | |
HashFunc::DEKHash(const char* str, uint len, uint hash) | |
{ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = ((hash << 5) ^ (hash >> 27)) ^ (*str); | |
} | |
return hash; | |
} | |
/* End Of DEK Hash Function */ | |
uint | |
HashFunc::BPHash(const char* str, uint len) | |
{ | |
return this->BPHash(str, len, 0); | |
} | |
uint | |
HashFunc::BPHash(const char* str, uint len, uint hash) | |
{ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash = hash << 7 ^ (*str); | |
} | |
return hash; | |
} | |
/* End Of BP Hash Function */ | |
uint | |
HashFunc::FNVHash(const char* str, uint len) | |
{ | |
return this->FNVHash(str, len, 0); | |
} | |
uint | |
HashFunc::FNVHash(const char* str, uint len, uint hash) | |
{ | |
const uint fnv_prime = 0x811C9DC5; | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash *= fnv_prime; | |
hash ^= (*str); | |
} | |
return hash; | |
} | |
/* End Of FNV Hash Function */ | |
uint | |
HashFunc::APHash(const char* str, uint len) | |
{ | |
return this->APHash(str, len, 0xAAAAAAAA); | |
} | |
uint | |
HashFunc::APHash(const char* str, uint len, uint hash) | |
{ | |
uint i = 0; | |
for(i = 0; i < len; str++, i++) | |
{ | |
hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ (*str) * (hash >> 3)) : | |
(~((hash << 11) ^ (*str) ^ (hash >> 5))); | |
} | |
return hash; | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef HASH_HH_ | |
# define HASH_HH_ | |
# include <cstring> | |
# include <iostream> | |
# include <istream> | |
# include <fstream> | |
typedef unsigned int uint; | |
class HashFunc | |
{ | |
public: | |
HashFunc (); | |
~HashFunc (); | |
/** | |
* Private string hashing methods | |
*/ | |
uint FNVHash (const char* str, uint len); // 1 Best one | |
uint SDBMHash (const char* str, uint len); // 2 Second Best one | |
uint APHash (const char* str, uint len); // 3 Third Best one | |
uint RSHash (const char* str, uint len); // 4 | |
uint BKDRHash (const char* str, uint len); // 4 | |
uint DJBHash (const char* str, uint len); // 5 | |
uint JSHash (const char* str, uint len); // 6 | |
uint DEKHash (const char* str, uint len); // 6 | |
uint ELFHash (const char* str, uint len); // 7 | |
uint PJWHash (const char* str, uint len); // 7 | |
uint BPHash (const char* str, uint len); // 8 | |
uint FNVHash (const char* str, uint len, uint hash); | |
uint SDBMHash (const char* str, uint len, uint hash); | |
uint APHash (const char* str, uint len, uint hash); | |
uint RSHash (const char* str, uint len, uint hash); | |
uint BKDRHash (const char* str, uint len, uint hash); | |
uint DJBHash (const char* str, uint len, uint hash); | |
uint JSHash (const char* str, uint len, uint hash); | |
uint DEKHash (const char* str, uint len, uint hash); | |
uint ELFHash (const char* str, uint len, uint hash); | |
uint PJWHash (const char* str, uint len, uint hash); | |
uint BPHash (const char* str, uint len, uint hash); | |
}; | |
#endif /* !HASH_HH_ */ | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment