Hash Function, Collisons Text: // http://www.cse.yorku.ca/~oz/hash.html // First

Question

Hash Function, Collisons Text:

// http://www.cse.yorku.ca/~oz/hash.html
// First reported by Dan Berstein in the news group comp.lang.c.

unsigned long djb2(unsigned char *str)
{
   unsigned long hash = 5381;
   int c;
   while (c = *str++)
       hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

   return hash;
}
// Created for sdbm (a public-domain reimplementation of ndbm) database library.
// It was found to do well in scrambling bits causing better distribution of
// the keys and fewer splits.
unsigned long sdbm(unsigned char *str)
{
   unsigned long hash = 0; int c;
   while (c = *str++)
       hash = c + (hash << 6) + (hash << 16) - hash;

   return hash;
}
// First appeared in K&R (1st edition). Terrible hashing algorithm because it
// produces many collisions.
unsigned long loselose(unsigned char *str)
{
   unsigned long hash = 0; int c;
   while (c = *str++)
       hash += c;

   return hash;
}

Explanation / Answer

main.cpp #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define Round(x) int(x + 0.5) #define all(x) x.begin(),x.end() #define rall(x) x.end(),x.begin() #define pb push_back #define sz(x) (int)x.size() #define ins insert #define getmax(a,b) ((a)>(b)?(a):(b)) #define getmin(a,b) ((a)>(b)?(b):(a)) #define OOR out_of_range typedef long ll; typedef vector vi; typedef vector vs; typedef set si; typedef set sets; typedef set setc; typedef pair pii; int main() { return 0; } hashing.cpp #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace __gnu_cxx; #define Round(x) int(x + 0.5) #define all(x) x.begin(),x.end() #define rall(x) x.end(),x.begin() #define pb push_back #define sz(x) (int)x.size() #define ins insert #define getmax(a,b) ((a)>(b)?(a):(b)) #define getmin(a,b) ((a)>(b)?(b):(a)) #define OOR out_of_range typedef long ll; typedef vector vi; typedef vector vs; typedef set si; typedef set sets; typedef set setc; typedef pair pii; vs allDictionaryWords; vs randomlyPickedWords; //int testRaanges[4] = {2000, 400, 6000, 8000}; vs hashTable; int getNextPrime(int num); unsigned long djb2(string str); unsigned long sdbm(string str); void loadFile(); void pickRandomWords(int numberOfWords); int getNextPrime(int num); void runProgram(); int buildTableANDtest(int numberOfWords); int main() { runProgram(); return 0; } unsigned long djb2(string str) { int hash = 5381; int c; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.