ключи цепочки хеш-таблиц с универсальным хэшированием, нужна ли перефразировка?
Я реализую хеш-таблицу с использованием вектора < списки>. Я изменил свой вектор до простого числа, скажем, 5. Чтобы выбрать ключ, который я использую универсальный хэзинг.
У меня вопрос, нужно ли перефразировать мой вектор? Я имею в виду, что этот код будет всегда генерировать ключ в диапазоне от 0 до 5, потому что он зависит от размера моей хеш-таблицы, что, конечно, вызывает коллизии, но все новые строки будут добавляться в списки каждой позиции в векторе … так что, похоже, мне не нужно менять размер / перефразировать все это. Как вы думаете? Это ошибка?
Решение
Да, вы делаете. В противном случае объекты будут в неправильном хэш-контейнере, и когда вы будете искать их, вы не найдете их. Весь смысл хеширования состоит в том, чтобы сделать поиск объекта быстрее — это не сработает, если объекты находятся не там, где они должны быть.
Кстати, вы, вероятно, не должны этого делать. Есть люди, которые потратили годы на разработку эффективных алгоритмов хеширования. Попытка свернуть свою собственную приведет к снижению производительности. Начните со статьи на линейное хеширование в википедии.
Другие решения
мне нужно перефразировать мой вектор?
Ваш контейнер может продолжать функционировать без перефразирования, но поиск, вставка и удаление будут работать все больше и больше, как обычный list вместо хеш-таблицы: например, если вы вставили 10000 элементов, вы можете ожидать каждый list в вашем vector иметь примерно 2000 элементов, и вам, возможно, придется поискать все 2000, чтобы увидеть, является ли значение, которое вы хотите вставить, дубликатом, или найти значение для eraseили просто вернуть iterator к. Конечно, 2000 лучше, чем 10 000, но это далеко от производительности O (1), ожидаемой от качественной реализации хеш-таблицы. Ваша реализация без изменения размера все еще «O (N)».
Это ошибка?
Да, фундаментальный.