This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 

  Hash Table
  Submitted by



Hello Coders at flipcode! I've recently delved into my stockpile of code searching for a method of quickly and easily accessing information. There are also quick methods of saving this hash table, but if you really want to make a game worthy hash table, check out the MoPaQ format (MPQ, as in Diablo, Starcraft, etc.) at http://www.campaigncreations.com/starcraft/inside_mopaq/ I'm using the table for a complete range of uses, from registration with a server object (simply add the hash entry) to variations of a heirachy. (I couldn't use STD with the heirachy implementation as well as a few others) The method that the hash values are created is with purpose, so don't believe that I enjoy being cryptic. Anyway, the top 16 bits of the 32 bit hash is the 'type' number. This is a unique ID generated as a verification number. The bottom 16 bits is the actual hash; in the hash table, it is used to quickly reference retrieve the position in the table. Once the position in the table is found, the table progresses through a linked list, consisting of all entries with the same lower 16 bits, searching for the entry that matches the top 16 bits. Enjoy! Comments, Code Corrections, Weather Reports, etc. Welcome! Chris Pergrossi

Currently browsing [hasht.zip] (4,683 bytes) - [main.cpp] - (576 bytes)

#include <stdio.h>
#include "hash.h"

// sample file // // adds a few entries, then displays and deletes them // void main (void) { CHashTable<long> table;

table.addHash (toHash ("Hello World"), 1); table.addHash (toHash ("Goodbye World!"), 2); table.addHash (toHash ("Chris Wuz Here"), 614);

long nHash, nValue;

printf ("# Table Entries: %d\n", table.getCount ());

table.getHash (&nHash, &nValue);

do { printf ("\tHash: %d\n\tValue: %d\n\n", nHash, nValue); table.removeHash (nHash); } while (table.getHash (&nHash, &nValue)); }

Currently browsing [hasht.zip] (4,683 bytes) - [hash.cpp] - (3,469 bytes)

#include <string.h>
#include <stdlib.h>
#include "hash.h"

// // if you find 256 entries too excessive for your liking // you may desize it, but I recommend a power-of-two size // (if you change the size, you must change the AND statement // in the function below) // long cryptTable[] = { 0x697A5,0x6045C,0xAB4E2,0x409E4,0x71209,0x32392,0xA7292,0xB09FC,0x4B658,0xAAAD5,0x9B9CF,0xA326A,0x8DD12,0x38150,0x8E14D,0x2EB7F, 0xE0A56,0x7E6FA,0xDFC27,0xB1301,0x8B4F7,0xA7F70,0xAA713,0x6CC0F,0x6FEDF,0x2EC87,0xC0F1C,0x45CA4,0x30DF8,0x60E99,0xBC13E,0x4E0B5, 0x6318B,0x82679,0x26EF2,0x79C95,0x86DDC,0x99BC0,0xB7167,0x72532,0x68765,0xC7446,0xDA70D,0x9D132,0xE5038,0x2F755,0x9171F,0xCB49E, 0x6F925,0x601D3,0x5BD8A,0x2A4F4,0x9B022,0x706C3,0x28C10,0x2B24B,0x7CD55,0xCA355,0xD95F4,0x727BC,0xB1138,0x9AD21,0xC0ACA,0xCD928, 0x953E5,0x97A20,0x345F3,0xBDC03,0x7E157,0x96C99,0x968EF,0x92AA9,0xC2276,0xA695D,0x6743B,0x2723B,0x58980,0x66E08,0x51D1B,0xB97D2, 0x6CAEE,0xCC80F,0x3BA6C,0xB0BF5,0x9E27B,0xD122C,0x48611,0x8C326,0xD2AF8,0xBB3B7,0xDED7F,0x4B236,0xD298F,0xBE912,0xDC926,0xC873F, 0xD0716,0x9E1D3,0x48D94,0x9BD91,0x5825D,0x55637,0xB2057,0xBCC6C,0x460DE,0xAE7FB,0x81B03,0x34D8F,0xC0528,0xC9B59,0x3D260,0x6051D, 0x93757,0x8027F,0xB7C34,0x4A14E,0xB12B8,0xE4945,0x28203,0xA1C0F,0xAA382,0x46ABB,0x330B9,0x5A114,0xA754B,0xC68D0,0x9040E,0x6C955, 0xBB1EF,0x51E6B,0x9FF21,0x51BCA,0x4C879,0xDFF70,0x5B5EE,0x29936,0xB9247,0x42611,0x2E353,0x26F3A,0x683A3,0xA1082,0x67333,0x74EB7, 0x754BA,0x369D5,0x8E0BC,0xABAFD,0x6630B,0xA3A7E,0xCDBB1,0x8C2DE,0x92D32,0x2F8ED,0x7EC54,0x572F5,0x77461,0xCB3F5,0x82C64,0x35FE0, 0x9203B,0xADA2D,0xBAEBD,0xCB6AF,0xC8C9A,0x5D897,0xCB727,0xA13B3,0xB4D6D,0xC4929,0xB8732,0xCCE5A,0xD3E69,0xD4B60,0x89941,0x79D85, 0x39E0F,0x6945B,0xC37F8,0x77733,0x45D7D,0x25565,0xA3A4E,0xB9F9E,0x316E4,0x36734,0x6F5C3,0xA8BA6,0xC0871,0x42D05,0x40A74,0x2E7ED, 0x67C1F,0x28BE0,0xE162B,0xA1C0F,0x2F7E5,0xD505A,0x9FCC8,0x78381,0x29394,0x53D6B,0x7091D,0xA2FB1,0xBB942,0x29906,0xC412D,0x3FCD5, 0x9F2EB,0x8F0CC,0xE25C3,0x7E519,0x4E7D9,0x5F043,0xBBA1B,0x6710A,0x819FB,0x9A223,0x38E47,0xE28AD,0xB690B,0x42328,0x7CF7E,0xAE108, 0xE54BA,0xBA5A1,0xA09A6,0x9CAB7,0xDB2B3,0xA98CC,0x5CEBA,0x9245D,0x5D083,0x8EA21,0xAE349,0x54940,0x8E557,0x83EFD,0xDC504,0xA6059, 0xB85C9,0x9D162,0x7AEB6,0xBED34,0xB4963,0xE367B,0x4C891,0x9E42C,0xD4304,0x96EAA,0xD5D69,0x866B8,0x83508,0x7BAEC,0xD03FD,0xDA122 };

// // I made this hash function after several months of looking around // and I must say, the greatest resource I found was looking at the // MPQ format used by Blizzard. The resource can be found at // http://www.campaigncreations.com/starcraft/inside_mopaq/ // // This function was made to be case - insensitive, just cause I hate // having to worry about caps or not, so if you want it case - sensitive, // replace the line: ch = toupper (*pKey++) with ch = *pKey++ // long toHash (char* pString) { long nSeed1, nSeed2;

// LOL, coder joke: Dead Code ;) nSeed1 = 0xDEADC0DE; nSeed2 = 0x7FED7FED;

char* pKey = pString; char ch;

while (*pKey != 0) { ch = toupper (*pKey++);

// if you changed the size of the cryptTable, you must change the & 0xFF below // to & whatever if it's a power of two, or % whatever, if it's not nSeed1 = cryptTable[((TYPE << 8) + ch)&0xFF] ^ (nSeed1 + nSeed2); nSeed2 = ch + nSeed1 + nSeed2 + (nSeed2 << 5) + 3; }

return nSeed1; }

Currently browsing [hasht.zip] (4,683 bytes) - [hash.h] - (5,401 bytes)

#ifndef _HASH_H_
#define _HASH_H_

#ifndef NULL #define NULL (0L) #endif

#define MAX_HASH_ENTRIES 128 #define TYPE (0x9C) /* If You Change This, You Change The Hash Output! */

// // this is my hash function // it is built upon several months of research // and should withstand VERY heavy testing without // duplicate hashes // long toHash (char* pString);

// // my generic hash table implementation, simply pass it the // class that you would like to be contained // template<class T> class CHashTable { protected: template<class D> struct hEntry_s { T entry; long type; hEntry_s<D>* next; };

long nCount;

hEntry_s<T>* pTable[MAX_HASH_ENTRIES];

public: CHashTable () { for (int i = 0; i < MAX_HASH_ENTRIES; i++) { pTable[i] = NULL; }

nCount = 0; }

~CHashTable () { hEntry_s<T> *pEnt, *pTmp;

for (int i = 0; i < MAX_HASH_ENTRIES; i++) { if (pTable[i]) { pEnt = pTable[i];

while (pEnt) { pTmp = pEnt; pEnt = pEnt->next; delete pTmp; }

pTable[i] = NULL; } } }

