الدرس 13 · Data structures

Hash maps: finding things by key

لم يُترجم بعد؛ يُعرض باللغة الإنجليزية

A dictionary lets a program find a value by its key, such as a person's age by their name, without searching through everything. Step through ten lines of Python and watch a hash function turn each key into a number that picks a slot, see what happens when two keys want the same slot, how the table grows when it fills up, and why some values cannot be keys.

11 دقيقة10 خطوات5 أسئلةBeginner

شكل 13 · تفاعلي

جارٍ تحميل الرسم…

أو ← →

اختبر نفسك

5 أسئلة سريعة

اختر إجابة لتعرف السبب. تُحفَظ نتيجتك مع تقدّمك.

01With the figure's toy hash, a key hashes to 29 and the table has 8 slots. Which slot does it go to?

The slot is the remainder after dividing by the table size: 29 % 8 = 5, because 8 × 3 = 24 and 29 − 24 = 5.

02Why is looking up a key in a dict usually fast, even when the dict is big?

Hashing the key gives the slot to look in directly, so on average a lookup takes the same short time however many keys there are: O(1).

03Two different keys pick the same slot. What is this called, and what does Python do?

Two keys wanting one slot is a collision. Python uses open addressing: it tries other slots in the same table until it finds a free one, and a lookup later follows the same path.

04What happens when you run d = {} then d[[1, 2]] = "x" ?

A list can change, so its hash could change and Python would look in the wrong slot. Lists are unhashable and cannot be keys; a tuple such as (1, 2) can.

05A dict has a table of 8 slots and already holds 5 keys. What happens when you add a 6th key?

CPython lets an 8-slot table hold at most 5 keys, so collisions stay rare. The 6th key makes a new table of 16 slots, and every key is placed again with % 16.

المصطلحات الأساسية

المسرد

Dictionary (dict): Python's built-in hash map: a collection that maps keys to values, written like {"ann": 31}.
Key and value: In ages["ann"] = 31, "ann" is the key you look things up by and 31 is the value stored with it.
Hash function: A function that turns a key into a whole number. The same key always gives the same number while the program runs.
Slot (bucket): One place in the hash table's row. The remainder after dividing the key's hash by the number of slots picks the slot.
Collision: When two different keys pick the same slot.
Open addressing: Handling a collision by searching for another free slot in the same table. Python's dict works this way.
Hashable: A value whose hash never changes, so it can be a key. Strings, numbers and tuples of them are hashable; lists and dicts are not.
O(1): "Constant time": the work does not grow as the collection grows. A dict lookup is O(1) on average.

تفاصيل إضافية

الملاحظات والمصادر

The figure uses a toy hash (add up letter positions) so you can check the sums. Python's real hash() for text gives a huge number, and it changes every time Python starts, so never rely on its value.
On a collision the figure tries the next slot (called linear probing). CPython also uses open addressing, but its search jumps around the table in a fixed pattern based on the hash, which spreads crowded keys out.
The sizes are CPython's: the first key added gets a table of 8 slots (an empty {} holds no table yet), and Python lets at most two thirds of them be used (5 of 8, 10 of 16). Adding the 6th key builds a table of 16.
Since Python 3.6, CPython keeps the keys and values in a separate list in the order they were added; the table of slots only holds positions in that list. That is how a dict keeps insertion order cheaply.
O(1) means the time does not grow with the number of keys. It is the average: if many keys collide, a lookup can take longer, up to checking every key in the worst case.

اختبار يتاح بعد الخطوة الأخيرة.