сравните Хеш с Деревом двоичного поиска
Для справедливо in-your-face пример различия между процедурным и OO, попытайтесь изучить Smalltalk. В Smalltalk, всем, и я подразумеваю, что все - объект. Нет никаких операторов "if" или циклов с условием продолжения. Вы достигаете той функциональности путем отправки сообщений в (иначе вызов методов на) другие объекты. Это действительно заставляет Вашу голову кружиться сначала, но я думаю, что Вы будете быстро grok, что OO, как предполагается.
7 ответов
Деревья допускают обход по порядку.
В худшем случае производительность для хеш-таблицы составляет O (N) (линейный поиск по одному сегменту), двоичный поиск ограничен O (журнал N).
NB: это требует, чтобы дерево было сбалансировано - вот почему типичная реализация использует самобалансирующееся дерево, например, красно-черное дерево.
Хотя такое ухудшение маловероятно, оно не невозможно и сильно зависит от возможность выбирать подходящую хеш-функцию и распределение фактических данных.
Реализация дерева также тривиально увеличивается до необходимого размера, тогда как хэш-карта начинает ухудшаться, когда она заполняется (для большинства реализаций сообщается, что заполнено около 70% корзин). Вам нужно либо перефразировать всю таблицу (опять же, плохо для приложений реального времени), либо постепенно переходить к новой таблице,
To add on peterchen answer, hash structures although theoretically faster at insertion and removal depend vastly on the actual data, the chosen hash function and the amount of data.
- A perfect hash function depends on the amount and distribution of the data.
Having large performance variations between best and worst cases makes them unfit for general purpose structures. Binary trees on the other hand are more predictable independently of the amount/type of data used, even though less efficient on best case scenario.
Изначально STL не включала хеш-таблицу среди контейнеров, поскольку хеш-таблицы более сложны - вам нужно выбирать между открытой и закрытой адресацией, не говоря уже о хеш-функции и т. Д. В то время Степанов и Страуструп пытались ускорить работу над этим, чтобы он был быстро принят в стандарт.
Деревья, с другой стороны, относительно проще. Уже было известно, что, поскольку это структуры данных в памяти, мы можем просто использовать двоичное дерево вместо B-дерева. Тогда был выбор между деревьями AVL и RB. Деревья RB, как правило, выбираются из-за лучших характеристик производительности, которые я не могу комментировать, но статьи в Википедии по обеим структурам ( AVL и RB ) расскажут вам больше с относительно хорошей детализацией.
В противном случае, деревья и хеш-таблицы хороши для разных целей. Если вам нужны быстрые вставки или извлечения, и вам не важен порядок их хранения, подойдут хэш-таблицы. Если вам нужны упорядочивающие характеристики и строгие гарантии вставки и извлечения, тогда подойдут двоичные деревья. Еще одно хорошее практическое правило - профилирование. Поскольку в большинстве случаев любой из них будет совместим с интерфейсом, помогает также профилирование, чтобы увидеть, что дает вам лучшую производительность.
Вы можете получить доступ к данным в двоичном дереве поиска по порядку.
Во времена C ++ люди все еще были поклонниками жесткого академического подхода к структурам данных и алгоритмам, поэтому они предпочитали структуры с меньшим объемом памяти и хорошо понимаемым поведением в лучшем и худшем случае. .
К тому времени, когда появился Ruby, люди поняли, что для целей создания сценариев они предпочитают простоту чистой производительности, и поскольку хэш-таблицы допускают семантику обоих массивов (если вы используете в качестве ключа последовательный индекс) И словарей (если вы используете естественный ключ), они рассматривались как более универсальная структура данных.
Чтобы использовать дерево, вам нужен способ упорядочить элементы в дереве. Чтобы использовать хеш-таблицу, вам нужна функция для вычисления хеш-значения элемента в хеш-таблице.
Интересно, что платформа .NET требует, чтобы каждый класс реализовал (или наследовал) функцию GetHashCode , позволяющую каждому объект для хранения в хеш-таблице. Однако это также добавляет дополнительную нагрузку на разработчиков, которые должны реализовывать семантически правильные хэш-функции, даже если они не предполагают, что класс будет хеширован. Одно из решений - вернуть постоянное значение из GetHashCode , которое является семантически правильным, но не очень эффективным, если функция когда-либо будет использоваться для хеширования.