Как реализован словарь c # /. Net 3.5?
Я использую приложение, которое использует несколько больших словарей (до 10 ^ 6 элементов), размер которых заранее неизвестен (хотя я могу догадаться в некоторых случаях ). Мне интересно, как реализован словарь, то есть, насколько плох, если я не даю первоначальную оценку размера словаря. Использует ли он внутренне (саморазвивающийся) массив так, как это делает List? в этом случае расширение словарей может привести к появлению большого количества массивов без ссылок на LOH.
4 ответа
Используя 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
Once мы проходим этот размер, следующий шаг выходит за пределы внутреннего массива, и он будет вручную искать более крупные простые числа. Это будет довольно медленно. Вы можете инициализировать с 7199369 (самое большое значение в массиве), или подумать, не означает ли наличие более 5 миллионов записей в словаре, что вам следует пересмотреть свой дизайн.
Лучшим способом для меня было бы использовать .NET Reflector.
http://www.red-gate.com/products/reflector/
Используйте дизассемблированный код, чтобы увидеть реализацию.
MSDN говорит: "Извлечение значения по ключу происходит очень быстро, почти O(1), потому что класс Dictionary реализован как хэш-таблица." и далее "емкость автоматически увеличивается по мере необходимости путем перераспределения внутреннего массива."
Но вы получите меньше перераспределений, если дадите начальную оценку. Если у вас есть все элементы с самого начала, может пригодиться метод LINQ ToDictionary.
У хэш-таблиц обычно есть нечто, называемое коэффициентом загрузки, который увеличивает резервное хранилище ведра при достижении этого порога. IIRC по умолчанию это что-то вроде 0.72. Если у вас идеальное хэширование, это значение может быть увеличено до 1.0.
Также, когда хэш-таблице требуется больше ведер, вся коллекция должна быть перехеширована.