Почему Python использует хеш-таблицу для реализации dict, а не Red-Black Tree? [закрыто]

11

Почему Python использует хеш-таблицу для реализации dict, а не Red-Black Tree?

Какой ключ? Производительность?

longdeqidao
источник
2
Обмен вашими исследованиями помогает всем . Расскажите нам, что вы пробовали и почему это не соответствует вашим потребностям. Это свидетельствует о том, что вы потратили время, чтобы попытаться помочь себе, избавляет нас от повторения очевидных ответов и, прежде всего, помогает получить более конкретный и актуальный ответ. Также см. Как спросить
Гнат

Ответы:

16

Это общий, не специфичный для Python ответ.

Алгоритмическое сравнение сложности

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

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

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

Деревья RB самобалансируются и не изменяют свою алгоритмическую сложность в худшем случае. Однако их сложнее реализовать. Их средняя сложность также хуже, чем у хеш-таблицы.

Ограничения на ключи

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

Ключи в дереве RB должны иметь полный порядок: каждый ключ должен быть сопоставим с любым другим ключом, и оба ключа должны сравниваться как меньшие, большие или равные. Это упорядоченное равенство должно быть эквивалентно семантическому равенству. Это просто для целых чисел и других чисел, также довольно просто для строк (порядок должен быть только согласованным и не наблюдаемым извне, поэтому порядок не должен учитывать локали [1] ), но сложным для других типов, которые не имеют собственного порядка , Абсолютно невозможно иметь ключи разных типов, если не возможно некоторое сравнение между ними.

[1]: На самом деле я здесь не прав. Две строки могут не быть равными байту, но все равно быть эквивалентными в соответствии с правилами некоторых языков. См., Например, нормализации Unicode для одного примера, где две одинаковые строки кодируются по-разному. Вопрос о том, имеет ли значение композиция Unicode для вашего хеш-ключа, неизвестен для реализации хеш-таблицы.

Можно подумать, что дешевым решением для ключей RB-Tree было бы сначала проверить на равенство, а затем сравнить идентичность (т.е. сравнить указатели). Однако это упорядочение не будет транзитивным: если a == bи id(a) > id(c), то оно также должно следовать за этим id(b) > id(c), что здесь не гарантируется. Поэтому вместо этого мы можем использовать хеш-код ключей в качестве ключей поиска. Здесь порядок работает правильно, но мы можем получить несколько разных ключей с одинаковым хеш-кодом, которые будут назначены одному и тому же узлу в дереве RB. Чтобы решить эти коллизии хешей, мы можем использовать отдельную цепочку, как с хеш-таблицами, но это также наследует поведение наихудшего случая для хеш-таблиц - худшее из обоих миров.

Другие аспекты

  • Я ожидаю, что хеш-таблица будет иметь лучшую локальность памяти, чем дерево, потому что хеш-таблица по сути является просто массивом.

  • Записи в обеих структурах данных имеют довольно высокие издержки:

    • хеш-таблица: ключ, значение и указатель на следующую запись в случае отдельного сцепления. Также хранение хеш-кода может ускорить изменение размера.
    • RB-дерево: ключ, значение, цвет, левый дочерний указатель, правый дочерний указатель. Обратите внимание, что, хотя цвет - это один бит, проблемы с выравниванием могут означать, что вы все равно будете тратить достаточно места для почти целого указателя или даже почти для четырех указателей, когда можно выделить только блоки памяти размером с степень двух. В любом случае запись в дереве RB занимает больше памяти, чем запись в хэш-таблице.
  • Вставки и удаления в RB-дереве включают в себя повороты дерева. Это не очень дорого, но связано с накладными расходами. В хэше вставка и удаление не дороже, чем простой доступ (хотя изменение размера хеш-таблицы при вставке является O(n)попыткой).

  • Хеш-таблицы по своей природе являются изменяемыми, тогда как RB-дерево также может быть реализовано неизменным образом. Однако это редко полезно.

Амон
источник
Можем ли мы иметь хеш-таблицу с небольшими RB-деревьями для встречных хешей?
aragaer
@aragaer не совсем, но это было бы возможно в некоторых конкретных случаях. Однако коллизии обычно обрабатываются связанными списками - их гораздо проще реализовать, гораздо меньше накладных расходов и, как правило, гораздо более производительно, потому что у нас, как правило, очень мало коллизий. Если мы ожидаем много коллизий, мы могли бы изменить хеш-функцию или использовать более простое B-дерево. Самобалансирующиеся деревья, такие как RB-деревья, потрясающие, но во многих случаях они просто не повышают ценность.
Амон
Деревьям нужны объекты, которые поддерживают «<». Хеш-таблицам нужны объекты, которые поддерживают хэш + "=". Таким образом, деревья RB могут быть невозможны. Но на самом деле, если в вашей хеш-таблице имеется значительное количество коллизий, вам нужна новая хеш-функция, а не альтернативный алгоритм для коллизии ключей.
gnasher729
1

Существует целый ряд причин, которые могут быть правдой, но наиболее вероятными могут быть следующие:

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

Проще написать / поддерживать, и выиграть производительность в типичных случаях использования? Зарегистрируйтесь, пожалуйста!

Donal Fellows
источник