Hashtable- Rehashing

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

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

Предположение: У нас есть хэш-таблица с n (где n < бесконечности) элементами, асимптотическая временная сложность которой o(1); мы (CLR) достигли этого, применяя некоторую хэш-функцию (хэш-функция Hn-1, где n>1).

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

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

8
задан sll 28 September 2011 в 18:20
поделиться