c# HashSet init takes too long

Question

I'm dealing with the fact that I need to init a HashSet with a set of elements but without any kind of comparation class.

After the init, any element added to the HashSet need to be passed with a comparator.

How can I accomplish it?

Now I have this:

HashSet<Keyword> set = new HashSet<Keyword>(new KeyWordComparer());

The problem is that the init takes to long and there's no necessity in applying the comparation.

KeywordComparer Class:

class KeyWordComparer : EqualityComparer<Keyword>
{
    public override bool Equals(Keyword k1, Keyword k2)
    {
        int equals = 0;
        int i = 0;
        int j = 0;

        // based on sorted ids
        while (i < k1._lista_modelos.Count && j < k2._lista_modelos.Count)
        {
            if (k1._lista_modelos[i] < k2._lista_modelos[j])
            {
                i++;
            }
            else if (k1._lista_modelos[i] > k2._lista_modelos[j])
            {
                j++;
            }
            else
            {
                equals++;
                i++;
                j++;
            }
         }

         return equals >= 8;
    }
    public override int GetHashCode(Keyword keyword)
    {
        return 0;//notice that using the same hash for all keywords gives you an O(n^2) time complexity though.
    }
}

Note: This is a follow-up question to c# comparing list of IDs.

Answer 1

every keyword has 20 IDs, so when I want to add a new Keyword to the HashSet, the KeywordComparer check that the new one does not have more than 8 ID's repeated with any keyword of the HashSet.In such case, new keyword is not included, if not, it's included.

Collecting these keywords is not a job for a hash set here. A hash set is generally not suited for items which depend on other elements of the set. You should only use it for things where a useful hash can be calculated for every item. Since it depends on the existing set of items whether a new item gets added to your set, this is totally the wrong tool.

Here’s an attempt to solve this problem according to your short description of what you actually want to do. Here, we are simply collecting the keywords in a list. In order to verify that they may be added, we use an addition hash set to collect the ids of the keywords. That way, we can quickly check for a new item, whether 8 or more of its ids are already contained within the list of keywords.

var keywords = new List<Keyword>();
var selectedIds = new HashSet<int>(); // I’m assuming that the ids are ints here

foreach (var keyword in GetListOfAllKeywords())
{
    // count the number of keyword ids that are already in the selectedIds set
    var duplicateIdCount = keyword.Ids.Count(id => selectedIds.Contains(id));

    if (duplicateIdCount <= 8)
    {
        // less or equal to 8 ids are already selected, so add this keyword
        keywords.Add(keyword);

        // and collect all the keyword’s ids
        selectedIds.AddRange(keyword.Ids);
    }
}

Answer 2

If I stay away from the fact if using the HashSet is the right type for the job at hand or if your Comparer even makes sense implementing a proper GetHashCode does seem to make a huge difference.

Here is an example implementation, based on an answer from Marc Gravell:

class KeyWordComparer : EqualityComparer<Keyword>
{
    // omitted your Equals implentaton for brevity

    public override int GetHashCode(Keyword keyword)
    {
        //return 0; // this was the original
        // Marc Gravell https://stackoverflow.com/a/371348/578411
        int hash = 13;
        // not sure what is up with the only 8 ID's but I take that as a given
        for(var i=0; i < Math.Min(keyword._lista_modelos.Count, 8) ; i++)
        {
            hash = (hash * 7) + keyword._lista_modelos[i].GetHashCode();
        }
        return hash;
    }
}

When I run this in LinqPad with this test rig

   Random randNum = new Random();
   var kc = new KeyWordComparer();
   HashSet<Keyword> set = new HashSet<Keyword>(kc);
   var sw = new Stopwatch();
   sw.Start();
   for(int i =0 ; i< 10000; i++)
   {
     set.Add(new Keyword(Enumerable
            .Repeat(0, randNum.Next(1,10))
            .Select(ir => randNum.Next(1, 256)).ToList()));
   }
   sw.Stop();
   sw.ElapsedMilliseconds.Dump("ms");

this is what I measure:

• 7 ms for 10,000 items

If I switch back to your return 0; implementation for GetHashCodeI measure

• 4754 ms for 10,000 items

If I increase the testloop to insert 100,000 items the better GetHashCode still completes in 224 ms on my box. I didn't wait for your implementation to finish.

So if anything implement a proper GetHashCode method.