Original Translation
107
Python's lists are really variable-length arrays, not Lisp-style linked lists. The implementation uses a contiguous array of references to other objects, and keeps a pointer to this array and the array's length in a list head structure.
108
This makes indexing a list ``a[i]`` an operation whose cost is independent of the size of the list or the value of the index.
109
When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don't require an actual resize.
110
How are dictionaries implemented?
111
Python's dictionaries are implemented as resizable hash tables. Compared to B-trees, this gives better performance for lookup (the most common operation by far) under most circumstances, and the implementation is simpler.
á é í ó ú ç ñ ü ¿ ¡
112
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.
113
Why must dictionary keys be immutable?
114
The hash table implementation of dictionaries uses a hash value calculated from the key value to find the key. If the key were a mutable object, its value could change, and thus its hash could also change. But since whoever changes the key object can't tell that it was being used as a dictionary key, it can't move the entry around in the dictionary. Then, when you try to look up the same object in the dictionary it won't be found because its hash value is different. If you tried to look up the old value it wouldn't be found either, because the value of the object found in that hash bin would be different.
115
If you want a dictionary indexed with a list, simply convert the list to a tuple first; the function ``tuple(L)`` creates a tuple with the same entries as the list ``L``. Tuples are immutable and can therefore be used as dictionary keys.
116
Some unacceptable solutions that have been proposed: