Какова реализация и сложность операций коллекций C #?

Question

Я хочу кешировать 10.000+ пар ключ / значение (обе строки) и начал думать, какая структура .NET (2.0, связанная с MS Studio 2005 :() будет лучшей. Все элементы будут добавлены в один кадр, затембудет несколько сотен запросов для конкретных ключей.
Я прочитал описания MSDN, на которые есть ссылка в другой вопрос , но я все же пропускаю некоторые подробности о реализации / сложности операций в различных коллекциях. Например, вВышеупомянутый вопрос, есть цитата из MSDN, в которой говорится, что SortedList основан на дереве, а SortedDictionary «имеет похожую объектную модель», но отличается сложностью. Другой вопрос: реализованы ли HashTable и Dictionary одинаково?
Для HashTable они запись :

Если значение Count меньше емкости Hashtable, этот метод является операцией O (1). Если емкость необходимо увеличить для соответствияновый элемент, этот метод становится операцией O (n), где n это Count.

Но когда tон увеличен?С каждым "Добавить"?Тогда это будет квадратичная сложность добавления серии пар ключ / значение.Как и в случае с SortedList.

Не говоря уже об OrderedDictionary, где ничего не говорится о реализации / сложности.

Может быть, кто-то знает какую-нибудь хорошую статью о реализации коллекций .NET?

Answer 1

емкость HashTable отличается от Count.

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

Из-за экспоненциально увеличивающегося интервала (междуO(n), n = Count, изменение размера), большинство реализаций хэша требуют O(1) амортизированного доступа .Цитата просто говорит: «Эй! Это амортизировано и не всегда верно!».

Счастливое кодирование.

Answer 2

Словарь - это своего рода хеш-таблица; Я никогда не использую оригинальный Hashtable, так как он содержит только «объекты». Не беспокойтесь о том, что при увеличении емкости вставка равна O (N); Словарь всегда удваивает емкость, когда хеш-таблица заполнена, поэтому сложность средняя (амортизированная) равна O (1).

Вы почти никогда не должны использовать SortedList (который в основном является массивом), поскольку сложность составляет O (N) для каждой вставки или удаления (при условии, что данные еще не отсортированы. Если данные отсортированы, то вы получите O (1) , но если данные уже отсортированы, вам все равно не нужно использовать SortedList, потому что достаточно обычного List.) Вместо SortedList используйте SortedDictionary , который предлагает O (N log N) для вставки, удалить и искать. Однако SortedDictionary медленнее, чем Dictionary, поэтому используйте его, только если ваши данные должны быть отсортированы.

Вы говорите, что хотите кэшировать 10 000 пар ключ-значение. Если вы хотите выполнить все вставки до выполнения каких-либо запросов, эффективный метод - создать несортированный список, затем Сортировать его и использовать BinarySearch для запросов. Этот подход экономит много памяти по сравнению с использованием SortedDictionary и создает меньше работы для сборщика мусора.

Answer 3

HashTable и Dictionary реализованы одинаково. Dictionary - это общая замена для HashTable.

Когда емкость коллекций, таких как List и Dictionary, должна увеличиться, она будет расти с определенной скоростью. Для List скорость равна 2.0, то есть емкость удваивается. Я не знаю точную ставку для Dictionary, но она работает так же.

Для List увеличение емкости означает, что предмет скопирован в среднем в 1,3 раза больше. Поскольку это значение остается постоянным при увеличении списка, метод Add в среднем по-прежнему является операцией O (1).

Answer 4

Если вы добавляете столько пар, вы можете / должны использовать этот конструктор словаря , чтобы заранее указать емкость. Тогда каждое добавление и поиск будут O (1).

Если вы действительно хотите увидеть, как реализованы эти классы, вы можете посмотреть источник Rotor или использовать .NET Reflector , чтобы посмотреть System.Collections (не уверен в законность последнего).