Сравнение методов организации словарей.

Мы рассмотрели несколько методов организации словарей: хеш-таблицы, несбалансированные двоичные деревья, красно-черные деревья и разделенные списки. Имеются несколько факторов, которые влияют на выбор алгоритма в конкретной ситуации:

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

 void WalkTree(Node *P) {
     if (P == NIL) return;
     WalkTree(P->Left);
     /* Здесь исследуем P->Data */
     WalkTree(P->Right);
 }
 WalkTree(Root);

Чтобы получить отсортированный список узлов разделенного списка, достаточно пройтись по ссылкам нулевого уровня. Вот так:

Node *P = List.Hdr->Forward[0];
while (P != NIL) {
    /* Здесь исследуем P->Data */
    P = P->Forward[0];

}

• Для хеш-таблиц требуется только один указатель на узел. Кроме того, требуется память под саму таблицу.
• Для красно-черных деревьев в каждом узле нужно хранить ссылку на левого и правого потомка, а также ссылку на предка. Кроме того, где-то нужно хранить и цвет узла! Хотя на цвет достаточен только один бит, из-за выравнивания структур, требуемого для эффективности доступа, как правило, будет потрачено больше места. Таким образом, каждый узел красно-черного дерева требует памяти, которой хватило бы на 3-4 указателя.
• Для разделенных списков в каждом узле имеется ссылка нулевого уровня. Вероятность иметь ссылку уровня 1 равна 1/2. Вероятность иметь ссылку уровня 2 равна 1/4. В общем, количество ссылок на узел равно
n = 1 + 1/2 + 1/4 + ... = 2.

В таблице 3-3приводится среднее время вставки, поиска и удаления 65,536 (2¹⁶) случайных элементов. В этом эксперименте размер хеш-таблицы равнялся 10009, для слоёных списков допускалось до 16 слоев. Хотя некоторое различие времен для этих четырех методов и наблюдается, результаты достаточно близки, так что для выбора алгоритма нужны какие-то другие соображения.

В таблице 3.4 приведены средние времена поиска для двух случаев: случайных данных, и упорядоченных, значения которых поступали в возрастающем порядке. Упорядоченные данные являются наихудшим случаем для несбалансированных деревьев, поскольку дерево вырождается в обычный односвязный список. Приведены времена для "одиночного" поиска. Если бы нам понадобилось найти все 65536 элементов, то красно-черныму дереву понадобилось бы .6 секунд, а несбалансированному - около 1 часа.