Hashtable- Перемывание

Question

Мне сказали, что Hashtable в .NET использует перефразирование, чтобы уменьшить / избежать столкновения.

То есть. "Реазинг работает следующим образом: предположим, что у нас есть набор различных хеш-функций, H1... Hn, и при вставке или извлечении элемента из хеш-таблицы изначально используется хеш-функция H1. Если это приводит к столкновению, вместо этого пробуют H2 и далее до Hn, чтобы избежать столкновения в Hashtable ".

Предположение: у нас есть хеш-таблица с n (где n 1).

Вопрос: Может ли кто-нибудь объяснить мне, как CLR сопоставляет Key с хеш-кодом, когда мы ищем (извлекаем) какой-либо элемент (если используются разные хеш-функции)? Как CLR отслеживает (если это) хеш-функцию любого живого объекта (хеш-таблицы)?

заранее спасибо

Answer 1

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

РЕДАКТИРОВАТЬ: Подробнее

Вернувшись домой, открыл книгу "Введение в алгоритмы" Т. Кормена и обнаружил следующее в разделе 11.3.3 "Универсальное хеширование":

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

Вы можете прочитать больше, предварительно просмотрев книгу на сайте Google Книг здесь