Как HashSet <T>.Contains быстрее, чем List <T>.Contains?

Question

У меня есть простое требование: у меня есть миллионы строк, и я хочу проверить, существуют ли они в небольшом наборе. Я сомневаюсь между использованием List<T> против HashSet<T> для этого набора.

Когда требование противоположное, например, у вас есть 100 строк, и вам нужно проверить, существуют ли они в наборе миллионов строк, я полностью понимаю, что HashSet<T> - лучший выбор.

Но в моем случае кажется, что .NET должен вычислять миллионы хешей (вызовов GetHashCode) при вызове Contains на HashSet<T>, поэтому вызов Contains из List<T> может быть быстрее

Может кто-нибудь объяснить, правильно ли это предположение?

Answer 1

Ничто из этого не кажется мне подходящим - HashSet<string> звучит так, как будто это может быть лучшим подходом для меня.

Да, .NET должен вычислять хеш-код для каждой строки - вопрос в том, займет ли это столько времени, сколько потребуется проверки на равенство с каждой из сотен строк в наборе кандидатов.

Как и во всех вопросах производительности, вы должны проверить это, а не угадывать. Например, если все строки имеют разную длину и все они длинные, то Equals будет дешевым для каждого кандидата, а GetHashCode может занять много времени. Однако, если все ваши строки имеют длину 10, начиная с одних и тех же 6 символов, скажем, тогда GetHashCode будет достаточно дешевым, но каждая проверка на равенство строк должна будет проверять все эти общие префиксные символы. Что из этого больше похоже на вашу реальную ситуацию? Что показали ваши тесты? Как быстро вам нужно это будет?

Answer 2

Я думаю, что Dictionary кэширует хэш ключей и явно вычислит только один раз хеш строки, которую вы ищете.Я добавлю, что если ваш набор строк статичен и редко изменяется, вы могли бы быстрее отсортировать неизменный список и использовать Array.BinarySearch, но, вероятно, я бы не стал этого делать, потому что это сделало бы код слишком сложным (еслисравнив его, я убедился, что это намного быстрее.)