Производительность HashSet и List

407

Понятно, что эффективность поиска универсального HashSet<T>класса выше, чем универсального List<T>класса. Просто сравните ключ на основе хеша с линейным подходом в List<T>классе.

Однако вычисление ключа хеша само по себе может занять несколько циклов ЦП, поэтому для небольшого количества элементов линейный поиск может стать реальной альтернативой HashSet<T>.

Мой вопрос: где безубыточность?

Чтобы упростить сценарий (и быть справедливым), давайте предположим, что List<T>класс использует метод элемента Equals()для идентификации элемента.

Михаил Даматов
источник
7
Если вы действительно хотите минимизировать время поиска, также рассмотрите массивы и отсортированные массивы. Чтобы правильно ответить на этот вопрос, необходим тест, но вы должны рассказать нам больше о T. Кроме того, на производительность HashSet может повлиять время выполнения T.GetHashCode ().
Eldritch Conundrum

Ответы:

822

Многие люди говорят, что, как только вы доберетесь до размера, где скорость на самом деле является проблемой, HashSet<T>которая всегда побеждает List<T>, но это зависит от того, что вы делаете.

Предположим, у вас есть List<T>только 5 предметов. В течение большого количества циклов, если один элемент добавляется или удаляется в каждом цикле, вам лучше использовать a List<T>.

Я проверил это на своей машине, и, чтобы получить преимущество, он должен быть очень маленьким List<T>. Для списка коротких строк преимущество ушло после размера 5, для объектов после размера 20.

1 item LIST strs time: 617ms
1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms
2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms
3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms
4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms
5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms
6 item HASHSET strs time: 1418ms

7 item LIST strs time: 1581ms
7 item HASHSET strs time: 1464ms

8 item LIST strs time: 1726ms
8 item HASHSET strs time: 1398ms

9 item LIST strs time: 1901ms
9 item HASHSET strs time: 1433ms

1 item LIST objs time: 614ms
1 item HASHSET objs time: 1993ms

4 item LIST objs time: 837ms
4 item HASHSET objs time: 1914ms

7 item LIST objs time: 1070ms
7 item HASHSET objs time: 1900ms

10 item LIST objs time: 1267ms
10 item HASHSET objs time: 1904ms

13 item LIST objs time: 1494ms
13 item HASHSET objs time: 1893ms

16 item LIST objs time: 1695ms
16 item HASHSET objs time: 1879ms

19 item LIST objs time: 1902ms
19 item HASHSET objs time: 1950ms

22 item LIST objs time: 2136ms
22 item HASHSET objs time: 1893ms

25 item LIST objs time: 2357ms
25 item HASHSET objs time: 1826ms

28 item LIST objs time: 2555ms
28 item HASHSET objs time: 1865ms

31 item LIST objs time: 2755ms
31 item HASHSET objs time: 1963ms

34 item LIST objs time: 3025ms
34 item HASHSET objs time: 1874ms

37 item LIST objs time: 3195ms
37 item HASHSET objs time: 1958ms

40 item LIST objs time: 3401ms
40 item HASHSET objs time: 1855ms

43 item LIST objs time: 3618ms
43 item HASHSET objs time: 1869ms

46 item LIST objs time: 3883ms
46 item HASHSET objs time: 2046ms

49 item LIST objs time: 4218ms
49 item HASHSET objs time: 1873ms

Вот эти данные отображаются в виде графика:

введите описание изображения здесь

Вот код:

