Я пытаюсь понять, как работают Hashtables в C#. Я прочитал статью в MSDN и понял, что хэш-таблицы C# используют "перехеширование" для коллизий, т.е. если я пытаюсь вставить пару ключ/значение в хэш-таблицу, то если использование HashFunction H1 приводит к коллизии, то она будет пробовать HashFunction H2, H3 и т.д., пока не будет найдено ни одной коллизии.
MSDN quote:
Класс Hashtable использует другую технику, называемую перехеширование. (В некоторых источниках перехеширование называют двойным хешированием.)
Перехеширование работает следующим образом: имеется набор различных хеш-функций, H1... функций, H1 ... Hn, и при вставке или извлечении элемента из хэш-таблицы, первоначально используется хэш-функция H1. Если это приводит к коллизии, вместо нее используется H2, и далее, если необходимо, до Hn. В предыдущем разделе была показана только одна хэш-функция, которая является начальная хэш-функция (H1). Другие хэш-функции очень похожи на эту функцию, только дифференцируются на мультипликативный коэффициент. В общем случае хэш-функция Hk определяется так:
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1))))] % hashsize
Однако, если взять пример с сайта MSDN1:
private static Hashtable employees = new Hashtable();
public static void Main()
{
// Add some values to the Hashtable, indexed by a string key
employees.Add("111-22-3333", "Scott");
employees.Add("222-33-4444", "Sam");
}
Предположим, что добавление второго ключа приведет к коллизии, поэтому придется использовать H2. Однако, когда я вызываю employees["222-33-4444"], как hashtable узнает, что нужно использовать H2? Существует ли отдельное отображение? Спасибо.