Hash Tables

As an array of linked lists

INSERT

• Compute the key's hash code (int or long)
• Map the hash code to an index in the array: hash(key) % array_length
• At this index, there is a linked list of keys and values. Insert the key and value into this linked list.

LOOKUP

• Compute the key's hash code
• Map the hash code to an index in the array
• Search the resulting linked list for the value with this key

Worst case if high collision rate: O(N), where N is the number of keys

Assuming a low collision rate: O(1) lookup

As a balanced binary search tree

Saves space by not allocating a large array, but O(log N) lookup time.

Implementation

import sys

class MyHashTable():
    def __init__(self):
        self.tableSize = 8
        self.table = [[] for _ in range(self.tableSize)]

    def insert(self, key, value):
        i = hash(key) % self.tableSize
        for pair in self.table[i]:
            if pair[0] == key:
                print("Insert error: key already exists")
                return -1
        self.table[i].append((key, value))
        print("Inserted (%r, %r) into %d" % (key, value, i))

    def lookup(self, key):
        i = hash(key) % self.tableSize
        for pair in self.table[i]:
            if pair[0] == key:
                return pair[1]
            else:
                print("chaining...")
        print("Key not found: %r" % key)
        return -1

    def __str__(self):
        str = "[\n"
        for _list in self.table:
            if not _list:
                str += "    []\n"
                continue
            str += "    ["
            for pair in _list:
                str +=("(%r, %r), " % (pair[0], pair[1]))
            str = str[:-2] + "]\n"
        return str + "]"