Комментарии 4
Built-in функция hash() работает напрямую с built-in типами и переключается на вызов __hash__ для типов, определяемых пользователем. Если два объекта сравниваются между собой, их хэш-коды также должны быть одинаковыми, иначе алгоритм хэш-таблицы не работает. Например, поскольку 1 == 1.0 — это True, то hash(1) == hash(1.0) тоже должно быть True, даже несмотря на то, что внутренние представления int и float сильно отличаются(1).
Повторяется 2 раза подряд
Почему Python не использует цепочки указателей? Из-за нарушения локальности?
все интересное происходит при удалении -- если нам надо удалить первый элемент, приведший к коллизии. Если мы просто вычеркнем его из таблицы, то потом рискуем не найти элемент, который столкнулся с удаленным. Поэтому вводят флаги - признаки - этот слот "просто пустой" и не инициализирован или "там было что-то" и поэтому при lookup нам нужно продолжить поиск до "просто пустой" -- согласитесь, это важный элемент устройства хеш таблиц с открытым размещением.
Публикации
Python. Внутреннее устройство множеств set и словарей dict. Часть 1 из 2