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