Thursday, May 17, 2012

Yet Another HashMap ...

There are several implementations of hashmaps available, this is just another implementation that I did when I  was too lazy to google for existing implementations.

This implementation is having 2 basic traits:
1. A strong hash function.
2. An efficient tree

To implement this I have used the hash implementation provided by Bob Jenkins

And the tree chosen is a basic red black tree implementation. 

A very simple API which enables insertion/deletion of the entries.

To insert entries:
hash_insert(void* key, uint32 key_len, void* data, uint32 data_len);

To Check if the entry is present in the table
hash_find(void* key, uint32 key_len);

To retrieve the data for a key
hash_getData(void* key, uint32 key_len, void* data, uint16* data_len)

To delete an entry
hash_deleteEntry(void* key, uint32 key_len);

Here is a sample code, to show how to use it.

#include "hashmap.h"#include
#define MAX_KEY_LEN 128
int main(){
      char key[MAX_KEY_LEN];
      uint16_t data;
      uint16_t dataLen;
      int i = 10000000;
      // First insert
      strcpy(key, "hello");
      data = 123;
      hash_insert((void*)key, strlen(key), &data, sizeof(data));
      //Lets retrieve it
      strcpy(key, "hello");
      uint16_t temp;
      hash_getData((void*)key, strlen(key), &temp, &dataLen);
      //Remove the entries
      strcpy(key, "hello");
      hash_deleteEntry((void*)key, strlen(key));

The default number of entries in the hashmap is defined in hashmap.h as follows

#define HASH_MAX_CAPACITY 10000000

This can be modified as per requirement.

How to Use

Just hit make in the extracted package. This generates a  library and libQuickHash.a.  There is a sample program testHash.c which can be of help. 

The compressed package is here

enjoy ...

No comments:

Post a Comment