linq Кроме и пользовательских IEqualityComparer

Question

Я пытаюсь реализовать пользовательский компаратор в двух списках строк и использую метод.Except() linq, чтобы получить те, которые не входят в один из списков. Причина, по которой я создаю собственный компаратор, заключается в том, что мне нужно выполнить "нечеткое" сравнение, то есть одна строка в одном списке может быть встроена в строку в другом списке.

Я сделал следующий компаратор

public class ItemFuzzyMatchComparer : IEqualityComparer<string>
{
    bool IEqualityComparer<string>.Equals(string x, string y)
    {
        return (x.Contains(y) || y.Contains(x));
    }

    int IEqualityComparer<string>.GetHashCode(string obj)
    {
        if (Object.ReferenceEquals(obj, null))
            return 0;
        return obj.GetHashCode();
    }
}

Когда я отлаживаю, единственная точка останова, которая попадает в метод GetHashCode(). Равные () никогда не трогают. Есть идеи?

Answer 1

Если все возвращенные хэш-коды различны, его никогда не нужно сравнивать на равенство.

По сути, проблема в том, что ваши концепции хэша и равенства очень разные. Я не совсем уверен, как вы это исправите, но пока вы не сделаете это, это точно не сработает.

Вы должны убедиться, что если Equals(a, b) возвращает истину, то GetHashCode(a) == GetHashCode(b), (Обратное не обязательно должно быть правдой - коллизии хешей допустимы, хотя, очевидно, вы хотите иметь как можно меньше из них.)

Answer 2

Как указал Джон, вам нужно убедиться, что хеш-код двух строк одинаков (согласно вашему правилу сравнения). Это, к сожалению, довольно сложно.

Чтобы продемонстрировать проблему, Equals(str, "") возвращает true для всех строк str, что по сути означает, что все строки равны пустой строке, и в результате все строки должны иметь такой же хэш-код, что и пустая строка. Поэтому единственный способ реализовать IEqualityComparer правильно всегда возвращать один и тот же хеш-код:

public class ItemFuzzyMatchComparer : IEqualityComparer<string>  { 
  bool IEqualityComparer<string>.Equals(string x, string y)  { 
    return (x.Contains(y) || y.Contains(x)); 
  }  
  int IEqualityComparer<string>.GetHashCode(string obj)  { 
    if (Object.ReferenceEquals(obj, null)) return 0; 
    return 1; 
  } 
}

Тогда вы можете использовать Except метод, и он будет вести себя правильно. Единственная проблема в том, что вы (вероятно) получите довольно неэффективную реализацию, поэтому, если вам нужна более высокая производительность, вам, возможно, придется реализовать свою собственную Except, Однако я не совсем уверен, насколько неэффективной будет реализация LINQ, и я не уверен, возможно ли вообще иметь какую-либо эффективную реализацию для вашего правила сравнения.

Answer 3

Возможно, эту проблему можно решить без реализации интерфейса IEqualityComparer. У Джона и Томаса есть хорошие моменты в реализации этого интерфейса, и равенство, похоже, не определяет вашу проблему. Из вашего описания, я думаю, вы могли бы сделать это без использования расширения Except во время сравнения. Вместо этого сначала найдите совпадения, а затем выполните исключение. Посмотрите, подходит ли вам эта работа:

 List<String> listOne = new List<string>(){"hard", "fun", "code", "rocks"};
 List<String> listTwo = new List<string>(){"fund", "ode", "ard"};

 var fuzzyMatchList = from str in listOne
                      from sr2 in listTwo
                      where str.Contains(sr2) || sr2.Contains(str)
                      select str;
 var exceptList = listOne.Except(fuzzyMatchList);