What is the most efficient data structure to store a list of integers that need to be looked up a lot in .Net?

Question

I need an efficient data structure to store a list of integers. The amount in the list could range from 1 to probably never more than 1000. The list will be queried about 20 times per request. What would be the most efficient collection type to store these in?

UPDATE

To give a little more insight, we'll take www.wikipediamaze.com (a little game I wrote) as an example (not the real scenario but close enough for conversation). For the list of puzzles on any given page, I am currently returning a list from the puzzles table joined to the table that stores which puzzles the current user has played. Instead I want to cache the list of puzzles agnostic to the user. So what I am doing is first loading and caching the list of puzzles from the database. Then I load and cache the list of puzzles the user has played. Then when I am iterating over the puzzles to display them, I want to do this:

protected BestDataStructure<long> PlayedPuzzles {get; set;} //Loaded from session

protected bool HasBeenPlayed(long puzzleId)
{
    return PlayedPuzzles.Contains(puzzleId)
}

Whenever they play a new puzzle I will save the record to the database and append it to the list stored in the session.

Thanks!

Answer 1

It depends on how you need to query them, but a simple array, or HashSet<int> springs to mind.

Both are O(1) when you index into them. HashSet.Contains is also O(1).

In response to your comment on the question: Use HashSet, since you need to check whether a specified integer exists. You should use Contains() on HashSet to do this; it will give you the best performance. If you need to store some other value related to the value, perhaps use Dictionary.

Answer 2

HashSet(int).

Answer 3

If you're looking for a structure that efficiently does an operation such as Contains(), then HashSet<int> is what you're looking for. HashSet<int> is O(1) (constant time) for Contains(), which is as good a complexity as you're going to get.

Answer 4

if you need to check for presence of element, then probably bool[] with 1000 elements and set true for existing integer elements?