Реализация словаря в Python 2.7

Нет, не путаю. Ведь если бы значения считались равны в случае равенства их хэшей, то два разных значения с одинаковыми хэшами (то есть в случае коллизии) были бы равны, а это неправильно.
В данном случае для сравнения 1 и 1.0 (типы разные — int и float), в соответствии с методом float_richcompare (так как у объекта int не реализован метод tp_richcompare), значения 1 и 1.0 будут приведены к double и сравнены.

Реализация словаря в Python 2.7

Есть один нюанс, связанный с тем, что после того как хэш-таблица будет заполнена на 2/3 произойдёт изменение её размера.

однажды переведя (2/3)N — 1 ячеек словаря в состояние пустая

После того как 2/3*N-1, то есть 5 элементов (для начального размера таблицы) будут добавлены и затем удалены, следующий добавляемый элемент определит что произойдёт: либо размер таблицы изменится, либо «пустая» ячейка, то есть одна из удалённых, будет использована заново. Перед добавлением элемента имеем ma_used = 0, ma_filled = 5.
В первом случае, после того как будет добавлен новый 6 элемент, будем иметь ma_used = 1, ma_filled = 6. Таблица заполнилась больше чем на 2/3, соответственно произойдёт изменение размера. Новый размер таблицы будет рассчитан так:

minused = ma_used * 4 = 1 * 4 = 4
newsize = PyDict_MINSIZE = 8
while newsize <= minused and newsize > 0:
    newsize = newsize * 2

Коэффициент увеличения размера равен 4, так как размер таблицы меньше 50000 элементов.
Получим newsize = 8, то есть размер таблицы не изменился. В функции изменения размера произойдёт полная перестройка хэш-таблицы с учётом нового размера – все «активные» ячейки будут перераспределены, а «пустые» и «неиспользованные» ячейки будут проигнорированы. Операция перестройки хэш-таблицы выполняется за линейное время.
Таким образом, после добавления 6 элемента, получим новую хэш-таблицу с единственной «активной» ячейкой, содержащей 6 элемент (ma_used = 1, ma_filled = 1).
Во втором случае одна из удалённых, будет использована заново и изменения размера не произойдёт, так как в хэш-таблице всё ещё 5 элементов (ma_used = 1, ma_filled = 5). Но если добавить новый 6 элемент, будем иметь ma_used = 2, ma_filled = 6. Таблица заполнилась больше чем на 2/3, произойдёт изменение размера. Новый размер таблицы рассчитывается следующим образом:

minused = ma_used * 4 = 2 * 4 = 8
newsize = PyDict_MINSIZE = 8
while newsize <= minused and newsize > 0:
    newsize = newsize * 2

Получим newsize = 16, то есть новый размер таблицы равен 16. После перераспределения получим новую хэш-таблицу с двумя «активными» ячейками, содержащими 5 и 6 элементы (ma_used = 2, ma_filled = 2).
Рассмотрим пример первого случая:

>>> d = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
>>> d.__sizeof__()
248
>>> for i in xrange(5): del d[i]
...
>>> d.__sizeof__()
248
>>> d[5] = 5
>>> d.__sizeof__()
248

Как видно из результатов, размер после добавления 6 элемента остался прежний.
Теперь рассмотрим пример второго случая:

>>> d = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
>>> d.__sizeof__()
248
>>> for i in xrange(5): del d[i]
...
>>> d.__sizeof__()
248
>>> d[4] = 4
>>> d[5] = 5
>>> d.__sizeof__()
632

Здесь видно, что размер хэш-таблицы изменился.

Реализация словаря в Python 2.7

Это могло бы быть верно, если бы «пустые» ячейки не использовались заново, но из-за того, что они используются заново, а в хэш-таблице точно будет найдена «неиспользованная» ячейка, этого не произойдёт.

Реализация словаря в Python 2.7

В процедуре поиска выполняется проверка и если найденная ячейка окажется «пустая» она сохранится и начнётся или продолжится пробирование. Когда будет найдена «неиспользованная» ячейка, то сохранённая найденная «пустая» ячейка будет использована заново.
Получается фактически, что при добавлении нового элемента (отсутствующего в словаре) поиск остановится только когда будет найдена «неиспользованная» ячейка.

Реализация словаря в Python 2.7

пришлось ввести понятия неиспользованной и пустой ячеек.

Насколько я понимаю, использование флага для определения удалён ли элемент в ячейке или нет, это общепринятая практика в методе открытой адресации. В данном случае флагом служит состояние ячейки.

Это необходимо для корректной остановки процедуры поиска элемента — останавливаться только, когда элемент найден или попалась неиспользованная ячейка в процессе пробирования (пустая ячейка никак не влияет на процесс)…

Это действительно необходимо для корректной работы поиска. «Пустая» ячейка всё-таки влияет на процесс, так как позволяет продолжить пробирование. Если бы при пробировании мы бы попали в удалённую ячейку, но её состояние не было бы помечено как «пустая», то поиск бы закончился, хотя на следующих шагах пробирования могла быть найдена искомая ячейка.

В то же время процедура вставки элемента в словарь должна останавливаться, когда найдется либо неиспользованная либо пустая ячейка.

Процедура поиска ячейки для вставки элемента в словарь остановится только когда будет найдена «неиспользованная» ячейка.

Реализация словаря в Python 2.7

В общем случае сложность поиска, добавления и удаления выполняется за константное время. Сложность поиска и добавления будет линейна от размера таблицы только в худшем случае (когда при пробировании будут последовательно происходить коллизии). Например если добавлять элементы, хэши ключей которых будут одинаковые, но сами ключи при этом разные.

Реализация словаря в Python 2.7

При добавлении элемента в ячейку, me_value становится != NULL, то есть она переходит в состояние «активная». Это единственное состояние (имеется ввиду единственное из трёх возможных), когда me_value != NULL. В примерах, в основном, происходит как раз добавление элементов.

Реализация словаря в Python 2.7

Совершенно верно. Если хэши значений оказались одинаковыми, сравниваются сами значения. А так как 1 == 1.0, считается что элемент уже есть в словаре и его значение обновляется.

Реализация словаря в Python 2.7

Да хороший доклад. Эта ссылка уже есть в статье.

Реализация словаря в Python 2.7

Спасибо. Теперь планирую разобраться как устроен словарь в Python 3. Судя по исходникам он претерпел кое-какие изменения.