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

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");

A Java implementation in < 60 LoC

import java.util.ArrayList;import java.util.List;import java.util.Random;public class HashTable {    class KeyValuePair {        Object key;        Object value;        public KeyValuePair(Object key, Object value) {            this.key = key;            this.value = value;        }    }    private Object[] values;    private int capacity;    public HashTable(int capacity) {        values = new Object[capacity];        this.capacity = capacity;    }    private int hash(Object key) {        return Math.abs(key.hashCode()) % capacity;    }    public void add(Object key, Object value) throws IllegalArgumentException {        if (key == null || value == null)            throw new IllegalArgumentException("key or value is null");        int index = hash(key);        List<KeyValuePair> list;        if (values[index] == null) {            list = new ArrayList<KeyValuePair>();            values[index] = list;        } else {            // collision            list = (List<KeyValuePair>) values[index];        }        list.add(new KeyValuePair(key, value));    }    public Object get(Object key) {        List<KeyValuePair> list = (List<KeyValuePair>) values[hash(key)];        if (list == null) {            return null;        }        for (KeyValuePair kvp : list) {            if (kvp.key.equals(key)) {                return kvp.value;            }        }        return null;    }    /**     * Test     */    public static void main(String[] args) {        HashTable ht = new HashTable(100);        for (int i = 1; i <= 1000; i++) {            ht.add("key" + i, "value" + i);        }        Random random = new Random();        for (int i = 1; i <= 10; i++) {            String key = "key" + random.nextInt(1000);            System.out.println("ht.get(\"" + key + "\") = " + ht.get(key));        }       }}

A HashTable is a really simple concept: it is an array in which key and value pairs are placed into, (like an associative array) by the following scheme:

A hash function hashes the key to a (hopefully) unused index into the array. the value is then placed into the array at that particular index.

Data retrieval is easy, as the index into the array can be calculated via the hash function, thus look up is ~ O(1).

A problem arises when a hash function maps 2 different keys to the same index...there are many ways of handling this which I will not detail here...

Hash tables are a fundamental way of storing and retrieving data quickly, and are "built in" in nearly all programming language libraries.