Продолжим наш путь по написанию собственной хеш-таблицы с нуля, мы будем совершенствовать и оптимизировать нашу реализацию с алгоритмической точки зрения.
Одним из возможных обновлений реализации является возможность повторного использования удаленных записей. В настоящее время удаленные являются по существу мертвыми записями, которые просто тратят пространство массива. Единственным способом их полного удаления является вызов метода `resize()`, который создает экземпляр новой хэш-таблицы. Более эффективное использование удаленных записей заключается в их переработке, если это возможно.
Это улучшение является простым. Необходимо изменить метод `insert()` так, чтобы при обнаружении удалённых записей во время проверки мы сохраняли его на случай, если мы сможем его переработать. Если нам не удалось найти запись, соответствующую данному ключу, то мы вставляем пару ключ-значение в эту сохраненную запись, а не новую запись. Я оставлю фактическую реализацию как упражнение. С этим изменением я смог увидеть около 4% улучшения во время выполнения с синтетическим тестом.
Мы можем применить гораздо лучший патч, который может принести нам больший прирост производительности. Этот алгоритм не только умный, но и напомнил мне, почему алгоритмы важны в программном обеспечении.
Хэширование Робингуд - это метод разрешения коллизий в хэш-таблицах с открытой адресацией. Одним из ключевых понятий является длина проверки последовательности, или PSL. Это расстояние между исходным местоположением (домашним слотом), указанным значением хэша, и фактическим расположением элемента. При отсутствии хеш-коллизии каждый элемент будет иметь 0 PSL. По мере того, как все больше и больше элементов сталкиваются, эти элементы будут размещаться дальше от идеального места.
Основная идея метода хеширования Робингуд заключается в уменьшении дисперсии PSL, поскольку время просмотра элемента пропорционально PSL. Это достигается путем сортировки элементов в соответствии с расположением их исходной локации.
С помощью этого свойства мы можем раньше остановить наши проверки, когда сталкиваемся с позицией, которая принадлежит другому домашнему слоту. На диаграмме выше, если наш домашний слот совпадает с 7, 23, 4, мы раньше завершаем проверку записи, которая содержит 6, потому что она принадлежит другому домашнему слоту. Как определить, где находится главный слот для каждой позиции? Ну, мы можем просто сохранить значение PSL вместе с ключом и значением для каждой записи. Компромисс заключается в том, что мы увеличим потребление памяти.
Основное обновление относится к методу `insert_helper()`. Чтобы убедиться, что элементы отсортированы по их домашним слотам, мы по существу проводим пузырьковую сортировку - обмениваем смежные элементы, если это необходимо, по мере проверки. Я никогда не думал, что пузырьковая сортировка будет иметь какое-то практическое применение, но здесь это великолепный алгоритм!
Еще одно преимущество хеширования Робингуд заключается в том, что мы можем устранить мертвые записи. То есть наши записи либо свободны, либо заняты. Для этого необходимо изменить метод remove() - при обнаружении записи с соответствующим ключом пометить ее как свободную. Мы продолжаем пробовать и сдвигать вниз следующие ключи на один слот назад, чтобы заполнить пробелы. Однако мы можем остановиться раньше, когда столкнемся с элементом, который имеет 0 PSL, что означает, что элемент уже находится в своем идеальном месте.
Патч - большой, поэтому вместо того, чтобы перечислять все различия здесь, я просто поделюсь полным кодом здесь. Я рекомендую вам попробовать реализовать его самостоятельно, чтобы действительно понять технику. А вот эталонный результат с нашей техникой хеширования Робингуд:
Время выполнения сократилось с 0,51 с до 0,41 с по сравнению с нашей предыдущей реализацией, что на 20% меньше, что делает нашу реализацию на шаг ближе к стандартной библиотеке. Неплохо для примерно 200 строк кода. С этим многообещающим результатом наша следующая задача - превзойти стандартную реализацию на этом эталоне. Оставайтесь в курсе, будет следующая статья!
Статья на rusty-code.ru
