What .NET collection provides the fastest search
You should read this blog that speed tested several different types of collections and methods for each using both single and multi-threaded techniques.
According to the results, a BinarySearch on a List and SortedList were the top performers constantly running neck-in-neck when looking up something as a "value".
When using a collection that allows for "keys", the Dictionary, ConcurrentDictionary, Hashset, and HashTables performed the best overall.
If you don't need ordering, try HashSet<Record>
(new to .Net 3.5)
If you do, use a List<Record>
and call BinarySearch
.
In the most general case, consider System.Collections.Generic.HashSet
as your default "Contains" workhorse data structure, because it takes constant time to evaluate Contains
.
The actual answer to "What is the fastest searchable collection" depends on your specific data size, ordered-ness, cost-of-hashing, and search frequency.
Have you considered List.BinarySearch(item)
?
You said that your large collection is already sorted so this seems like the perfect opportunity? A hash would definitely be the fastest, but this brings about its own problems and requires a lot more overhead for storage.