Да, у меня когда я первый раз читал про Хэш Тейбл был такой же вопрос :)
Далее цитата из статьи: Эти две проблемы связаны: очевидно, что мы не можем вычислять длинные хэши если хотим хранить небольшое количество элементов — это приведет к неоправданым затратам памяти, потому хэш функция обычно выглядти как то так:
index = f(key, arrayLength)
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда.
1. Сейчас исправлю.
2. К сожалению подробно не мог рассмотреть все хэши в рамках одной статьи, если рассматривать подробно и все вариации — то на каждую структуру можно по отдельной статье написать (хотя, возможно они этого заслуживают).
Это слегка мутировавший вектор. Массив, на котором он базируется — является массивом ссылок на элементы произвольного типа.
Смотрим сорсы в них include/listobject.h
Там видим:
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
Автор открыл для себя то, что в асинхронном приложении тоже бывают проблемы с конкурентным доступом, и хотел этим поделиться. Ну и DeferredLock он тоже для себя открыл, написав вначале штуки 2 вариаций «на тему».
Далее цитата из статьи:
Эти две проблемы связаны: очевидно, что мы не можем вычислять длинные хэши если хотим хранить небольшое количество элементов — это приведет к неоправданым затратам памяти, потому хэш функция обычно выглядти как то так:
index = f(key, arrayLength)
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда.
2. К сожалению подробно не мог рассмотреть все хэши в рамках одной статьи, если рассматривать подробно и все вариации — то на каждую структуру можно по отдельной статье написать (хотя, возможно они этого заслуживают).
Смотрим сорсы в них include/listobject.h
Там видим: