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

[CrazyOpossum]

Спасибо.
У вас псевдокод во фреймах с подсветкой Питона, после первой кавычки всё зеленеет. Попробуйте поиграть с подсветкой, а лучше поменяйте на честный Питон, все всё поймут :)

[galaxy]

Мы могли бы использовать связанный список для хранения пар, имея при этом один и тот же хэш, но это бы увеличило время поиска, и оно бы не равнялось уже в среднем O(1).

По-моему, что пнем об сову, что наоборот. При поиске придется использовать пробирование, что мало отличается от перебора связного списка.

[Tishka17]

Вообще, отличается. В связном списке у вас будут все элементы, у которых совпали n-бит хэша. А при пробировании, будут учтены другие биты и количество проб может быть меньше

[miksir]

Немного не понял идеи, поясните?
Первый тест, который приводит к коллизии, все-равно ориентируется на n бит хеша.
Если k ключей попали под такую коллизию, то для поиска k-того ключа нужно или пройтись по всем элементам связанного списка или по всем ключам в порядке пробирования, т.е. тоже самое число итераций.

[Tishka17]

Первый тест ориентируется на n бит хэша. Для второго теста — уже другое количество бит и не факт, что хоть у кого-то их тех k ключей будет снова коллизия.

[miksir]

Да, точно, спасибо

[Hivemaster]

На Хабре это уже третья или четвёртая статья на эту тему.

[jandevel]

Никого не смущает, что это неудачный перевод (без указания авторства) вот этой статьи?
www.laurentluce.com/posts/python-dictionary-implementation