Почему Python использует хеш-таблицу для реализации dict, а не Red-Black Tree?
Какой ключ? Производительность?
python
data-structures
longdeqidao
источник
источник
Ответы:
Это общий, не специфичный для Python ответ.
Алгоритмическое сравнение сложности
Проблема с хеш-таблицами заключается в том, что хеш-коды могут конфликтовать. Существуют различные механизмы разрешения коллизий, например, открытая адресация или отдельная цепочка. В худшем случае все ключи имеют одинаковый хеш-код, и в этом случае хеш-таблица будет преобразована в связанный список.
Во всех других случаях хеш-таблица - это отличная структура данных, которую легко реализовать и которая обеспечивает хорошую производительность. Недостатком является то, что реализации, которые могут быстро увеличить таблицу и перераспределить свои записи, вероятно, будут тратить почти столько же памяти, сколько фактически используется.
Деревья RB самобалансируются и не изменяют свою алгоритмическую сложность в худшем случае. Однако их сложнее реализовать. Их средняя сложность также хуже, чем у хеш-таблицы.
Ограничения на ключи
Все ключи в хеш-таблице должны быть хешируемыми и сопоставимыми для равенства между собой. Это особенно легко для строк или целых чисел, но также довольно просто распространить на определенные пользователем типы. В некоторых языках, таких как Java, эти свойства гарантированы по определению.
Ключи в дереве RB должны иметь полный порядок: каждый ключ должен быть сопоставим с любым другим ключом, и оба ключа должны сравниваться как меньшие, большие или равные. Это упорядоченное равенство должно быть эквивалентно семантическому равенству. Это просто для целых чисел и других чисел, также довольно просто для строк (порядок должен быть только согласованным и не наблюдаемым извне, поэтому порядок не должен учитывать локали [1] ), но сложным для других типов, которые не имеют собственного порядка , Абсолютно невозможно иметь ключи разных типов, если не возможно некоторое сравнение между ними.
[1]: На самом деле я здесь не прав. Две строки могут не быть равными байту, но все равно быть эквивалентными в соответствии с правилами некоторых языков. См., Например, нормализации Unicode для одного примера, где две одинаковые строки кодируются по-разному. Вопрос о том, имеет ли значение композиция Unicode для вашего хеш-ключа, неизвестен для реализации хеш-таблицы.
Можно подумать, что дешевым решением для ключей RB-Tree было бы сначала проверить на равенство, а затем сравнить идентичность (т.е. сравнить указатели). Однако это упорядочение не будет транзитивным: если
a == b
иid(a) > id(c)
, то оно также должно следовать за этимid(b) > id(c)
, что здесь не гарантируется. Поэтому вместо этого мы можем использовать хеш-код ключей в качестве ключей поиска. Здесь порядок работает правильно, но мы можем получить несколько разных ключей с одинаковым хеш-кодом, которые будут назначены одному и тому же узлу в дереве RB. Чтобы решить эти коллизии хешей, мы можем использовать отдельную цепочку, как с хеш-таблицами, но это также наследует поведение наихудшего случая для хеш-таблиц - худшее из обоих миров.Другие аспекты
Я ожидаю, что хеш-таблица будет иметь лучшую локальность памяти, чем дерево, потому что хеш-таблица по сути является просто массивом.
Записи в обеих структурах данных имеют довольно высокие издержки:
Вставки и удаления в RB-дереве включают в себя повороты дерева. Это не очень дорого, но связано с накладными расходами. В хэше вставка и удаление не дороже, чем простой доступ (хотя изменение размера хеш-таблицы при вставке является
O(n)
попыткой).Хеш-таблицы по своей природе являются изменяемыми, тогда как RB-дерево также может быть реализовано неизменным образом. Однако это редко полезно.
источник
Существует целый ряд причин, которые могут быть правдой, но наиболее вероятными могут быть следующие:
Проще написать / поддерживать, и выиграть производительность в типичных случаях использования? Зарегистрируйтесь, пожалуйста!
источник