A table of buckets

Build a hash table that uses chaining (lesson 2). Do not use Python’s dict or set: the point is to build one. Use Python’s own hash(key) for the hash.

• A new table has 8 buckets. A key goes in bucket hash(key) % m, where m is the number of buckets.
• A new key goes at the end of its bucket’s chain.
• After a put adds a new key, if the number of keys n is now bigger than m, double m. Then move every key to its new bucket: take the old buckets in order (0 first), and each chain from front to back.
• The table never shrinks.
• buckets() returns the keys in each bucket, for example [[], [9], [], [3, 11]].

T = ChainMap()
T.put('NDLS', 1); T.put('BCT', 2)
T.get('NDLS')      # 1
T.get('MAS')       # None
T.remove('BCT')    # True
len(T)             # 1

The tests make an object and call its methods in order. A test shows the list of calls, and compares the list of everything they returned (methods that return nothing give None).

Limits

• Up to 100,000 keys. Every method except buckets() must take O(1) time on average.