4.2.6.1, 4.2.7.1 - Hash tables and dictionaries (Python)
Use keys to retrieve values, apply a simple hash function and rehashing rule, and build Python dictionaries for practical information retrieval.
Key-value structures
A key-value structure retrieves a value through an associated key rather than through the value's position in a sequence.
Dictionary
A collection of key-value pairs in which a value is accessed using its associated key.
A library can associate an accession number with a book record, or a word with its frequency. Keys must uniquely identify entries: assigning a new value to an existing key updates that entry rather than creating a second pair with the same key. A value need not be unique; two books can have the same author.
A hash table implements key-value mapping by calculating a storage location from a key. A dictionary is the abstract keyed collection; a hash table is one possible implementation. Python's built-in dict uses hashing internally, but its actual storage and collision resolution need not match the simple educational array model below. Python dictionary keys must be hashable, such as strings, integers or suitable immutable tuples; a mutable list cannot be a key. Values can be mutable objects.
Simple hashing
A hash function converts a key into a candidate index within the table's capacity.
For non-negative integer keys and a table of size seven, use . Key 10 maps to index 3 because the division remainder is 3. Key 20 maps to index 6. Indices range from zero to six. To hash text in a simple exercise, sum character codes and take the remainder: sum(ord(c) for c in key) % size. This may distribute keys poorly; the hash function does not preserve alphabetic or numeric ordering.
The key must be stored alongside its value because two keys can map to the same index. Hashing is not reversible identification and it is not encryption. A successful lookup verifies the stored key, rather than assuming any value at the computed location belongs to the requested key. If keys are spread well and the table is not crowded, keyed operations can be fast; a worst case with many collisions needs more comparisons.
Collisions and rehashing
A collision occurs when different keys compute the same hash, so insertion must follow an agreed alternative-location rule.
In this lesson, rehashing means computing the next candidate location after a collision. We use linear probing: (index + 1) % size. Other rehashing rules are possible; apply the one the task gives. Some software uses the term rehashing for rebuilding a resized table, so state the intended meaning rather than assuming one rule everywhere.
For a seven-slot empty table, insert key 10 at 3, then key 17: its initial index is also 3, so probe 4. Key 24 starts at 3 and probes 4 then 5. To retrieve 24, follow the same sequence and compare keys until finding 24 or a never-used empty slot. Stop after at most the table's capacity in probes; otherwise a full table and an absent key could cause an infinite loop. Adding a pair with an existing key updates its value. Removing from an open-addressed table needs care: simply turning a middle slot into a never-used empty slot can break later searches. A deleted-slot marker or a correctly rebuilt probe cluster avoids that problem.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account