Set-like collection in C#/.NET

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.

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

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.

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

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

I would like to, but...

Quote:

---

You must spread some Reputation around before giving it to Norfy again.

---

Ah yes, multiple inheritance post ;)

Quote:

---

Originally Posted by Norfy

Ah yes, multiple inheritance post ;)

---

Yes. :blush:

Quote:

---

Originally Posted by mehdi62b (Rating Comment)

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.

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. :)

Quote:

---

Originally Posted by Norfy

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).

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.

Quote:

---

Originally Posted by Norfy

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:

Quote:

---

Originally Posted by mehdi62b

I meant it doesn't use hashing...and you tell it use hashing(how?) ..I don't know exactly.

---

Have you checked out Reflector yet?

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

I will check that link :thumb:

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 Contains(object item);Declaring Type:System.Collections.ArrayList

Code:

---

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...

public virtual object this[object key] { get; set; }Declaring Type:System.Collections.Hashtable

Code:

---

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 ContainsKey(object key);Declaring Type:System.Collections.Hashtable

Code:

---

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:

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)

Quote:

---

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. :)

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

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.

Quote:

---

Originally Posted by Norfy

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!

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.