Using EqualityComparer to find contained value While searching for a method in HashSet which allows me to actually find an object in \$O(1)\$ (not just Contains, I need the reference), I came across this question on Stack Overflow and specifically the latest answer drew my attention. 

I reworked the answer in a more generic approach and came up with the following;

public class EqualityComparerWithValue&lt;T&gt; : IEqualityComparer&lt;T&gt;
{
    public T Value;
    public bool Equals(T t1, T t2)
    {
        if (!(t1.GetHashCode() == t2.GetHashCode())) return false;
        if (!t1.Equals(t2)) return false;
        Value = t1;
        return true;
    }

    public int GetHashCode(T t)
    {
        return t.GetHashCode();
    }
}


Then an implementation of a potential \$O(1)\$ TryGetValue() would be something like this:

public static bool TryGetValue&lt;T&gt;(this HashSet&lt;T&gt; hs, T valIn, out T valOut)
{
    if (hs.Contains(valIn))
    {
        if (hs.Comparer is EqualityComparerWithValue&lt;T&gt;)
            valOut = (hs.Comparer as EqualityComparerWithValue&lt;T&gt;).Value;
        else
            valOut = hs.First(t =&gt; t.Equals(valIn));

        return true;
    }
    else
    {
        valOut = default(T);
        return false;
    }
}


Which will find the searched object in \$O(1)\$ if the EqualityComparerWithValue is specified in the constructor, and in \$O(n)\$ otherwise.

An implementation of this would be:

var set = new HashSet&lt;string&gt;(new EqualityComparerWithValue&lt;string&gt;());
string sOut = "";
if (set.TryGetValue("searchTerm", out sOut))
{
    //do stuff
}


Now, in my eyes, this seems to be a very legit solution. However, I'm just starting out. Are there any problems this could cause which I am overlooking? Is there any way to improve TryGetValue()?
if (!(t1.GetHashCode() == t2.GetHashCode())) return false;


Even if JIT compiler generated code will/should be the same negation operator is easy ignored during source code scanning by human beings. Because !(a == b) is effectively a != b I would rewrite it as:

 if (t1.GetHashCode() != t2.GetHashCode())
    return false;


Note I also reintroduced line breaks, it helps readability and for short functions (as they should be) there is not need to reduce vertical space.

Even if you shouldn't (generally) rely on these implementation details please
note that in your equality comparer you do not need to check for hashcode again.
HashSet already does it and it has an advantage over your code: it calculates
hashcode for item you're searching for just once. In your code you have to
calculate both hashes again and again for each comparison (and it may be slow,
according to effective data type and hashing algorithm). Please note that you shouldn't (IMO!) rely on this optimization on generic comparers because you do not have any knowledge of type implementation. Think what hashcode does for integer types, is it faster to calculate hash or to perform direct comparison? What about strings with different lengths? It may be done by a container (for example because hash is used to organize items) but, I think, a generic comparer should be ignorant of this.


if (hs.Comparer is EqualityComparerWithValue&lt;T&gt;)
    valOut = (hs.Comparer as EqualityComparerWithValue&lt;T&gt;).Value;
else
    valOut = hs.First(t =&gt; t.Equals(valIn));



You first check for type and then you cast (which implicitly check for type again). It's a waste then you may simply rewrite as this:

var comparer = hs.Comparer as EqualityComparerWithValue&lt;T&gt;;
valOut = comparer != null ? comparer.Value : hs.First(t =&gt; t.Equals(valIn));


On the same code block you also have a return then you don't need else, save indentation and make code clearer:

   if (hs.Contains(valIn))
   {
        var comparer = hs.Comparer as EqualityComparerWithValue&lt;T&gt;;
        valOut = comparer != null ? comparer.Value : hs.First(t =&gt; t.Equals(valIn));

        return true;
   }

    valOut = default(T);
    return false;


However, beside these minor micro-design stuff, what I don't agree with is solution itself. I wouldn't expect an equality comparer to keep state for at least these reasons:


It would be the only one to do it. Astonishing.
When you use your hashset you have to remember to use that comparer.
It forces you to check for types (and it's something with a pretty bad smell, IMO).
You're putting helpers inside an unrelated class. O(1) search is something related to hashset not to a specific type comparer.
It doesn't work with inherited comparers (what if I want to reuse same code with my own special IEqualityComparer&lt;T&gt; class?)
It's not thread-safe!


However algorithm itself probably isn't for CodeReview. What I would do to mitigate some of these issues? I would accept another
IEqualityComparer&lt;T&gt; as input, you decorate that comparer to keep last match
but you delegate comparison to given implementation:

public sealed class EqulEqualityComparerWithValue&lt;T&gt; : IEqualityComparer&lt;T&gt;
{
    public EqulEqualityComparerWithValue(IEqualityComparer&lt;T&gt; comparer = null)
    {
        _comparer = comparer ?? EqualityComparer&lt;T&gt;.Default;
    }

    public bool Equals(T x, T y)
    {
        if (_comparer.Equals(x, y))
        {
            Value = x;
            return true;
        }

        return false;
    }

    public int GetHashCode(T obj)
    {
        return _comparer.GetHashCode(obj);
    }

    public T Value
    {
        get;
        private set;
    }

    private IEqualityComparer&lt;T&gt; _comparer;
}