Fastest way to check if two List<T> are equal

Question

I have two Lists

ListA<Emp> and ListB<Emp> both are having 1000 records.

Emp is an object of Employee Class. Below is my Employee class

public class Employee
{
    int ID = 0;
    string Name = String.Empty;
    string Dept = String.Empty;
    string Address = String.Empty;
    int Age = 0;
    string Email = String.Empty;
}

I want to verify if both the Lists are equal. The Emp objects may be placed in different order. Also, there might be several Emp objects which are having exactly same info in both the list. I have to verify those also.

I tried to sort the lists and compared using SequenceEqual

Enumerable.SequenceEqual(ListA.OrderBy(s => s), ListB.OrderBy(s => s)

I am getting below error

At least one object must implement IComparable.
Exception Stack trace is as below 

   at System.Collections.Comparer.Compare(Object a, Object b)
   at System.Collections.Generic.ObjectComparer`1.Compare(T x, T y)
   at System.Linq.EnumerableSorter`2.CompareKeys(Int32 index1, Int32 index2)
   at System.Linq.EnumerableSorter`1.QuickSort(Int32[] map, Int32 left, Int32 right)
   at System.Linq.EnumerableSorter`1.Sort(TElement[] elements, Int32 count)
   at System.Linq.OrderedEnumerable`1.<GetEnumerator>d__0.MoveNext()
   at System.Linq.Enumerable.SequenceEqual[TSource](IEnumerable`1 first, IEnumerable`1 second, IEqualityComparer`1 comparer)
   at System.Linq.Enumerable.SequenceEqual[TSource](IEnumerable`1 first, IEnumerable`1 second)

How can I implement this ? Also it will be better if you guys can provide me the fastest way of doing this because the number of objects in List may grow to 10 million. Thanks for your help !

EDIT: Every employee must be in both list, order does not matter. But, if ListA contains same employee object 5 times (that means some duplicate entries), and ListB contains the employee object 4 times, then ListA and ListB are not equal.

Answer 1

Best complexity is O(N) Following realization with using HashSet:

Class with implementation of GetHashCode and Equals:

public class Employee
{
    public int ID = 0;
    public string Name = String.Empty;
    public string Dept = String.Empty;
    public string Address = String.Empty;
    public int Age = 0;
    public string Email = String.Empty;

    public override int GetHashCode()
    {
        return
            ID.GetHashCode() ^
            (Name ?? String.Empty).GetHashCode() ^
            (Dept ?? String.Empty).GetHashCode() ^
            (Address ?? String.Empty).GetHashCode() ^
            Age.GetHashCode() ^
            (Email ?? String.Empty).GetHashCode()
            ;
    }
    public override bool Equals(object obj)
    {
        Employee other = obj as Employee;
        if (obj == null)
            return false;

        return ID == other.ID &&
                Name == other.Name &&
                Dept == other.Dept &&
                Address == other.Address &&
                Age == other.Age &&
                Email == other.Email;
    }
}

Function to compare lists:

public static bool CompareLists(List<Employee> list1, List<Employee> list2)
{
    if (list1 == null || list2 == null)
        return list1 == list2;

    if (list1.Count != list2.Count)
        return false;
    Dictionary<Employee, int> hash = new Dictionary<Employee, int>();
    foreach (Employee employee in list1)
    {
        if (hash.ContainsKey(employee))
        {
            hash[employee]++;
        }
        else
        {
            hash.Add(employee, 1);
        }
    }

    foreach (Employee employee in list2)
    {
        if (!hash.ContainsKey(employee) || hash[employee] == 0)
        {
            return false;
        }
        hash[employee]--;
    }

    return true;
}

Answer 2

You can use SequenceEqual with a custom IEqualityComparer<Employee>:

class EmployeeComparer : IEqualityComparer<Employee>
{
    public bool Equals(Employee x, Employee y)
    {
        if (x == null || y == null) return false;

        bool equals = x.ID==y.ID && x.Name == y.Name && x.Dept == y.Dept 
            && x.Address == y.Address && x.Age == y.Age && x.Email == y.Email;
        return equals;
    }

    public int GetHashCode(Employee obj)
    {
        if (obj == null) return int.MinValue;

        int hash = 19;
        hash = hash + obj.ID.GetHashCode();
        hash = hash + obj.Name.GetHashCode();
        hash = hash + obj.Dept.GetHashCode();
        hash = hash + obj.Address.GetHashCode();
        hash = hash + obj.Age.GetHashCode();
        hash = hash + obj.Email.GetHashCode();
        return hash;
    }
}

Now it's so simple:

listA.SequenceEqual(ListB, new EmployeeComparer());

If the order is not important and you only want to know if all employees are in both lists you can use HashSet<Employee>.SetEquals to determine if both lists contain the same people:

var empComparer =  new EmployeeComparer();
bool bothEqual = new HashSet<Employee>(ListA, empComparer)
      .SetEquals(new HashSet<Employee>(ListB, empComparer));

Answer 3

If the numbers in the list are going to grow enormous (10M), you are probably going to have to consider parallelization of the look-up to get an acceptable query time.

Consider using PLINQ.

Some more clarity on what you mean by 'equal' would be good. How complex is the equivalence check? Are you checking that the objects are the same or that the objects values are the same?

Another consideration would be this; if the number of elements are going to become large, could you consider moving this check down from .NET into your database - perhaps as a stored procedure? You may find it executes more efficiently there.