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])
```