static void Main(string[] args)
{
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();
}
innominate227
источник
8
Спасибо огромное! Это отличное объяснение, я искал что-то, что можно было бы добавить и удалить быстрее, чем List<T>для игрового движка, и, поскольку у меня обычно будет большой объем объектов, этот вид коллекции будет идеальным.
Redcodefinal
17
На самом деле в .NET Framework есть коллекция, которая переключается между списком и хастабильной реализацией в зависимости от количества содержащихся в нем элементов: HybridDictionary .
MgSam
8
MS, похоже, отказалась от этой мысли, поскольку у нее есть только неуниверсальная версия.
MgSam
47
Как бы ни был полон этот ответ, он не может ответить на первоначальный вопрос, касающийся производительности поиска по списку и по хэш-сетям. Вы проверяете, насколько быстро вы можете вставлять и удалять из них, что занимает значительно больше времени и отличается от других характеристик производительности, чем поиск. Попробуйте еще раз, используя .Contains, и ваш график существенно изменится.
Роберт Макки
5
@hypehuman ЦП не может работать непосредственно с данными в системной памяти, но извлекает данные из памяти в кэш для работы. Между запросом на перемещение памяти и фактическим поступлением памяти существует значительная задержка, поэтому ЦП часто запрашивает больший кусок непрерывной памяти для одновременного перемещения. Идея заключается в том, что память, необходимая для следующей инструкции, вероятно, очень близка к памяти, используемой предыдущей инструкцией, и, следовательно, часто уже находится в кеше. Когда ваши данные разбросаны по всей памяти, вероятность стать счастливчиком уменьшается.
Рой Т.
70

Вы смотрите на это неправильно. Да, линейный поиск по списку превзойдет HashSet для небольшого количества элементов. Но разница в производительности обычно не имеет значения для небольших коллекций. Как правило, о больших коллекциях вы должны беспокоиться, и именно здесь вы думаете о Big-O . Однако, если вы измерили реальное узкое место в производительности HashSet, вы можете попытаться создать гибридный List / HashSet, но вы сделаете это, проведя множество эмпирических тестов производительности - не задавая вопросов по SO.

Eloff
источник
5
большие коллекции, о которых вам нужно беспокоиться . Мы можем переопределить этот вопрос с точки зрения when small collection becomes large enough to worry about HashSet vs List?десятков, десятков тысяч, миллиардов элементов?
om-nom-nom
8
Нет, вы увидите значительную разницу в производительности выше нескольких сотен элементов. Суть всегда в том, чтобы использовать HashSet, если вы выполняете те типы доступа, в которых хорошо работает HashSet (например, есть ли элемент X в наборе). Если ваша коллекция настолько мала, что List быстрее, тогда эти поиски очень редки. на самом деле являются узким местом в вашем приложении. Если вы можете измерить его как единое целое, хорошо, вы можете попытаться оптимизировать его, но в противном случае вы напрасно тратите свое время.
Элофф
15
Что делать, если у вас есть небольшая коллекция, которая много раз попадает в цикл? Это не редкий сценарий.
Дан-г-н
3
@ om-nom-nom - я думаю, дело в том, что не имеет значения, где находится переломный момент, потому что: «Если производительность вызывает беспокойство, используйте HashSet<T>. В случаях с небольшим числом, где List<T>может быть быстрее, разница незначительна «.
Скотт Смит
66

По сути, бессмысленно сравнивать две структуры по производительности, которые ведут себя по-разному. Используйте структуру, которая передает намерение. Даже если вы скажете, что у вас List<T>не будет дубликатов, и порядок итераций не имеет значения, делая его сравнимым с a HashSet<T>, его все равно плохой выбор, List<T>поскольку он относительно менее отказоустойчив.

Тем не менее, я буду проверять некоторые другие аспекты производительности,

+------------+--------+-------------+-----------+----------+----------+-----------+
| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |
|            | access |             |           |          |          |           |
+------------+--------+-------------+-----------+----------+----------+-----------+
| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |
| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |
+------------+--------+-------------+-----------+----------+----------+-----------+
  • Несмотря на то, что сложение равно O (1) в обоих случаях, оно будет относительно медленным в HashSet, поскольку требует затрат на предварительную обработку хеш-кода перед его сохранением.

  • Превосходная масштабируемость HashSet имеет стоимость памяти. Каждая запись хранится как новый объект вместе со своим хеш-кодом. Эта статья может дать вам представление.

