Dictionaries and Maps

Key-value pairs and unique keys

A dictionary is a collection of key-value pairs. Each entry binds a key to a value, and you retrieve, change, or remove a value by naming its key rather than by naming a position. NIST's Dictionary of Algorithms and Data Structures defines the same structure, under the name associative array, as a collection of items randomly accessible by a key. The word 'randomly accessible' here means direct access — you jump straight to the entry you asked for — not that anything is chosen at random.

Two rules define the structure. First, keys are unique within one dictionary: assigning to a key that already exists overwrites its value rather than creating a second entry, so there is exactly one value per key. Second, keys must be of a type the implementation can handle deterministically — in practice an immutable, hashable type such as a string, number, or tuple of those. Values carry no such restriction; a value can be any object, including another dictionary. Because entries are found by key, the natural questions a dictionary answers are 'what value is filed under this key?' and 'is this key present?' — not 'what is the tenth entry?'

How hashing makes lookup fast

The usual implementation is a hash table. A hash function turns each key into a number that selects a slot in an underlying array, so the dictionary can compute where a key's value should live and go straight there instead of scanning. NIST defines a hash table as a dictionary in which keys are mapped to array positions by hash functions. When two different keys map to the same slot, that is a collision, and the table needs a resolution strategy — commonly chaining (a small list at each slot) or probing (trying nearby slots).

With a good hash function and enough room in the table, the number of keys sharing any one slot stays small, so lookup, insertion, and deletion each take average-case O(1) time — constant, independent of how many entries the dictionary holds. This is the headline property of dictionaries and the reason they are everywhere. The cost is not free: the table trades extra memory (empty slots that keep collisions rare) for that speed, a classic space-for-time trade-off. The worst case is genuinely worse. If a poor hash function or adversarial keys pile many entries into the same slot, the structure degenerates toward a single long list and an operation can take O(n) time, linear in the number of entries. Well-engineered library dictionaries make the worst case rare, but it is real, which is why we describe dictionary performance as average-case O(1), worst-case O(n).

Ordering, and the same idea under many names

Abstractly, a map is unordered: it is defined by which keys map to which values, not by any sequence. Historically that meant you could not rely on the order entries came back when you iterated. Concrete implementations differ, though, and this is a place where language matters. Python guarantees that a dict yields its keys in insertion order — the order in which they were first added. That behavior was a CPython implementation detail in version 3.6 and was written into the language specification in Python 3.7. 'Insertion order' is not the same as 'sorted': the entries come back in the order you added them, not alphabetically or numerically, and if you need sorted output you must sort explicitly. Many other languages' plain hash maps make no ordering promise at all.

The structure also travels under several names, which trips up students reading across sources. Python calls it a dictionary; much of computer science and many languages call it a map or hash map; the classical data-structures term is associative array. These are names for the same abstract data type: unique keys mapping to values, accessed by key. When you meet 'HashMap' in Java, 'object'/'Map' in JavaScript, 'dict' in Python, or 'associative array' in a textbook, read them as the same tool with local spelling and local guarantees about ordering and worst-case behavior.

Where dictionaries fit among data structures

It helps to place the dictionary beside the structures it resembles. An array or a Python list is indexed by integer position: element zero, element one, and so on, with O(1) access when you already know the position. A dictionary is indexed by key, so you look things up by a meaningful label — a username, a product code, a word — and you neither know nor care where it sits internally. Use an array or list when your data is naturally a sequence and position matters; use a dictionary when your data is naturally a set of labeled facts and you will look them up by that label. Membership tests show the contrast sharply: asking 'is this value in the collection?' is O(n) in an unsorted list because you may scan every element, but asking 'is this key in the dictionary?' is average-case O(1). That single difference is why counting occurrences, caching results, de-duplicating by identifier, and joining records are all textbook jobs for a dictionary.