Hashtable collision rehashing - как читаются значения?

Я пытаюсь понять, как работают 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? Существует ли отдельное отображение? Спасибо.

9
задан BrokenGlass 6 February 2012 в 10:01
поделиться