Навфал
источник
11
Мой вопрос (шесть лет назад) был не о теоретической работе.
Михаил Даматов
1
HashSet разрешает произвольный доступ с ElementAt (), и я думаю, что это будет O (n) времени. Также, возможно, вы могли бы указать в своей таблице, допускает ли каждая коллекция дубликаты (например, списки разрешают, а хэш-наборы - нет)
Дан W
1
@DanW в таблице я сравниваю чисто рабочие характеристики, а не поведенческие характеристики. Спасибо за подсказку ElementAt.
Nawfal
1
ElementAt - это просто расширение LINQ. Оно не делает ничего, что вы не можете сделать, и лучше оптимизируется другим способом, который вы добавляете сами. Я думаю, что таблица имела больше смысла без учета ElementAt, поскольку все другие методы явно существуют в этих классах.
Динердо
1
Спасибо за эту таблицу, в моем случае использования мне нужно добавлять и удалять цели в заполненной коллекции каждый раз, когда они включены / отключены, и это помогло мне сделать правильный выбор (HashSet).
Кейси Хофланд
50

Использовать ли HashSet <> или List <> зависит от того, как вам нужен доступ к вашей коллекции . Если вам нужно гарантировать порядок товаров, используйте Список. Если вы этого не сделаете, используйте HashSet. Позвольте Microsoft беспокоиться о реализации своих алгоритмов хеширования и объектов.

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

ядро
источник
List потенциально может вычислять смещение для конкретного элемента по его индексу (поскольку все элементы имеют одинаковый тип и потенциально занимают один и тот же объем памяти). Так что в List нет необходимости перечислять его элементы
Lu55
@ Lu55 - Вопрос о поиске предмета в коллекции. Типичным сценарием является то, что коллекция является динамической - элементы могут быть добавлены или удалены с момента последнего поиска данного элемента - поэтому индекс не имеет смысла (поскольку он будет изменен). Если у вас есть статическая коллекция (которая не изменится, пока вы выполняете свои вычисления), или элементы никогда не удаляются и всегда добавляются в конце, тогда Listпредпочтительным является a , поскольку вы можете запомнить индекс - это ситуация, в которой вы описываю.
ToolmakerSteve
Вы можете использовать SortedSet, если вам нужно отсортировать HashSet. Все еще намного быстрее чем Список.
live-love
25

Просто подумал, что я бы включил некоторые тесты для различных сценариев, чтобы проиллюстрировать предыдущие ответы:

  1. Несколько (12 - 20) маленьких строк (длиной от 5 до 10 символов)
  2. Много (~ 10К) маленьких строк
  3. Несколько длинных строк (длиной от 200 до 1000 символов)
  4. Много (~ 5К) длинных строк
  5. Несколько целых чисел
  6. Много (~ 10К) целых чисел

И для каждого сценария ищем значения, которые появляются:

  1. В начале списка («начало», индекс 0)
  2. В начале списка («рано», индекс 1)
  3. Посередине списка («середина», индекс количества / 2)
  4. Ближе к концу списка («поздно», индекс-2)
  5. В конце списка («end», index count-1)

Перед каждым сценарием я генерировал случайные по размеру списки случайных строк, а затем передавал каждый список в хэш-набор. Каждый сценарий выполнялся 10000 раз, по сути:

(тестовый псевдокод)

stopwatch.start
for X times
    exists = list.Contains(lookup);
stopwatch.stop

stopwatch.start
for X times
    exists = hashset.Contains(lookup);
stopwatch.stop

Пример вывода

Проверено на Windows 7, 12 ГБ оперативной памяти, 64-разрядных, Xeon 2,8 ГГц

---------- Testing few small strings ------------
Sample items: (16 total)
vgnwaloqf diwfpxbv tdcdc grfch icsjwk
...

