Хеш-таблицы и деревья AVL выполняют принципиально разные функции.Короче говоря, хеш-таблица предназначена для поиска, тогда как древовидная структура предназначена для поиска и обхода.
Хеш-таблица обеспечивает очень быстрый поиск значений, связанных с отдельными ключами.Если вы вставили значение с ключом «xqj57», вы можете быстро получить его.И если «xqj57» не был вставлен, поиск скажет, что такой записи не существует.И вставка, и поиск являются операциями O (1).
Деревья AVL и подобные структуры хороши для хранения вещей в отсортированном порядке.Это позволяет вам обходить структуру в отсортированном порядке, а также позволяет легко, по порядку, извлекать по порядку все записи, ключ которых начинается с «A», или получать первую запись, ключ которой больше или равен «foo»,и т.д. Вставка и поиск - это O (log n) операций.Обход, конечно, O (n).
Если вы хотите просмотреть хеш-таблицу в отсортированном порядке, вам придется сначала отсортировать ее.
Хеш-таблица имеет немногодополнительные накладные расходы памяти по сравнению с древовидной структурой, но не , что много.
Если ключи не являются исключительно длинными или если ваша функция хеширования действительно сложна, стоимость вычисления значения хеш-функции дляКлюч дешевый по сравнению со стоимостью сравнения ключей в журнале (n), который вам нужно сделать, чтобы найти что-то в древовидной структуре.
Если вы просто хотите быструю вставку и поиск, тогда трудно победитьхеш-таблица.Если вы хотите работать с отсортированным списком, то хеш-таблица определенно не подходит.Дерево AVL, красно-черное дерево, список пропусков или другая подобная отсортированная структура будет работать лучше.