Design HashMap

The Monster Vault holds every monster in the kingdom, and its keeper has to fetch any one of them in a single step. Walking past the monsters one by one is hopeless once there are a million of them. So the vault is a row of buckets. A hash function turns a monster's name into a bucket number: to store a monster, hash its name and drop it in that bucket; to find it, hash the name again and look in that one bucket only. Two names can land in the same bucket. That's a collision, so each bucket keeps a short list.

Build the vault yourself: a class MonsterVault with

• MonsterVault(): an empty vault.
• put(name, power): store the monster, or update its power if that name is already in the vault.
• get(name): the monster's power, or -1 if no monster has that name.
• remove(name): take the monster out of the vault. Does nothing if it isn't there.

v = MonsterVault()
v.put("OGRE", 40)
v.put("GOB", 7)
v.put("LICH", 90)    # GOB and LICH may share a bucket: that's fine
v.get("LICH")        # 90
v.get("ORC")         # -1
v.put("GOB", 12)     # GOB is already there: update it
v.get("GOB")         # 12
v.remove("OGRE")
v.get("OGRE")        # -1

• Don't store the monsters in your language's built-in hash map or set (dict, set, defaultdict or Counter in Python, unordered_map or map in C++, HashMap or TreeMap in Java). Lists or arrays of buckets are fine, and so is a ready-made hash of a string (hash(name), std::hash<string>, name.hashCode()) or one you write. The tests can't check this: building the buckets is the exercise.
• Names are 1 to 12 uppercase letters A–Z; powers are in [0, 10^9].
• The tests store 40,000 different monsters, so one long list, or a fixed handful of buckets, is too slow. When the buckets get too full, double the row and spread everyone out again.