How to generate a unique hash for a collection of objects independent of their order [duplicate]

Question 1

For optimal performance I would try to avoid iterating the whole collection every time GetHashCode is called. The purpose of GetHashCode is to improve performance to a point better than evaluating every element. So I might try maintaining the hash code when elements in the list are changed like this.

class Program
{
  static void Main(string[] args)
  {
     MyClassList l = new MyClassList() { new MyClass() {Type="Bob", Id=1}, new MyClass() {Type="Jones", Id=2}};
     MyClassList l2 = new MyClassList() { new MyClass() { Type = "Jones", Id = 2 }, new MyClass() { Type = "Bob", Id = 1 } };
     MyClassList l3 = new MyClassList() { new MyClass() { Type = "Jones", Id = 2 }};
     Console.WriteLine("{0} {1} {2}", l.GetHashCode(), l2.GetHashCode(), l3.GetHashCode());
     l3.Add(new MyClass() { Type = "Bob", Id = 1 });
     Console.WriteLine("{0}", l3.GetHashCode());
  }
}

public class MyClass
{
  public string Type { get; set; }
  public int Id { get; set; }
  public override int GetHashCode()
  {
     return (Type.GetHashCode() % 0x8000) | (int)((uint)Id.GetHashCode() & 0xFFFF0000);
  }
}

public class MyClassList : IList<MyClass>
{
  List<MyClass> internalList;
  int hashCode = 0;

  public MyClassList()
  {
     internalList = new List<MyClass>();
  }

  private void IncludeInHash(MyClass item)
  {
     hashCode ^= item.GetHashCode();
  }

  private void ExcludeFromHash(MyClass item)
  {
     IncludeInHash(item);
  }

  public override int GetHashCode()
  {
     return hashCode;
  }

  public int IndexOf(MyClass item)
  {
     return internalList.IndexOf(item);
  }

  public void Insert(int index, MyClass item)
  {
     internalList.Insert(index, item);
     // Make sure Insert is successful (doesn't throw an exception) before affecting the hash
     IncludeInHash(item);
  }

  public void RemoveAt(int index)
  {
     MyClass reduce = internalList[index];
     internalList.RemoveAt(index);
     // Make sure RemoveAt is successful before affecting the hash
     ExcludeFromHash(reduce);
  }

  public MyClass this[int index]
  {
     get
     {
        return internalList[index];
     }
     set
     {
        MyClass reduce = internalList[index];
        internalList[index] = value;
        // Make sure these happen atomically; don't allow exceptions to prevent these from being accurate.
        ExcludeFromHash(reduce);
        IncludeInHash(value);
     }
  }

  public void Add(MyClass item)
  {
     internalList.Add(item);
     IncludeInHash(item);
  }

  public void Clear()
  {
     internalList.Clear();
     hashCode = 0;
  }

  public bool Contains(MyClass item)
  {
     return internalList.Contains(item);
  }

  public void CopyTo(MyClass[] array, int arrayIndex)
  {
     internalList.CopyTo(array, arrayIndex);
  }

  public int Count
  {
     get { return internalList.Count; }
  }

  public bool IsReadOnly
  {
     get { return false; }
  }

  public bool Remove(MyClass item)
  {
     if (internalList.Remove(item))
     {
        ExcludeFromHash(item);
        return true;
     }
     else
        return false;
  }

  public IEnumerator<MyClass> GetEnumerator()
  {
     return internalList.AsReadOnly().GetEnumerator();
  }

  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  {
     return GetEnumerator();
  }
}

Question 2

I propose this solution (I didn't implement the Equals method) :

public class MyClass
{
    public string Type { get; set; }
    public int Id { get; set; }

    public override int GetHashCode()
    {
        int hash = 17;
        hash = hash + 23 * this.Type.GetHashCode();
        hash = hash + 23 * this.Id.GetHashCode();
        return hash;
    }
}

public class MyClassList : List<MyClass>
{
    public MyClassList(IEnumerable<MyClass> enumerable) : base(enumerable) { }

    public override int GetHashCode()
    {
        return this.Aggregate(17, (state, current) => state * 23 + current.GetHashCode());
    }
}

The way to generate the hashcode is inspired from Microsoft method to compute the hash value for anonymous objects.

Question 3

The solution given by clto works. Here is an alternative: sort the list by some total ordering (any ordering will do, as long as it is unambiguous). Then you can calculate the hash code using any normal means. You don't need order-independence. You could even use a cryptographic hash function.

Question 4

If the order isn't important then you should use a collection that inherently is a set, rather than a list.

Also, it's generally best to not inherit from collections; use composition instead.

So for a collection you can use a HashSet, as it will have set semantics.

To have MyClass use both properties as it's identity just override it's equals and get hash code implementations, or create an IComparer<MyClass> if you can't or don't want to do that.

public class MyClass:IEquatable<MyClass>
{
    public string Type { get; set; }
    public int Id { get; set; }

    public override bool Equals(object obj)
    {
        return Equals(obj as MyClass);
    }

    public bool Equals(MyClass other)
    {
        if (other == null)
            return false;

        return Type == other.Type &&
            Id == other.Id;
    }

    public override int GetHashCode()
    {
        return Type.GetHashCode() * 79 + Id;
    }
}

Then your collection is as simple as:

HashSet<MyClass> set = new HashSet<MyClass>();

And if you want to compare various sets just use:

HashSet<MyClass>.CreateSetComparer();