Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What data structures in .NET do O(1) on Contains() calls?

Tags:

c#

.net

vb.net

I'm drawing a blank here; I can't find it, unless I'm really overlooking something under my nose.

I'm trying to store a list of ints in a data structure.
But after I add them, I will later in code check if an int exists in the list already.

The generic List<int> does an O(n) operation with its Contains().
I want something that works as fast as Dictionary<>'s Contains(), which does an O(1) operation because it hashes the keys.

I know the answer is something so simple and that I've worked for too long today I can't remember it.

Help!

like image 271
BeemerGuy Avatar asked Sep 28 '10 01:09

BeemerGuy


2 Answers

Will HashSet<T> work for you?

like image 133
Daniel A. White Avatar answered Sep 28 '22 15:09

Daniel A. White


Since I work with C# 2.0 because of platform constraints, I usually use Dictionary<int,bool>, with the constraint that if a key is in the map, the bool is true (so the bool isn't really encoding any information -- it's just a substitute for the missing unit type from .NET).

like image 37
luqui Avatar answered Sep 28 '22 14:09

luqui