Перефразирование хэш-таблицы столкновений - как считываются значения?

Question

Я пытаюсь понять, как работают Hashtables в C #.Я прочитал статью MSDN и понял, что C # Hashtables использует 'rehashing' для коллизий, т.е. если я пытаюсь вставить пару ключ / значение в хеш-таблицу, если использование HashFunction H1 приводит к коллизии, то он попытается использовать HashFunction H2, H3и т. д. до тех пор, пока не будут обнаружены коллизии.

MSDN цитата:

В классе Hashtable используется другой метод, называемый повторным отображением.(Некоторые источники называют перефразирование как двойное хеширование.)

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

Hk (ключ) = [GetHash (ключ) + k * (1 + (((GetHash (ключ) >> 5) + 1)% (размер хеша)- 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 придется использовать.Однако когда я звоню сотрудникам ["222-33-4444"], как хеш-таблица знает, как использовать H2?Есть ли отдельное сопоставление?Благодаря.

Answer 1

Я думаю, вы неправильно поняли перефразировку. Есть только одна хеш-функция: виртуальная object.GetHashCode() (или, если вы предоставляете IHashCodeProvider или IEqualityComparer, он использует этот объект для вычисления хеш-кода). Когда хэш-таблица заполнена, она расширяет свои возможности и перераспределяет элементы по новым, более крупным массивам. Закрытый метод, который делает это, называется Rehash(), но он не пересчитывает хеш-коды.

CORRECTION

Перефразировка не использует новую функцию, а работает с предыдущим значением хеш-кода; это приводит к поиску в последующих слотах до тех пор, пока не будет найден пустой (для вставки / установки) или пока все ключи с одинаковым (начальным) хэш-кодом не будут проверены на равенство с индексным ключом (для извлечения).

EDIT

Чтобы ответить на ваш вопрос напрямую:

Предположим, что добавление второго ключа приведет к коллизии, поэтому придется использовать H2. Однако, когда я звоню сотрудникам ["222-33-4444"], как хеш-таблица знает, как использовать H2? Есть ли отдельное сопоставление? Спасибо.

1. Рассчитать правильный сегмент на основе хеш-кода переданного ключа.
2. Если эта корзина пуста, произойдет сбой.
3. Если ключ корзины соответствует переданному ключу, вернуть значение корзины.
4. Если счетчик коллизий хэшей равен нулю, произойдет сбой.
5. Рассчитать следующий хеш-код из текущего хеш-кода.
6. Рассчитать правильный сегмент на основе нового хэш-кода.
7. Перейти к шагу 2.

Answer 2

Хеш-таблицы хранят ключ и значение в самой хеш-таблице.Таким образом, позже во время таких операций, как поиск в хеш-таблице, можно гарантировать, что найденное значение соответствует индексу, используемому для поиска.Хеш-таблицы используют простую методологию «попробуй основной метод поиска до успеха».В этом случае методом поиска является «использовать хэш-функцию X», где X изменяется при сбое.

В других схемах методом поиска является «просмотр записи таблицы X» (какопределяется хэш-функцией) где X просто увеличивается на единицу при каждом сбое.

Теперь возникает вопрос: что происходит, когда значение ISN'T в таблице?Что ж, это может быть довольно уродливо: когда вы либо нажали на запись в таблице, которая отсутствует, или, что еще хуже, когда вы перебрали столько записей, сколько хранится в таблице, вы можете быть уверены, что запись ненет, но в худшем случае это может занять некоторое время.

Имейте в виду, что, поскольку с одним ключом может быть связано только одно значение, после того, как вы нашли ключ, вынашел значение.Худшее, что может сделать хеш-таблица, - это выполнить эквивалент недешевного кэширования линейного поиска по всем значениям в самой хеш-таблице ... но, в конечном счете, оно найдет значение, если оно там, потому что оно сравнивает хранимый ключ сзапрошенный ключ, чтобы проверить, есть ли он там.Единственная оптимизация, которую делают закрытые хеш-таблицы, - это где искать сначала - в этом случае, где хеш-функция говорит 1, а затем 2, а затем 3 ...

Answer 3

Сначала он попробует H1.Если он не находит соответствия, он будет использовать H2.И так далее.