Benchmarks:
1: hashset: late -- 100.00 % -- [Elapsed: 0.0018398 sec]
2: hashset: middle -- 104.19 % -- [Elapsed: 0.0019169 sec]
3: hashset: end -- 108.21 % -- [Elapsed: 0.0019908 sec]
4: list: early -- 144.62 % -- [Elapsed: 0.0026607 sec]
5: hashset: start -- 174.32 % -- [Elapsed: 0.0032071 sec]
6: list: middle -- 187.72 % -- [Elapsed: 0.0034536 sec]
7: list: late -- 192.66 % -- [Elapsed: 0.0035446 sec]
8: list: end -- 215.42 % -- [Elapsed: 0.0039633 sec]
9: hashset: early -- 217.95 % -- [Elapsed: 0.0040098 sec]
10: list: start -- 576.55 % -- [Elapsed: 0.0106073 sec]


---------- Testing many small strings ------------
Sample items: (10346 total)
dmnowa yshtrxorj vthjk okrxegip vwpoltck
...

Benchmarks:
1: hashset: end -- 100.00 % -- [Elapsed: 0.0017443 sec]
2: hashset: late -- 102.91 % -- [Elapsed: 0.0017951 sec]
3: hashset: middle -- 106.23 % -- [Elapsed: 0.0018529 sec]
4: list: early -- 107.49 % -- [Elapsed: 0.0018749 sec]
5: list: start -- 126.23 % -- [Elapsed: 0.0022018 sec]
6: hashset: early -- 134.11 % -- [Elapsed: 0.0023393 sec]
7: hashset: start -- 372.09 % -- [Elapsed: 0.0064903 sec]
8: list: middle -- 48,593.79 % -- [Elapsed: 0.8476214 sec]
9: list: end -- 99,020.73 % -- [Elapsed: 1.7272186 sec]
10: list: late -- 99,089.36 % -- [Elapsed: 1.7284155 sec]


---------- Testing few long strings ------------
Sample items: (19 total)
hidfymjyjtffcjmlcaoivbylakmqgoiowbgxpyhnrreodxyleehkhsofjqenyrrtlphbcnvdrbqdvji...
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0018266 sec]
2: list: start -- 115.76 % -- [Elapsed: 0.0021144 sec]
3: list: middle -- 143.44 % -- [Elapsed: 0.0026201 sec]
4: list: late -- 190.05 % -- [Elapsed: 0.0034715 sec]
5: list: end -- 193.78 % -- [Elapsed: 0.0035395 sec]
6: hashset: early -- 215.00 % -- [Elapsed: 0.0039271 sec]
7: hashset: end -- 248.47 % -- [Elapsed: 0.0045386 sec]
8: hashset: start -- 298.04 % -- [Elapsed: 0.005444 sec]
9: hashset: middle -- 325.63 % -- [Elapsed: 0.005948 sec]
10: hashset: late -- 431.62 % -- [Elapsed: 0.0078839 sec]


---------- Testing many long strings ------------
Sample items: (5000 total)
yrpjccgxjbketcpmnvyqvghhlnjblhgimybdygumtijtrwaromwrajlsjhxoselbucqualmhbmwnvnpnm
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: list: start -- 132.73 % -- [Elapsed: 0.0021517 sec]
3: hashset: start -- 231.26 % -- [Elapsed: 0.003749 sec]
4: hashset: end -- 368.74 % -- [Elapsed: 0.0059776 sec]
5: hashset: middle -- 385.50 % -- [Elapsed: 0.0062493 sec]
6: hashset: late -- 406.23 % -- [Elapsed: 0.0065854 sec]
7: hashset: early -- 421.34 % -- [Elapsed: 0.0068304 sec]
8: list: middle -- 18,619.12 % -- [Elapsed: 0.3018345 sec]
9: list: end -- 40,942.82 % -- [Elapsed: 0.663724 sec]
10: list: late -- 41,188.19 % -- [Elapsed: 0.6677017 sec]


---------- Testing few ints ------------
Sample items: (16 total)
7266092 60668895 159021363 216428460 28007724
...

