Set-like collection in C#/.NET

[emirc]

Is there a collection among .NET collection that doesn't allow duplicates?
ArrayList is very suitable for what I need, except it allows duplicate values.
I've searched the System.Collections namespace but couldn't find anything alike.

[Norfy]

Couldn't find one myself so knocked up a simple implementation of Set

[emirc]

Thank you Norfy, very nice implementation.
I was going to implement a set anyway,
just wanted to check if there's already an implementation among .NET's collections.

[Norfy]

No problem, just thought I would save you some typing.

For that alone could you 'rate this post'? :)

[emirc]

I would like to, but...
You must spread some Reputation around before giving it to Norfy again.

[Norfy]

Ah yes, multiple inheritance post ;)

[emirc]

Ah yes, multiple inheritance post ;)
Yes. :blush:

[Norfy]

I learnt this from you,didn't get why you used a hashtable while you set every key to null..wel we could also use an IList..
Quite simply, the behaviour of the keys collection of a Hashtable is that of a set.
For small sets then an IList is ok but for larger sets a Hashtable is quicker.

[emirc]

there are some interesting collections that NHibernate uses...
the DLL is Iesi.Collections.
I don't know the licensing policy, but i think they're ok generally. :)

[mehdi62b]

For small sets then an IList is ok but for larger sets a Hashtable is quicker.we want to just look for in an collection and keys in hashtable are just an ICollection ...hastable is fast but when we give a key and want its item,well its time is O(1)
but when we want to get whether an item is included or not..
no difference between a hashtable(keys) and IList...(both of them are an ICollection)
both of them have O(n).

[Norfy]

Sorry mehdi62b I couldn't follow your comment.

Whether you ask a Hashtable for a value or if it contains a key the access time is not linear O(n) , it uses hashing for both.

The keys are returned as an ICollection but are not implemented as such internally.

[mehdi62b]

Whether you ask a Hashtable for a value or if it contains a key the access time is not linear O(n) , it uses hashing for both.I meant when we ask a hashtable whetere it contains a key the time is not O(1)..I meant it doesn't use hashing...
and you tell it use hashing(how?) ..I don't know exactly..
no problem...should have a look at one of my book :wave:

[Norfy]

I meant it doesn't use hashing...and you tell it use hashing(how?) ..I don't know exactly.
Have you checked out Reflector (http://www.aisto.com/roeder/dotnet/) yet?

Nice tool, lets you browse the (decompiled) core .NET libraries.

[mehdi62b]

I will check that link :thumb:

[mehdi62b]

Hi Norfy,
thank you very much for that link..I didn't know it..its very usefull tool
and yes,you were right..

public virtual bool (http://www.aisto.com/roeder/dotnet/Default.aspx?Object=1) Contains(object (http://www.aisto.com/roeder/dotnet/Default.aspx?Object=2) item);Declaring Type:System.Collections.ArrayList


public virtual bool Contains(object item)
{
if (item == null)
{
for (int num1 = 0; num1 < this._size; num1++)
{
if (this._items[num1] == null)
{
return true;
}
}
return false;
}
for (int num2 = 0; num2 < this._size; num2++)
{
if (item.Equals(this._items[num2]))
{
return true;
}
}
return false;
}
and it clearly shows it has O(n)

and to be countinued...

[mehdi62b]

public virtual object (http://www.aisto.com/roeder/dotnet/Default.aspx?Object=1) this[object (http://www.aisto.com/roeder/dotnet/Default.aspx?Object=2) key] { get; set; }Declaring Type:System.Collections.Hashtable
public virtual object this[object key]
{
get
{
uint num1;
uint num2;
Hashtable.bucket bucket1;
if (key == null)
{
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Hashtable.bucket[] bucketArray1 = this.buckets;
uint num3 = this.InitHash(key, bucketArray1.Length, out num1, out num2);
int num4 = 0;
do
{
int num5 = (int) (num1 % bucketArray1.Length);
bucket1 = bucketArray1[num5];
if (bucket1.key == null)
{
return null;
}
if (((bucket1.hash_coll & 0x7fffffff) == num3) && this.KeyEquals(key, bucket1.key))
{
return bucket1.val;
}
num1 += num2;
}
while ((bucket1.hash_coll < 0) && (++num4 < bucketArray1.Length));
return null;
}
set
{
this.Insert(key, value, false);
}
}

and it should be O(1)

public virtual bool (http://www.aisto.com/roeder/dotnet/Default.aspx?Object=1) ContainsKey(object (http://www.aisto.com/roeder/dotnet/Default.aspx?Object=2) key);Declaring Type:System.Collections.Hashtable
public virtual bool ContainsKey(object key)
{
uint num1;
uint num2;
Hashtable.bucket bucket1;
if (key == null)
{
throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
}
Hashtable.bucket[] bucketArray1 = this.buckets;
uint num3 = this.InitHash(key, bucketArray1.Length, out num1, out num2);
int num4 = 0;
do
{
int num5 = (int) (num1 % bucketArray1.Length);
bucket1 = bucketArray1[num5];
if (bucket1.key == null)
{
return false;
}
if (((bucket1.hash_coll & 0x7fffffff) == num3) && this.KeyEquals(bucket1.key, key))
{
return true;
}
num1 += num2;
}
while ((bucket1.hash_coll < 0) && (++num4 < bucketArray1.Length));
return false;
}

and how similar to the perevious one!!and it should be O(1)
thank you very much :wave:

[cjard]

how about a real world test? i use a hashtable to weed out the lines of a text file, that are the same as the previous day's text file.. a bit like sql minus union..

a text file 4 megabytes big, with 100000 lines, is processed in about a second:

read all of file one into hashtable, using the whole line as the key, and null as the value
read file 2 and call ContainsKey repeatedly on the hashtable.. if the HT doesnt containskey the line being read, write it out to a third output file.


i htink my program is IO bound, as it takes just less than a second for files only a few hundred lines long...


so in a word.. yes there is a set/collection that disallows duplicate values: use a hashtable with the values you want to store as the Key, and NULL as the value.
ht.put(myValue, null)

[Norfy]

so in a word.. yes there is a set/collection that disallows duplicate values: use a hashtable with the values you want to store as the Key, and NULL as the value.
ht.put(myValue, null)or wrap this behaviour in a class called Set which is what the last few posts have been about. :)

[Andy Tacker]

How about simply implementing the CollectionBase class? it's pretty handy for these kind of stuff...

[Norfy]

Sorry Andy but I don't think that is a good idea. CollectionBase gives you nothing more than an underlying list.

Anything to do with Set functionality you would have to write yourself, which with a basic implementation gives you something similar to
mehdi62b's solution.

[Elorn]

Couldn't find one myself so knocked up a simple implementation of Set

Was about to start on implementing exactly this, then decided to have a quick look on the net first and came across your post.
Very nice implementation, cheers!

[Matt Heffron]

Look at System.Collections.Generic.HashSet<T> generic class in .NET 3.5.
As a generic it is type-safe and avoids the boxing/unboxing operations if the "elements" are value types.