#записки_на_полях
Замечена интересная особенность в Python: множества с "малыми" числами печатаются по возрастанию:
Хотя, казалось бы, сет должен печатать каждый раз вразнобой, ибо является неупорядоченной коллекцией. Но, на самом деле, set никому ничего не должен :-) Я порылась в нескольких статьях и документации и на своем уровне (червяка) вот что поняла:
Множества (и ключи к словарям) реализуются на основании хэш‑таблиц: каждый элемент множества хэшируется с помощью hash(), хэш элемента является его ключом (зная хэш → знаем элемент), а далее эта парочка хэш — элемент помещаются в хэш‑таблицу по соответствующему индексу.
Хэш‑таблица представляет собой два столбца из не менее 8 строк:
первый столбец — хэш элемента;
а второй — ссылка на элемент множества.
Каждая строка таблицы называется bucket.
Сначала Python создает пустую таблицу, состоящую из 8 строк. В поле для хэша в каждой строке (bucket) помещается ''-1», что означает «нет хэша». По мере добавления хэшей в таблицу, Python следит за тем, чтобы как минимум 1/3 buckets были пустыми, удваивая размер таблицы, когда требуется больше места (это делается, чтобы было место для коллизий).
Чтобы заполнить строку по соответствующему индексу в таблице (хотя индексов как таковых нет, ибо они нигде не хранятся, а каждый раз вычисляются), Python берет хэш‑код по модулю размер таблицы, то есть берет остаток от деления хэша на размер таблицы (оператор% в Python).
Хэш строк, например, при перезапуске может быть разным, т.к. hash() добавит разную соль (надо проверить!). Но для «малых» int хэш будет равен самому числу всегда:
Тут сразу всплывает вопрос, а что такое «малое» число? До Python3 все было понятно, а теперь надо еще разобраться (в другой заметке).
Разберем множество {35, 3, 6, 2, 7, 1, 11, 9}. Python все время будет выводить на печать:
В этом множестве все числа «малого» размера, поэтому хэши у них будут соответствующие.
Элементов сета len(first_set) = 8. Помним, что минимум 1/3 buckets должны быть пустыми. То есть, как я понимаю, Python должен взять таблицу, состоящую из 8 * 2 = 16 строк (чтобы не менее 1/3, то есть 5 строк были пустыми).
Как я вижу, что Python отсортирует числа по возрастанию, найдет их хэши, а потом, вычислив индексы, будет заполнять таблицу:
Дойдя до числа 35, у которого индекс тоже 3, который уже занят в таблице (коллизия), Python проверит хэш (если хэш одинаковый, то Python поймет, что элемент уже в таблице, а это повторяющийся и не нужен, ибо set — это множество уникальных элементов). А если хэш различается, то элемент другой (у нас 3 и 35). Тогда Python начинает искать пустую ячейку. Пишут, что в Python используется метод квадратичного зондирования, то есть: если слот hash(x)% S заполнен, то мы пробуем (hash(x) + 1*1)% S.
В нашем случае 3 заполнен, мы пробуем (3 + 1)% 16 → 4. Таким образом, 35 идет в bucket с индексом 4 и у нас получается вывод сета на печать:
В CPython, кстати, пишут, что используется случайный поиск (псевдослучайный порядок), но я не заметила...
С примером вывода set(35, 3, 6, 2, 7, 1, 11, 9) на печать что‑то логичное вырисовывается, если предположить, что при заполнении хэш‑таблицы Python сначала сортирует числа. Ибо если бы он не сортировал их, то по указанному алгоритму указанный сет должен выводиться на печать в таком «порядке»: {1, 2, 35, 3, 6, 7, 9, 11}.
Для меня остается пока загадкой, что происходит с вот таким set(20, 35, 3, 6, 2, 7, 1, 11, 9)? Как он размещается в таблице, если вывод на печать:
20% 16 = 4
И по описанному алгоритму, должно бы выводиться на печать {1, 2, 3, 20, 6, 35, 7, 9, 11}
У 35 индекс 3, поменялся на 4 (опять занят), тогда (hash(x) + 2*2)% S → 7. У числа 7 индекс 7, но занят, (hash(7) + 1*1)% 16 = 8. Но все совсем не так.
Как же тогда заполняются хэш‑таблицы для int????
Статьи: