Easy-to-Use Hash Table

Environment: VC6, BC5

The purpose of this article is to show a small hashtable that works with std::strings as key and any data as member.

The hash_map that is implemented as extension of the STL is too complex for my problem and not easy to compile with several compilers (BorlandC, VisualC), so I wrote this little CHashTable class. The class has functions to Add, Remove, and Rename entries and to Get the member data via key. The class is derived from std::list. The Add and Remove functions also push and erase the keys in the parent list class so that you can use the list::iterator functionality.

The class consists of the following member-functions:

CHashTable(long tabsize = 10009, long (*VoidPtr)(const std::string& c, const long prime) = hash_fun1);

Per default, the hash_array has a length of 10009. Of course, you can store more than 10,009 values. You can change the size with argument 1 ( it doesn’t have to be a prime number; the constructor adjusts the argument to a prime number).

Argument 2 is the hash function. Per default, it’s a the function “hash_fun1” defined in the header file “hash_fun.h”.

If the hash_fun calculates equal positions for several keys, the collision is solved via a std::list.

bool AddKey(std::string key, T* member);

Adds a new member with the key “key”. If the “key” exists, the function returns false.

bool RenameKey(std::string key, std::string new_key);

Renames the key of the member with the key “key” to “new_key”. If the “key” doesn’t exist, the function returns false. If the “new_key” exists, the function also returns false.

bool RemoveKey(const std::string& key, bool free_mem = false);

Removes a member with the key “key”. If the “key” doesn’t exist, the function returns false. If free_mem is true, the memory of the member pointer will be deallocated.

bool RemoveAllKey(bool free_mem = false);

Removes all members (free_mem see “RemoveKey”).

T* GetPtr(const std::string& key);

Gets a member with the key “key”. If the “key” doesn’t exist, the function returns false.

I have added three sample projects that show the usage of the class, and at the end, two examples how to use the class. The first one stores long values in the hash, which are static variables. The second example stores dynamically allocated structs in the table and then reads back one member. After this, all keys are removed and the allocated memory is cleaned up.


/*********************/
/* Example 1 */
/* ——— */
/* hash with long’s */
/*********************/

#include “hash_table.h”

void main()
{
/* my hash table is of type <long> */
typedef CHashTable<long> CLongHashT;

std::string keys[3] = {“three”, “seven”, “ten”};
long entries[3] = {3, 7, 10};

/* fill the hash table */
CLongHashT MyHashTable;
for(int i = 0; i < 3; i++) MyHashTable.AddKey(keys[i],
&entries[i]);

/* get a member */
std::string key = keys[1];
long* pMember = MyHashTable.GetMember(key);
if(pMember) printf(“Entry for key “%s” is %d.nn”,
key.c_str(), *pMember);

/* clean up the hash (do not free memory) */
MyHashTable.RemoveAllKey(false);
}

/*********************/
/* Example 2 */
/* ——— */
/* hash with struct */
/*********************/

#include “hash_table.h”

struct SMyStruct
{
int fat;
int sugar;
std::string comment;
};

void main()
{
/* my hash table is of type <SMyStruct> */
typedef CHashTable<struct SMyStruct> CMyStructHashT;

/* fill the hash table */
CMyStructHashT MyHashTable;
struct SMyStruct* pStruct = NULL;

/* first key */
pStruct = new SMyStruct;
if(pStruct)
{
pStruct->fat = 0;
pStruct->sugar = 622;
pStruct->comment = “good for tired people”;
MyHashTable.AddKey(“cola”, pStruct);
}

/* second key */
pStruct = new SMyStruct;
if(pStruct)
{
pStruct->fat = 15;
pStruct->sugar = 0;
pStruct->comment = “good for young people”;
MyHashTable.AddKey(“milk”, pStruct);
}

/* get a member */
pStruct = MyHashTable.GetMember(“milk”);
if(pStruct) printf(“Milk is %s.nn”, pStruct->comment.c_str());

/* clean up the hash (and free memory) */
MyHashTable.RemoveAllKey(true);
}

Downloads


Download demo project – 22 Kb


Download source – 5 Kb

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read