Benchmarks:
1: hashset: early -- 100.00 % -- [Elapsed: 0.0016211 sec]
2: hashset: end -- 100.45 % -- [Elapsed: 0.0016284 sec]
3: list: early -- 101.83 % -- [Elapsed: 0.0016507 sec]
4: hashset: late -- 108.95 % -- [Elapsed: 0.0017662 sec]
5: hashset: middle -- 112.29 % -- [Elapsed: 0.0018204 sec]
6: hashset: start -- 120.33 % -- [Elapsed: 0.0019506 sec]
7: list: late -- 134.45 % -- [Elapsed: 0.0021795 sec]
8: list: start -- 136.43 % -- [Elapsed: 0.0022117 sec]
9: list: end -- 169.77 % -- [Elapsed: 0.0027522 sec]
10: list: middle -- 237.94 % -- [Elapsed: 0.0038573 sec]


---------- Testing many ints ------------
Sample items: (10357 total)
370826556 569127161 101235820 792075135 270823009
...

Benchmarks:
1: list: early -- 100.00 % -- [Elapsed: 0.0015132 sec]
2: hashset: end -- 101.79 % -- [Elapsed: 0.0015403 sec]
3: hashset: early -- 102.08 % -- [Elapsed: 0.0015446 sec]
4: hashset: middle -- 103.21 % -- [Elapsed: 0.0015618 sec]
5: hashset: late -- 104.26 % -- [Elapsed: 0.0015776 sec]
6: list: start -- 126.78 % -- [Elapsed: 0.0019184 sec]
7: hashset: start -- 130.91 % -- [Elapsed: 0.0019809 sec]
8: list: middle -- 16,497.89 % -- [Elapsed: 0.2496461 sec]
9: list: end -- 32,715.52 % -- [Elapsed: 0.4950512 sec]
10: list: late -- 33,698.87 % -- [Elapsed: 0.5099313 sec]
drzaus
источник
7
Интересно. Спасибо за запуск этого. К сожалению, я подозреваю, что эти обсуждения вызывают бесполезный рефакторинг. Надеемся, что для большинства людей вывод состоит в том, что в вашем сценарии с абсолютным наихудшим случаем Listвсе еще требуется всего 0,17 миллисекунды для выполнения одного поиска, и вряд ли потребуется замена HashSetдо тех пор, пока частота поиска не достигнет абсурдных уровней. К тому времени использование List обычно является наименьшей из проблем.
Пол Уоллс
Это не актуальная информация на данный момент .. Или, возможно, это изначально неправильно ... Я только что проверил небольшие значения от 2 до 8 символов. List / HashSet были созданы для каждых 10 значений ... HashSet медленнее на 30% ... Если используется емкость в List, тогда разница даже ~ 40%. HashSet становится быстрее на 10%, только если у нас в List нет указанной емкости, и проверяет каждое значение перед добавлением через весь список.
Максим
Если количество предметов уменьшено до 4, то список снова побеждает даже в худшем сценарии (с разницей в 10%). Поэтому я не рекомендую использовать HashSet для небольшого набора строк (скажем, <20). И это то, что отличается от ваших «нескольких маленьких» тестов.
Максим
1
@ Максим не может сказать, что мои результаты "неправильные" - это то, что произошло на моей машине. YMMV. На самом деле я просто запустил их снова ( gist.github.com/zaus/014ac9b5a78b267aa1643d63d30c7554 ) на новом твердотельном компьютере Win10 4,0 ГГц 16 ГБ и получил аналогичные результаты. Вывод, который я вижу, заключается в том, что производительность хэш-набора была более стабильной независимо от того, где находился ключ поиска или насколько велик список, в то время как производительность списка сильно варьировалась от лучшего до более чем 300-кратного замедления. Но, как прокомментировал Пол Уоллс, мы говорим о серьезной # микрооптимизации.
drzaus
@ Максим для справки: dotnetfiddle.net/5taRDd - не стесняйтесь играть с ним.
drzaus
10

