Функция FindEntry в Dictionary.cs

Я смотрел на реализацию словаря в .NET, так как я хотел понять, что делает словарь ContainsKey и поиск быстрым:http://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,15debc34d286fdb3

Функция ContainsKey в основном приводит к перечислению FindEntry, указанному ниже:

buckets - это массив целых чисел, а записи - это массив объектов Entry, которые представляют собой структуры, содержащие HashCode, TKey и TValue.

Итак, я понимаю, что этот поиск быстрый, так как это простой поиск по массиву.

private int FindEntry(TKey key) {
        if( key == null) {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }
   if (buckets != null) {
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
            }
        }
        return -1;
    }

Однако я пытаюсь понять эти 2 строки:

int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)

1) Если я правильно понял 0x7FFFFFFF, это гарантирует, что мы не получим отрицательное значение. Так что же возвращает первая строка? Это простое число или простое число?

2) Во второй строке, почему мы инициализируем i в buckets [hashCode% buckets.Length]?

 Patrick Hofman07 июл. 2016 г., 12:01
Итак, я понимаю, что этот поиск быстрый, так как это простой поиск по массиву. Нет, ходит по дереву.

Ответы на вопрос(1)

Решение Вопроса

чтобы сделать число положительным. Это не обязательно простое число. Это полностью допустимо, чтобы удалить данные из любого хэша. Хеш0 (постоянный ноль) всегда является допустимым хешем. Вот почему эта операция безопасна.

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

В .NETDictionary Класс каждого блока логически является началом связанного списка.int[] buckets содержит индекс дляentries для начала связанного списка, хранящегося внутриentries.

Это сложно по причинам производительности. Логически,buckets может бытьnew LinkedList<Entry>[capacity], Это сделало бы то же самое, но с гораздо большим количеством ассигнований.

В Интернете есть статьи оDictionary Внутренности. Я нахожу алгоритм довольно хорошим и умным. Не нужен коэффициент загрузки. Таблица может быть загружена полностью.

 Iason07 июл. 2016 г., 12:31
«В классе .NET Dictionary каждый сегмент логически является началом связанного списка. Int [] buckets содержит индекс для записей для начала связанного списка, хранящегося внутри записей». Я думаю, что понял. Вы говорите, что это связанный список из-за .next в каждом объекте Entry, который указывает на следующий объект Entry. Это правильно?
 usr07 июл. 2016 г., 12:36
Правильный. Вы можете найтиfreeList интересно. Это связанный список, связывающий все удаленные записи вместе. Это довольно умный дизайн. Я не понимаю, почему хэш-таблицы построены как-то иначе.

Ваш ответ на вопрос