ADT Dictionary

Every structure you have met so far is reached by a number: arrays by index, stacks by position, trees by following pointers. A dictionary drops the number. Instead, each item is stored under a key — a label you choose — and you fetch the item by handing back that same key. The thing stored is the value. Together they form a key–value pair.

Think of student records: you rarely want “the 7th student”, you want “the student whose ID is S1042”. The ID is the key; the student's record is the value. Because keys are unique, looking one up returns exactly one value — and with hashing behind the scenes, it returns it almost instantly, no matter how many students are stored.

By the end of this page you will use the built-in dictionary, wrap it as a tidy ADT, build one yourself from plain arrays, and explain how a hash function turns a key into a storage position.

Below, Musarrat stores the marks of her revision group. Each name is a key; each mark is the value it maps to. To read it you never count positions — you simply follow the arrow from a key to its value.

marks = {"Aymaan": 72, "Mehrin": 85}   # create with two pairs
marks["Nazifa"] = 64                    # ADD a new pair
print(marks["Mehrin"])                  # LOOK UP a value -> 85
marks["Aymaan"] = 90                    # UPDATE (key exists -> overwrite)
del marks["Nazifa"]                     # DELETE a pair
if "Mehrin" in marks:                   # MEMBERSHIP test -> True
    print("found")

Notice that add and update use exactly the same line, marks[key] = value. Python decides which it is by whether the key already exists. That is the rule from Section 2 in action: a repeated key overwrites rather than duplicating.

class Dictionary:
    def __init__(self):
        self.items = {}                 # the private store

    def add(self, key, value):
        self.items[key] = value         # add or overwrite

    def get(self, key):
        if key in self.items:
            return self.items[key]      # found
        return None                     # not present -> safe answer

    def remove(self, key):
        if key in self.items:
            del self.items[key]

    def contains(self, key):
        return key in self.items        # True / False

Each method is one obvious job. get guards the look-up so it returns None instead of crashing — the safer behaviour. Because everything goes through these four methods, you could later swap the inner {} for your own hash table without changing any code that uses the dictionary.

The idea: Keys[i] and Values[i] belong together. To find a value you search Keys for the target; its index then points to the matching value.

Search Keys for “Mehrin” → index 1 → Values[1] = 85.

def lookup(self, target):
    for i in range(len(self.keys)):    # linear search
        if self.keys[i] == target:
            return self.values[i]      # lined-up value
    return None                        # key not found

This works, but every look-up may scan the whole keys array — slow once there are thousands of pairs. That weakness is exactly the problem hashing solves in the next section.

A hash function takes a key and returns an array index. A simple one for numeric IDs is index = key MOD tableSize. Below, IDs are stored in a table of size 7, so ID 52 lands at 52 MOD 7 = 3.

def hash_index(self, key):
    return key % self.size            # key MOD tableSize

def add(self, key, value):
    i = self.hash_index(key)
    self.table[i] = (key, value)      # store the pair at its slot

The catch: two different keys can hash to the same slot — a collision. For example 52 MOD 7 = 3 and 59 MOD 7 = 3 both want slot 3. A dictionary must handle this, commonly by open addressing (try the next free slot) or chaining (each slot holds a small list of pairs).

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked Python/pseudocode solution.