Я использую приложение, которое использует большое количество словарей (до 10 ^ 6 элементов), размер которых неизвестен заранее (хотя я могу догадаться в некоторых случаях). Мне интересно, как реализуется словарь, т.е. Насколько плох эффект, если я не дам начальную оценку размера словаря. Внутренне ли он использует (саморазрастающийся) массив в том, как работает List? и в этом случае, если словари будут расти, может оставить много больших массивов без ссылки на LOH.
Как реализован словарь С#/.NET 3.5?
Ответ 1
Используя Reflector, я нашел следующее: Словарь хранит данные в массиве struct. Он подсчитывает, сколько пустых мест осталось в этом массиве. Когда вы добавляете элемент и пустое место не остается, оно увеличивает размер внутреннего массива (см. Ниже) и копирует данные из старого массива в новый массив.
Итак, я бы предложил вам использовать конструктор, в котором вы устанавливаете начальный размер, если знаете, что будет много записей.
EDIT: логика на самом деле довольно интересная: для поиска простых чисел существует внутренний класс HashHelpers. Чтобы ускорить это, он также сохранил некоторые простые числа в статическом массиве от 3 до 7199369 (некоторые из них отсутствуют, по этой причине см. Ниже). Когда вы добавляете емкость, она находит следующий массив (то же значение или больше) из массива и использует его как начальную емкость. Если вы даете ему большее количество, чем в своем массиве, он начинает проверку вручную.
Итак, если ничего не передается как емкость для Словаря, стартовая емкость - три.
Как только мощность превышена, она умножает текущую емкость на два, а затем находит следующее большее простое значение с использованием класса-помощника. Вот почему в массиве не обязательно каждое простое, так как простые числа "слишком близко друг к другу" на самом деле не нужны.
Итак, если мы не получим начального значения, мы получим (я проверил внутренний массив):
- 3
- 7
- 17
- 37
- 71
- 163
- 353
- 761
- 1597
- 3371
- 7013
- 14591
- 30293
- 62851
- 130363
- 270371
- 560689
- 1162687
- 2411033
- 4999559
Как только мы передаем этот размер, следующий шаг выходит за пределы внутреннего массива, и он будет вручную искать большие простые числа. Это будет довольно медленно. Вы можете инициализировать с помощью 7199369 (наибольшее значение в массиве) или подумать, может ли иметь более 5 миллионов записей в словаре, что вы должны пересмотреть свой дизайн.
Ответ 2
MSDN говорит: "Извлечение значения с помощью его ключа очень быстро, близко к O (1), потому что класс Dictionary реализуется как хэш-таблица". и далее "емкость автоматически увеличивается, как требуется, перераспределяя внутренний массив".
Но вы получаете меньше перераспределений, если вы даете начальную оценку. Если у вас есть все элементы с самого начала, может оказаться полезным метод LINQ ToDictionary.
Ответ 3
У Hashtables обычно есть что-то, называемое коэффициентом загрузки, что увеличит хранилище резервных ковшов, если этот порог будет достигнут. IIRC по умолчанию - это что-то вроде 0.72. Если у вас отличное хеширование, это может быть увеличено до 1.0.
Также, когда хэш-таблице требуется больше ковшей, вся коллекция должна быть перефразирована.
Ответ 4
Лучший способ для меня - использовать .NET Reflector.
http://www.red-gate.com/products/reflector/
Используйте дизассемблированный код, чтобы увидеть реализацию.