From b20a019d467daad5a6e2856a36fca4d90904f969 Mon Sep 17 00:00:00 2001 From: Georg Brandl Date: Wed, 14 Mar 2012 07:50:17 +0100 Subject: [PATCH] Closes #14298: update section about dict implementation. --- Doc/faq/design.rst | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) diff --git a/Doc/faq/design.rst b/Doc/faq/design.rst index 1521f6c089..5441fd448a 100644 --- a/Doc/faq/design.rst +++ b/Doc/faq/design.rst @@ -526,14 +526,16 @@ far) under most circumstances, and the implementation is simpler. Dictionaries work by computing a hash code for each key stored in the dictionary using the :func:`hash` built-in function. The hash code varies widely depending -on the key; for example, "Python" hashes to -539294296 while "python", a string -that differs by a single bit, hashes to 1142331976. The hash code is then used -to calculate a location in an internal array where the value will be stored. -Assuming that you're storing keys that all have different hash values, this -means that dictionaries take constant time -- O(1), in computer science notation --- to retrieve a key. It also means that no sorted order of the keys is -maintained, and traversing the array as the ``.keys()`` and ``.items()`` do will -output the dictionary's content in some arbitrary jumbled order. +on the key and a per-process seed; for example, "Python" could hash to +-539294296 while "python", a string that differs by a single bit, could hash +to 1142331976. The hash code is then used to calculate a location in an +internal array where the value will be stored. Assuming that you're storing +keys that all have different hash values, this means that dictionaries take +constant time -- O(1), in computer science notation -- to retrieve a key. It +also means that no sorted order of the keys is maintained, and traversing the +array as the ``.keys()`` and ``.items()`` do will output the dictionary's +content in some arbitrary jumbled order that can change with every invocation of +a program. Why must dictionary keys be immutable? -- 2.50.1