How would you implement a hashtable in language x? [closed]

Question

The point of this question is to collect a list of examples of hashtable implementations using arrays in different languages. It would also be nice if someone could throw in a pretty detailed overview of how they work, and what is happening with each example.

Edit:

Why not just use the built in hash functions in your specific language?

Because we should know how hash tables work and be able to implement them. This may not seem like a super important topic, but knowing how one of the most used data structures works seems pretty important to me. If this is to become the wikipedia of programming, then these are some of the types of questions that I will come here for. I'm not looking for a CS book to be written here. I could go pull Intro to Algorithms off the shelf and read up on the chapter on hash tables and get that type of info. More specifically what I am looking for are code examples. Not only for me in particular, but also for others who would maybe one day be searching for similar info and stumble across this page.

To be more specific: If you had to implement them, and could not use built-in functions, how would you do it?

You don't need to put the code here. Put it in pastebin and just link it.

Answer 1

A hash table a data structure that allows lookup of items in constant time. It works by hashing a value and converting that value to an offset in an array. The concept of a hash table is fairly easy to understand, but implementing is obviously harder. I'm not pasting the whole hash table here, but here are some snippets of a hash table I made in C a few weeks ago...

One of the basics of creating a hash table is having a good hash function. I used the djb2 hash function in my hash table:

int ComputeHash(char* key) {     int hash = 5381;     while (*key)     hash = ((hash << 5) + hash) + *(key++);     return hash % hashTable.totalBuckets; } 

Then comes the actual code itself for creating and managing the buckets in the table

typedef struct HashTable{     HashTable* nextEntry;     char*      key;     char*      value; }HashBucket;  typedef struct HashTableEntry{     int totalBuckets;       // Total number of buckets allocated for the hash table     HashTable** hashBucketArray; // Pointer to array of buckets }HashTableEntry; HashTableEntry hashTable;  bool InitHashTable(int totalBuckets) {     if(totalBuckets > 0)     {         hashTable.totalBuckets = totalBuckets;         hashTable.hashBucketArray = (HashTable**)malloc(totalBuckets * sizeof(HashTable));         if(hashTable.hashBucketArray != NULL)         {             memset(hashTable.hashBucketArray, 0, sizeof(HashTable) * totalBuckets);             return true;         }     }     return false; }  bool AddNode(char* key, char* value) {     int offset = ComputeHash(key);     if(hashTable.hashBucketArray[offset] == NULL)     {         hashTable.hashBucketArray[offset] = NewNode(key, value);         if(hashTable.hashBucketArray[offset] != NULL)             return true;     }      else     {         if(AppendLinkedNode(hashTable.hashBucketArray[offset], key, value) != NULL)             return true;     }     return false; }  HashTable* NewNode(char* key, char* value) {     HashTable* tmpNode = (HashTable*)malloc(sizeof(HashTable));     if(tmpNode != NULL)     {         tmpNode->nextEntry = NULL;         tmpNode->key   = (char*)malloc(strlen(key));         tmpNode->value = (char*)malloc(strlen(value));          strcpy(tmpNode->key, key);         strcpy(tmpNode->value, value);     }     return tmpNode; } 

AppendLinkedNode finds the last node in the linked list and appends a new node to it.

The code would be used like this:

if(InitHashTable(100) == false) return -1; AddNode("10", "TEN"); 

Finding a node is a simple as:

HashTable* FindNode(char* key) {     int offset = ComputeHash(key);     HashTable* tmpNode = hashTable.hashBucketArray[offset];     while(tmpNode != NULL)     {         if(strcmp(tmpNode->key, key) == 0)             return tmpNode;         tmpNode = tmpNode->nextEntry;     }     return NULL; } 

And is used as follows:

char* value = FindNode("10");