Безубыток будет зависеть от стоимости вычисления хэша. Хеш-вычисления могут быть тривиальными или нет ... :-) Всегда есть класс System.Collections.Specialized.HybridDictionary, чтобы не беспокоиться о точке безубыточности.

Вальден Леверих
источник
1
Вам также необходимо учитывать стоимость проведения сравнения. В случае Contains (T) HashSet выполнит сравнение, чтобы убедиться, что в нем нет коллизии Hash, по сравнению со списком, сравнивающим каждый элемент, на который он смотрит, прежде чем найдет правильный. Вы также должны принять во внимание распределение хэшей, сгенерированных T.GetHashCode (), как будто это всегда возвращает одно и то же значение, которое вы в основном заставляете HashSet делать то же самое, что List.
Мартин Браун
6

Ответ, как всегда, « Это зависит ». Я полагаю из тегов, которые вы говорите о C #.

Ваш лучший выбор - определить

  1. Набор данных
  2. Требования к использованию

и написать несколько тестов.

Это также зависит от того, как вы сортируете список (если он вообще сортируется), какого рода сравнения необходимо выполнить, сколько времени занимает операция «Сравнить» для определенного объекта в списке или даже как вы собираетесь использовать коллекция.

Как правило, лучший выбор не столько зависит от размера данных, с которыми вы работаете, сколько от того, как вы намереваетесь получить к нему доступ. У вас есть каждый фрагмент данных, связанный с определенной строкой или другими данными? Лучше всего подойдет коллекция на основе хешей. Важен ли порядок хранимых данных или вам потребуется доступ ко всем данным одновременно? Обычный список может быть лучше.

Дополнительно:

Конечно, мои комментарии выше предполагают, что «производительность» означает доступ к данным. Что еще нужно рассмотреть: что вы ищете, когда говорите «производительность»? Производительность индивидуальной ценности смотрит вверх? Это управление большими (10000, 100000 или более) наборами значений? Производительность заполнения структуры данных данными? Удаление данных? Доступ к отдельным битам данных? Замена значений? Перебирая значения? Использование памяти? Скорость копирования данных? Например, если вы обращаетесь к данным по строковому значению, но основным требованием к производительности является минимальное использование памяти, у вас могут возникнуть конфликтующие проблемы проектирования.

Роберт П
источник
5

Вы можете использовать HybridDictionary, который автоматически обнаруживает точку разрыва и принимает нулевые значения, делая его практически таким же, как HashSet.

MUIS
источник
1
Подтвердил это за идею, но никто, пожалуйста, никогда не используйте это сегодня. Скажи нет не-дженериков. Также словарь - это сопоставления ключ-значение, набор - нет.
nawfal
4

Это зависит. Если точный ответ действительно имеет значение, сделайте профилирование и узнайте. Если вы уверены, что в наборе никогда не будет больше определенного количества элементов, используйте Список. Если число не ограничено, используйте HashSet.

Адам Розенфилд
источник
3

Зависит от того, что вы хэшируете. Если ваши ключи целые числа, вам, вероятно, не нужно много элементов, прежде чем HashSet станет быстрее. Если вы вводите его в строку, это будет медленнее и зависит от входной строки.

Конечно, вы могли бы довольно легко поднять отметку?

Питер
источник
3

Одним из факторов, который вы не учитываете, является надежность функции GetHashcode (). С идеальной функцией хеширования HashSet, несомненно, будет иметь лучшую производительность поиска. Но с уменьшением хеш-функции время поиска HashSet будет уменьшаться.

JaredPar
источник
0

Зависит от множества факторов ... Реализация списка, архитектура процессора, JVM, семантика цикла, сложность метода equals и т. Д. К тому времени, когда список становится достаточно большим, чтобы эффективно тестировать (более 1000 элементов), двоичный двоичный код поиск превосходит линейный поиск, и оттуда разница только увеличивается.

Надеюсь это поможет!

рукав моря
источник
1
JVM ... или CLR :-)
bvgheluwe