int getCount () { return nCount; }

// // this adds an entry to a position in the hash table // I would typically 'hash' the name of the object // being inserted // bool addHash (long nHash, T entry) { long nPos, nType;

nPos = (nHash & 0xFFFF) % MAX_HASH_ENTRIES; nType = nHash >> 16;

hEntry_s<T> *pEnt;

pEnt = pTable[nPos];

if (pEnt) { while (pEnt->next != NULL) pEnt = pEnt->next;

pEnt->next = new hEntry_s<T>;

pEnt = pEnt->next; } else { pTable[nPos] = pEnt = new hEntry_s<T>; }

pEnt->entry = entry; pEnt->type = nType; pEnt->next = NULL;

nCount++;

return true; }

// // this is if you retrieve the entry (via getHash ()) // and make some changes to it, this will update it // bool updateHash (long nHash, T* entry) { long nPos, nType;

nPos = (nHash & 0xFFFF) % MAX_HASH_ENTRIES; nType = nHash >> 16;

hEntry_s<T> *pEnt;

pEnt = pTable[nPos];

if (!pEnt) return false;

while (pEnt->type != nType) { if (pEnt->next != NULL) pEnt = pEnt->next; else break; }

if (pEnt->type == nType) { pEnt->entry = *entry; return true; }

return false; }

// // this will return the entry with the // given hash // bool getHash (long nHash, T* entry) { long nPos, nType;

nPos = (nHash & 0xFFFF) % MAX_HASH_ENTRIES; nType = nHash >> 16;

hEntry_s<T> *pEnt;

pEnt = pTable[nPos];

if (!pEnt) return false;

while (pEnt->type != nType) { if (pEnt->next != NULL) pEnt = pEnt->next; else break; }

if (pEnt->type == nType) { *entry = pEnt->entry; return true; }

return false; }

// // I use this when I use the table for pointers to memory // this will return the first entry in the table (not the // first slot, but the first actual entry) and it's paired // hash value // bool getHash (long* nHash, T* entry) { for (int i = 0; i < MAX_HASH_ENTRIES; i++) if (pTable[i]) { *entry = pTable[i]->entry; *nHash = i | (pTable[i]->type << 16); return true; }

return false; }

// // this will return the next hash in the list, given // an original hash value (again, I use this for freeing memory) // // Watch Out: It searches for the previous entry to give the next entry. // If you erase the previously returned entry (removeHash ()) you must // use getHash () to return another entry, because getNext () won't find // anymore and return false // bool getNext (long nHash, long* nNext, T* entry) { long nPos, nType;

nPos = (nHash & 0xFFFF) % MAX_HASH_ENTRIES; nType = nHash >> 16;

hEntry_s<T> *pEnt;

pEnt = pTable[nPos];

if (!pEnt) return false;

while (pEnt->type != nType) { if (pEnt->next != NULL) pEnt = pEnt->next; else break; }

if (pEnt->type == nType) { if (pEnt->next != NULL) { pEnt = pEnt->next; *entry = pEnt->entry; *nNext = nPos | (pEnt->type << 16);

return true; }

int i;

for (int d = 0; d < MAX_HASH_ENTRIES; d++) { i = d + nPos + 1;

if (i >= MAX_HASH_ENTRIES) i -= MAX_HASH_ENTRIES;

if (pTable[i]) { *entry = pTable[i]->entry; *nNext = i | (pTable[i]->type << 16); return true; } } }

return false; }

// // this will remove a hash from the table, freeing // up the slot // bool removeHash (long nHash) { long nPos, nType;

nPos = (nHash & 0xFFFF) % MAX_HASH_ENTRIES; nType = nHash >> 16;

hEntry_s<T> *pEnt, *pPrev;

pPrev = pEnt = pTable[nPos];

if (!pEnt) return false;

if (pEnt->type == nType) { pPrev = pEnt->next; delete pEnt; pTable[nPos] = pPrev;

nCount--;

return true; }

pEnt = pEnt->next;

if (!pEnt) return false;

while (pEnt->type != nType) { if (pEnt->next != NULL) { pPrev = pEnt; pEnt = pEnt->next; } else break; }

if (pEnt->type == nType) { pPrev->next = pEnt->next; delete pEnt;

nCount--;

return true; }

return false; } };

#endif

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.