Hashtable

Overview

For this assignment you will complete the implementation of a hashtable data structure, which exposes an API mirroring that of the built-in Python dict.

A hashtable is conceptually a two-tiered data structure, where keys are initially mapped — via their hash values — to slots in a "buckets" array, each of which in turn contain singly-linked (non-circular) lists of key/value pairs (known as "chains"). The hope is that by keeping the number of collisions — i.e., instances where keys map to the same bucket — low, key-based lookups can be performed very quickly. The essential operations on a hashtable h are listed alongside their behavior/mechanics below:

Operation Description
h[k] = v The key k's hash value is used to locate the appropriate slot in the array of buckets. If the bucket entry is None, a new linked list is created with k & v as the first entry and the head of the list is placed in the bucket. Otherwise, the list is searched for a node containing key k; if found the node's value will be updated with v, else a new node containing key k & value v is appended to the list. Note that this implies a given key has a unique mapping in a hashtable.
h[k] The key k's hash value is used to locate the appropriate slot in the array of buckets. If the bucket entry is not None, the linked list at that location is searched for a node containing k; if found, the corresponding value is returned. If the bucket is empty or the list does not contain a node with key k, a KeyError is raised.
del h[k] The key k's hash value is used to locate the appropriate slot in the array of buckets. If the bucket entry is not None, the linked list in the bucket is searched for a node with key k; if found, it is deleted. If either the bucket is empty or the list doesn't contain key k, a KeyError is raised.
k in h Returns True if key k is found in a list in the appropriate bucket.
len(h) Returns the number of keys stored across all buckets.
iter(h) Returns an iterator over all the keys in the hashtable.
h.keys() Returns an iterator over all the keys in the hashtable (the same as above).
h.values() Returns an iterator over all the values in the hashtable.
h.items() Returns an iterator over all the key/value pairs (as tuples) in the hashtable.
h.setdefault(key, default) If key is in the dictionary, return its value. If not, insert key with a value of default and return default. default defaults to None.

Your hashtable will be provided with the initial number of buckets on creation (i.e., in __init__), which will be used to create an array with that size (where each slot contains None). Because the hash value of a given key can exceed the number of buckets, hash values will be mapped to buckets using the modulus operator; i.e., hash(k) % len(self.buckets) will return the index of the appropriate bucket for key k.

For testing purposes, the avg_chain_length method is provided, which returns the average length of the chains stored across all non-empty buckets. You may want to look over its implementation to get a sense of how the buckets and lists they contain might be navigated.

In [ ]:
class Hashtable:
    class Node:
        """Instances of this class will be used to construct the linked lists (chains)
        found in non-empty hashtable buckets."""
        def __init__(self, key, val, next=None):
            self.key = key
            self.val = val
            self.next = next

    def __init__(self, n_buckets=1000):
        self.buckets = [None] * n_buckets # initially empty buckets array
        self.count = 0
    
    def __getitem__(self, key):
        # YOUR CODE HERE
        raise NotImplementedError()
    
    def __setitem__(self, key, val):
        # YOUR CODE HERE
        raise NotImplementedError()
    
    def __delitem__(self, key):
        # YOUR CODE HERE
        raise NotImplementedError()
                
    def __contains__(self, key):
        # YOUR CODE HERE
        raise NotImplementedError()
        
    def __len__(self):
        return self.count
    
    def __iter__(self):
        # YOUR CODE HERE
        raise NotImplementedError()
                    
    def keys(self):
        return iter(self)

    def values(self):
        # YOUR CODE HERE
        raise NotImplementedError()

    def items(self):
        # YOUR CODE HERE
        raise NotImplementedError()
        
    def setdefault(self, key, default=None):
        # YOUR CODE HERE
        raise NotImplementedError()
In [ ]:
from unittest import TestCase
import random

tc = TestCase()

class MyInt(int):
    def __hash__(self):
        """MyInts hash to themselves — already current Python default, 
        but just to ensure consistency."""
        return self
    
def ll_len(l):
    """Returns the length of a linked list with head `l` (assuming no sentinel)"""
    c = 0
    while l:
        c += 1
        l = l.next
    return c
    
ht = Hashtable(10)
for i in range(25):
    ht[MyInt(i)] = i*2

tc.assertEqual(len(ht), 25)

for i in range(5):
    tc.assertEqual(ll_len(ht.buckets[i]), 3)
    
for i in range(5, 10):
    tc.assertEqual(ll_len(ht.buckets[i]), 2)

for i in range(25):
    tc.assertTrue(MyInt(i) in ht)
    tc.assertEqual(ht[MyInt(i)], i*2)
In [ ]:
# iterator testing
from unittest import TestCase
import random

tc = TestCase()

ht = Hashtable(100)
d = {}

for i in range(100):
    k, v = str(i), str(random.randrange(10000000, 99999999))
    d[k] = v
    ht[k] = v
    
keys = set(ht.keys())
tc.assertEqual(len(keys), 100)
for k in keys:
    tc.assertTrue(k in ht)
    tc.assertEqual(ht[k], d[k])

tc.assertEqual(sorted(ht.values()), sorted(d.values()))

for k,v in ht.items():
    tc.assertEqual(d[k], v)
In [ ]:
# deletion testing
from unittest import TestCase
import random

tc = TestCase()

ht = Hashtable(100)
d = {}

for i in range(100):
    k, v = str(i), str(random.randrange(10000000, 99999999))
    d[k] = v
    ht[k] = v

for _ in range(50):
    k = str(random.randrange(100))
    if k in d:
        del d[k]
        del ht[k]

tc.assertEqual(len(ht), len(d))

for k,v in ht.items():
    tc.assertEqual(d[k], v)
In [ ]:
# setdefault testing
from unittest import TestCase
import random

tc = TestCase()

ht = Hashtable(100)
d = {}

tc.assertEqual(ht.setdefault('1', '2'), '2')
ht['3'] = '4'
tc.assertEqual(ht.setdefault('3', '5'), '4')
del ht['3']
tc.assertEqual(ht.setdefault('3', '6'), '6')
tc.assertEqual(ht.setdefault('7'), None)
ht['7'] = '8'
tc.assertEqual(ht.setdefault('7'), '8')
In [ ]:
# stress testing

from unittest import TestCase
import random

tc = TestCase()

ht = Hashtable(100000)
d = {}

for _ in range(100000):
    k, v = str(random.randrange(100000)), str(random.randrange(10000000, 99999999))
    d[k] = v
    ht[k] = v
    
for k,v in d.items():
    tc.assertTrue(k in ht)
    tc.assertEqual(d[k], ht[k])