4
\$\begingroup\$

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<T> : IEqualityComparer<T>
{
    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<T>(this HashSet<T> hs, T valIn, out T valOut)
{
    if (hs.Contains(valIn))
    {
        if (hs.Comparer is EqualityComparerWithValue<T>)
            valOut = (hs.Comparer as EqualityComparerWithValue<T>).Value;
        else
            valOut = hs.First(t => 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<string>(new EqualityComparerWithValue<string>());
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()?

\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

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<T>)
    valOut = (hs.Comparer as EqualityComparerWithValue<T>).Value;
else
    valOut = hs.First(t => 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<T>;
valOut = comparer != null ? comparer.Value : hs.First(t => 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<T>;
        valOut = comparer != null ? comparer.Value : hs.First(t => 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<T> 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<T> as input, you decorate that comparer to keep last match but you delegate comparison to given implementation:

public sealed class EqulEqualityComparerWithValue<T> : IEqualityComparer<T>
{
    public EqulEqualityComparerWithValue(IEqualityComparer<T> comparer = null)
    {
        _comparer = comparer ?? EqualityComparer<T>.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<T> _comparer;
}
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the input! I really like the decorator approach. Is it not being thread safe a big issue? AFAIK HashSet itself is not thread safe either. I like how you mention reasons on why you don't agree with the solution itself and they make a point, but how would you rather implement it? I was thinking of a Dictionary, but figured it would be too much refactoring. Any other solutions? \$\endgroup\$
    – Dion V.
    Nov 9, 2015 at 11:41
  • \$\begingroup\$ Hashset is not thread-safe for concurrent writes/reads but it can safely accept multiple concurrent reads (for this reason it may be protected by a simple ReadWriterLockSlim). If you use this approach...even reads aren't thread-safe (even worse...equality comparer isn't thread-safe, an object that should be stateless). \$\endgroup\$ Nov 9, 2015 at 11:46
  • \$\begingroup\$ What to do? It depends if you need to keep HashSet<T> in-place or not. If you can drop it in favor of your own implementation (just pick its implementation from Reference Source and imply add the single method you need...) \$\endgroup\$ Nov 9, 2015 at 11:47
5
\$\begingroup\$

Your Equals() method of the EqualityComparerWithValue is flawed because a HasSet<T> allows adding of null if T != struct which by checking GetHashCode will throw an NullReferenceException which will bubble up the TryGetValue() method.

A TryGetValue() implies that no exception is beeing thrown, so that method is, at least if this comparer is used, flawed too.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the input! So, checking on null in the equals would solve the problem, right? Returning false in either case of null seems to be the way to go then? \$\endgroup\$
    – Dion V.
    Nov 9, 2015 at 11:33
  • 2
    \$\begingroup\$ No exactly. If both are null it should return true. See: msdn.microsoft.com/en-us/library/w4hkze5k%28v=vs.110%29.aspx \$\endgroup\$
    – Heslacher
    Nov 9, 2015 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.