C # - с какого размера коллекции я должен начать использовать словарь - PullRequest
Новая
       15

C # - с какого размера коллекции я должен начать использовать словарь

0 голосов
/ 07 марта 2019

Я был удивлен, что не смог найти ответ на этот вопрос. Итак, я знаю, что Словарь выполняет поиск в O (1) асимптотически, но с хэшированием. Есть ли эмпирическое правило для размера коллекции, при котором список предпочтительнее словаря? Десятки предметов? сотни? Тысячи?

1 Ответ

0 голосов
/ 07 марта 2019

По моему опыту, переломный момент составляет от 10 до 50 пунктов, в зависимости от схемы использования и сложности вашей хэш-функции. Но вы должны сделать бенчмарк для ваших данных, особенно если ваша пользовательская хеш-функция может занять некоторое время для вычисления кэша.

Вы также можете использовать HybridDictionary, который является внутренним списком для небольшого количества записей и хэш-таблицей после этого. .Net framework source показывает точку переключения на 9 элементов. 

    public class HybridDictionary: IDictionary {

    // These numbers have been carefully tested to be optimal. Please don't change them
    // without doing thorough performance testing.
    private const int CutoverPoint = 9;
    private const int InitialHashtableSize = 13;
    private const int FixedSizeCutoverPoint = 6;

Обновление : как отметил @Hans Passant в комментарии выше, гибридный словарь не имеет универсальной версии, которая может повлиять на производительность при упаковке / распаковке и общем использовании. Итак, вы должны быть осторожны и делать тесты для вашей ситуации. Моя цель состояла в том, чтобы показать, что что-то около ~ 10 пунктов может быть точкой, чтобы начать использовать словарь против списка.

...