Implementing a HashTable with Simple Hashing Functions

A hash table stores key-value pairs and uses a hashing function to map keys to indices in the array backing the table. Simple hashing functions can provide good average-case performance.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MyHashTable {

  private HashEntry[] table;

  private int hash(String key) {
    int hash = 0;
    for (int i = 0; i < key.length(); i++) {
      hash += key.charAt(i);
    }
    return hash % table.length;
  }
  
  public void put(String key, Integer value) {
    int index = hash(key);
    table[index] = new HashEntry(key, value);
  }

  private class HashEntry {
    String key;
    Integer value;

    HashEntry(String key, Integer value) {
      this.key = key;
      this.value = value;
    }
  }

}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MyHashTable {
  
private:

  vector<list<pair<string, int>>> table;

  int hash(string key) {
    int hash = 0;
    for (auto c : key) {
      hash += c;
    }
    return hash % table.size();
  }

public:

  void put(string key, int value) {
    int index = hash(key);
    table[index].push_back(make_pair(key, value));
  }

};

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class MyHashTable:

  def __init__(self):
    self.table = [[] for _ in range(16)]

  def hash(self, key):
    hash_value = 0
    for ch in key:
      hash_value += ord(ch)
    return hash_value % len(self.table)

  def put(self, key, value):
    index = self.hash(key)
    self.table[index].append((key, value))

Simple hashing like sum of characters mod table size provides good performance for many use cases while being easy to implement.

A HashTable is a data structure that stores key-value pairs and provides fast lookup, insertion, and deletion operations. The idea is to use a hash function to convert the key into an index in an array, where the value associated with that key is stored. HashTables handle collisions, which occur when two keys hash to the same index, through various techniques like chaining.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.LinkedList;

public class HashTable {
    private LinkedList<KeyValuePair>[] table;
    private int capacity;

    public HashTable(int capacity) {
        this.capacity = capacity;
        table = new LinkedList[capacity];
    }

    public void put(String key, String value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }
        table[index].add(new KeyValuePair(key, value));
    }

    public String get(String key) {
        int index = hash(key);
        if (table[index] != null) {
            for (KeyValuePair pair : table[index]) {
                if (pair.key.equals(key)) {
                    return pair.value;
                }
            }
        }
        return null;
    }

    private int hash(String key) {
        return key.hashCode() % capacity;
    }

    private static class KeyValuePair {
        String key;
        String value;

        KeyValuePair(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <list>
#include <utility>
#include <string>
using namespace std;

class HashTable {
private:
    list<pair<string, string>>* table;
    int capacity;

public:
    HashTable(int capacity) : capacity(capacity) {
        table = new list<pair<string, string>>[capacity];
    }

    void put(string key, string value) {
        int index = hash(key);
        table[index].emplace_back(key, value);
    }

    string get(string key) {
        int index = hash(key);
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return "";
    }

    int hash(string key) {
        hash<string> hasher;
        return hasher(key) % capacity;
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class HashTable:
    def __init__(self, capacity):
        self.capacity = capacity
        self.table = [[] for _ in range(capacity)]

    def put(self, key, value):
        index = self.hash(key)
        self.table[index].append((key, value))

    def get(self, key):
        index = self.hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def hash(self, key):
        return hash(key) % self.capacity

These examples demonstrate the core concept of a HashTable and how to implement it using simple hashing functions. We used an array of linked lists to handle collisions through chaining. The hash function is based on the key’s hash code modulo the table’s capacity.