Алгоритм Робина Гуда очень умный, но он зависит от наличия хорошей хэш-функции так же, как и любая другая техника открытого хеширования.
В худшем случае рассмотрим наихудшую из возможных хеш-функций:
int hash(const char* key) { return 0; }
Поскольку при этом каждый элемент сопоставляется с одним и тем же слотом, легко увидеть, что общее количество проб является квадратичным по количеству записей: первая вставка успешно выполняется на первом пробе;вторая вставка требует двух зондов;третий - три зонда;и так далее, в результате чего получается n(n+1)/2 проб для n вставок.Это верно независимо от того, используете ли вы простое линейное зондирование или зондирование Робина Гуда.
Интересно, что эта хеш-функция может вообще не влиять на вставку в цепочечную хеш-таблицу, если - и это очень большая , если - не предпринимается попытка проверить, является ли вставленный элемент уникальным.(Это имеет место в коде, который вы представляете, и это не является абсолютно необоснованным; вполне возможно, что хеш-таблица строится как фиксированная таблица поиска, и уже известно, что добавляемые записи являются уникальными. Подробнее об этомпозже.)
В реализации цепочки хэшей неподтверждающая функция вставки может выглядеть следующим образом:
void insert(hashNode *node, int index) {
node->next = hashTable[index];
hashTable[index] = node;
}
Обратите внимание, что нет веских причин для использования двусвязного спискадля цепочки хэшей, даже если вы планируете реализовать удаление.Дополнительная ссылка - это просто трата памяти и циклов.
Тот факт, что вы можете построить сцепленную хэш-таблицу за (практически) время, вовсе не означает, что алгоритм построилхороший хэш-стол.Когда придет время искать значение в таблице, проблема будет обнаружена: среднее число проб, чтобы найти элемент, будет вдвое меньше, чем количество элементов в таблице.Хэш-таблица с открытым адресом Робин Гуда (или линейная) имеет одинаковую производительность, поскольку все поиски начинаются в начале таблицы.Тот факт, что хеш-таблица с открытыми адресами также создавалась медленно, вероятно, не имеет значения по сравнению со стоимостью использования таблицы.
Нам не нужна хеш-функция, настолько ужасная, как «всегда использовать 0»."Функция для получения квадратичной производительности.Достаточно, чтобы хеш-функция имела чрезвычайно маленький диапазон возможных значений (по сравнению с размером хеш-таблицы).Если возможные значения одинаково вероятны, цепочечный хеш будет по-прежнему квадратичным, но средняя длина цепочки будет разделена на количество возможных значений.Это не относится к линейному / R.Hood зондируемому хешу, особенно, если все возможные значения хеша сконцентрированы в небольшом диапазоне.Предположим, например, что хеш-функция равна
int hash(const char* key) {
unsigned char h = 0;
while (*key) h += *key++;
return h;
}
Здесь диапазон хеш-функции ограничен [0, 255).Если размер таблицы намного больше 256, это быстро приведет к той же ситуации, что и постоянная хеш-функция.Очень скоро первые 256 записей в хеш-таблице будут заполнены, и каждая вставка (или поиск) после этой точки потребует линейного поиска в линейно увеличивающемся компактном диапазоне в начале таблицы.Таким образом, производительность будет неотличима от производительности таблицы с постоянной хеш-функцией.
Ничто из этого не предназначено для мотивации использования связанных хеш-таблиц.Скорее, это указывает на важность использования хорошей хэш-функции.(Хороший в том смысле, что результат хеширования ключа равномерно распределен по всему диапазону возможных положений узла.) Тем не менее, обычно бывает, что умные схемы открытой адресации более чувствительны к плохим хеш-функциям, чем простое сцепление.
Схемы открытой адресации, безусловно, привлекательны, особенно в случае статических таблиц поиска.Они более привлекательны в случае статических таблиц поиска, потому что удаление действительно может быть проблемой, поэтому отсутствие необходимости в удалении ключа устраняет огромное осложнение.Наиболее распространенным решением для удаления является замена удаленного элемента на маркерный элемент DELETED.Пробники поиска по-прежнему должны пропускать маркеры DELETED, но если после поиска будет следовать вставка, первый маркер DELETED можно запомнить во время сканирования поиска и перезаписать вставленным узлом, если ключ не найден.Это работает приемлемо, но коэффициент загрузки должен быть рассчитан с ожидаемым количеством маркеров DELETED, и если шаблон использования иногда последовательно удаляет много элементов, реальный коэффициент загрузки для таблицы значительно снизится.
В случае, когда удаление не является проблемой, однако, хэш-таблицы с открытыми адресами имеют некоторые важные преимущества.В частности, они значительно снижают издержки в случае, когда полезная нагрузка (ключ и соответствующее значение, если оно есть) мала.В случае связанной хеш-таблицы каждый узел должен содержать указатель next, а индекс хеш-таблицы должен быть вектором указателей на цепочки узлов.Для хеш-таблицы, ключ которой занимает только пространство указателя, накладные расходы составляют 100%, что означает, что хеш-таблица с открытым адресом и линейным зондированием с коэффициентом загрузки 50% занимает немного меньше места, чем связная таблица, индекс которойвектор полностью занят и узлы которого выделяются по требованию.
Мало того, что линейная таблица зондирования более эффективна для хранения, она также обеспечивает гораздо лучшую эталонную локализацию, что означает, что кэши ОЗУ ЦП будут использоваться для гораздо большегопреимущество.При линейном зондировании может быть возможно выполнить восемь зондирований, используя одну кэш-линию (и, следовательно, только одну медленную ссылку на память), что может быть почти в восемь раз быстрее, чем зондирование через связанный список случайно распределенных записей таблицы.(На практике ускорение не будет таким экстремальным, но вполне может быть более чем вдвое быстрее.) Для строковых ключей в тех случаях, когда производительность действительно имеет значение, вы можете подумать о сохранении длины и / или первых нескольких символовключа в самой записи хеша, так что указатель на полную символьную строку в основном используется только один раз, чтобы проверить успешность проверки.
Но преимущества открытой и пространственной адресации зависят отХеш-таблица представляет собой массив записей , а не массив указателей на записи, как в вашей реализации.Размещение записей непосредственно в хеш-индексе позволяет избежать потенциально значительных накладных расходов указателя на запись (или, по крайней мере, на цепочку) и позволяет эффективно использовать кэш-память.Так что это то, о чем вы могли бы подумать в своей окончательной реализации.
Наконец, не обязательно тот случай, когда открытая адресация усложняет удаление.В хеше кукушки (и различных алгоритмах, которые он вдохновил в последние годы), удаление не сложнее, чем удаление в цепочечном хеше, и, возможно, даже проще.В хеше кукушки любой данный ключ может находиться только в одном из двух мест в таблице (или, в некоторых вариантах, в одном из k мест для некоторой небольшой константы k), и операция поиска должна только исследовать эти двамест.(Вставка может занять больше времени, но все равно ожидается, что O (1) для коэффициентов загрузки менее 50%.) Таким образом, вы можете удалить запись, просто удалив ее из того места, где она есть;это не окажет заметного влияния на скорость поиска / вставки, и слот будет прозрачно использован повторно без какого-либо дополнительного вмешательства.(С другой стороны, два возможных местоположения для узла не являются смежными, и они, вероятно, находятся на отдельных строках кэша. Но для данного поиска есть только два из них. Некоторые варианты имеют лучшую локальность ссылки.)
Несколько последних комментариев о вашей реализации Робин Гуда:
Я не совсем уверен, что коэффициент загрузки 99,5% является разумным.Может быть, все в порядке, но разница между 99% и 99,5% настолько мала, что нет никаких очевидных причин искушать судьбу.Кроме того, довольно медленная операция остатка во время вычисления хеш-функции может быть устранена, если сделать размер таблицы степенным, равным двум (в данном случае 1 048 576), и вычислить остаток с помощью битовой маски.Конечный результат вполне может быть заметно быстрее.
Кэширование числа зондов в хеш-записи работает (несмотря на мои предыдущие сомнения), но я все еще считаю, что предложенный подход кешированиявместо этого значение хеша выше.Вы можете легко рассчитать расстояние до зонда;это разница между текущим индексом в цикле поиска и индексом, вычисленным из кэшированного значения хеша (или самого кэшированного начального местоположения индекса, если это то, что вы решили кэшировать).Это вычисление не требует каких-либо изменений в записи хеш-таблицы, поэтому оно кешируется и работает немного быстрее и не требует больше места.(Но в любом случае, есть издержки хранения, которые также уменьшают удобство кэша.)
Наконец, как отмечалось в комментарии, у вас есть ошибка «один за другим» в вашем цикле обходакод;это должно быть
if(index >= NUM_WORDS) index = 0;
При строгом тесте «больше чем», как написано, ваша следующая итерация попытается использовать запись с индексом NUM_WORDS, которая выходит за пределы.