Поиск в коллекциях или когда O(N) быстрее O(1) #dotnet #csharp #performance Сравниваются Array.Contains и HashSet.Contains для int и string на .NET 6/8/10 с бенчмарками; объясняют, почему на малых коллекциях массивы иногда быстрее и какие аппаратные и компиляторные оптимизации за это отвечают. 🔎 На малых коллекциях (≈5–10 элементов) массивы в некоторых условиях обгоняют HashSet — в тестах на .NET 10 это наблюдается для int и особенно для string. ⚡ .NET 8 внедрил векторизацию (Vector128/256/512) и SIMD-инструкции (AVX2/AVX‑512), что существенно уменьшает константу при последовательном поиске, но алгоритм остаётся O(N). 🧠 В .NET 10 JIT/PGO и Guarded Devirtualization позволяют инлайнить сравнения (особенно для string), увеличивая размер кода, но снижая число виртуальных вызовов и такты процессора. 🧩 HashSet по‑прежнему даёт предсказуемое O(1) поведение и выигрывает на больших коллекциях; для int разница может быть небольшой, для длинных или частых поисков HashSet выгоднее. 🛠️ В авторском анализаторе есть правило, предлагающее заменить Contains на HashSet для версий .NET ≤8 (порог срабатывания можно настроить через dotnet_diagnostic.CI0008.min_items_count). https://habr.com/ru/companies/skbkontur/articles/1012968/ @aStateOfNet