Is there an implementation of IList<T> where Contains(T) is an O(1) operation?

Question

I'm wondering if there is an IList<T> implementation that's backed by a hash like HashSet<T> but offers indexed access?

To be clear, I'm not concerned on how to implement one, just wondering if anyone knows if it's already available.

Answer 1

KeyedCollection<TKey, TItem> provides this type of functionality, though you do have to derive from it and provide it with a function to extract a key from the item which is hashed.

Answer 2

You can have any number of (hashed or other) indexes into doubly linked list nodes (doubly linked so you have O(1) deletion).

Answer 3

There is none in .Net 3.5, but its very easy to implement one:

public class Set<T> : KeyedCollection<T,T>
{
    public Set()
    {}

    public Set(IEnumerable<T> collection)
    {
        foreach (T elem in collection)
        {
            Add(elem);
        }
    }

    protected override T GetKeyForItem(T item)
    {
        return item;
    }
}

Answer 4

You could implement IList<T> yourself and keep two backing collections - a List<T> and a HashSet<T>. Basically get Visual Studio to provide a "throw exception" implementation for everything in IList<T>, then for each method work out whether you want to proxy it to the list or the set.

Of course you'd have to be careful for duplicates etc (define the behaviour of Add(x), Add(x), Remove(x), Contains(x) - you could end up with it in the list but not the set) but it wouldn't be too hard.

Answer 5

HashSet<T> implements ICollection<T>, if that's any use. Available from 3.5 onwards.

Answer 6

Quick answer - no, it is not already available.

Implementing it is of course easy as you realise. The reason why it is not commonly implemented is as follows. If you can do contains in O(1) then you could do index lookup in O(1). But of course index lookup is not unique if you have duplicate elements.

As what you essentially need is two data structures, a Set (or Map) and a List, and there isn't a much more efficient way of doing it than this, the standard library authors leave you to combine the data-structures yourself.