Сравнение методов

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

 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.2 сравниваются времена поиска для каждого алгоритма. Обратите внимание на то, что наихудшие случаи для хеш-таблиц и разделенных списков чрезвычайно маловероятны. Экспериментальные данные описаны ниже.
• Простота. Если алгоритм короток и прост, при его реализации и/или использовании ошибки будут допущены с меньшей вероятностью. Кроме того, это облегчает проблемы сопровождения программ. Количества операторов, исполняемых в каждом алгоритме, также содержатся в таблице 3.2.