Можно ли написать функцию хеш-кода для сравнения, совпадающего со многими?

Question

Могу ли я написать функцию хеш-кода для следующей логики сравнения?

Два экземпляра My равны, если совпадают по меньшей мере два свойства от (A, B, C).

Часть равных проста, но я нахожусь на части хеш-кода, и часть меня думает, что это будет невозможно.

class MyOtherComparer : IEqualityComparer<My> 
{ 
    public bool Equals(My x, My y) 
    { 
     if (Object.ReferenceEquals(x, y)) 
      return true;  

     if (Object.ReferenceEquals(x, null) || Object.ReferenceEquals(y, null)) 
      return false; 

     int matches = 0; 

     if(x.A == y.A) matches++; 

     if(x.B == y.B) matches++; 

     if(x.C == y.C) matches++; 

     // match on two out of three 
     return (matches > 1) 
    } 

    // If Equals() returns true for a pair of objects 
    // then GetHashCode() must return the same value for these objects. 
    public int GetHashCode(My x) 
    { 
     // ??? 
    } 
} 

UPDATE: В дополнении к правильному ответу Рида Copsey, очень важным момент о общей полезности нечеткого компаратора четко заявил Этан Браун - пожалуйста, смотрите его ответа, а также для полного понимания того, что лежит в основе этого Вопроса/ответа.

Answer 1

Да, это возможно. Простейшей реализацией было бы всегда возвращать константу.

public int GetHashCode(My x) 
{ 
    return 0; 
} 

В GetHashCode документация говорится:

Реализация должна гарантировать, что если метод Equals возвращает истину для двух объектов х и у, то значение, возвращаемое метод GetHashCode для й должно равняться значение, возвращаемое для y.

Однако вы можете свободно возвращать один и тот же хэш-код для двух объектов, которые не равны.

Это, как говорится, потенциально может привести к тому, что некоторые алгоритмы будут выполняться очень плохо, так как вы получите много хэш-коллизий. Однако, учитывая характер вашей нечетной/уникальной проверки равенства, это может потребоваться.

---

Обратите внимание, что это будет проблематично в любом случае. Учитывая вашу логику, возможно иметь три объекта, где comparer.Equals(foo, bar)==true и comparer.Equals(foo, baz)==true, но comparer.Equals(baz, bar)==false. Вероятно, это будет проблематично во многих случаях, когда используется IEqualityComparer<T>.

Answer 2

Хэш-код должен быть одинаковым для двух равных объектов, но он не должен быть разным для двух разных объектов. Вы можете вернуть такое же значение для всех объектов, чтобы удовлетворить потребителей IEqualityComparer, но я не знаю, как получить какую-либо выгоду от хэша в вашей ситуации.

Answer 3

Могу ли я написать функцию хеш-кода для следующей логики сравнения?

Да. Вы всегда можете написать хеш-код для чего-либо. Вопрос в том, насколько он эффективен. Независимо от того, вы всегда можете иметь:

public int GetHashCode() 
{ 
    return 0; 
} 

Он всегда будет работы, но это ужасно * неэффективно *.

Answer 4

Предположим, что у нас есть 2 объекта A, B. Каждый из них обладает свойствами p1, p2 и p3. Предположим, что A.p1 == B.p1 и A.p3 == B.p3, если хеш-функция зависит от p2, она будет отличаться для A и B, поэтому они не равны.Если вы хотите вычислить хеш-функцию на основе p1 и p3, существует много примеров, хеш-функция не вернет правильное значение хэша, и многие равные объекты будут не равны. Я думаю, что мы не можем иметь переменную функцию. Вы можете использовать константу, но если вы хотите использовать ее в качестве хеш-ключа в словаре или хеш-таблице, вы не получите сложности O (1).

Answer 5

Основная проблема с получением непостоянной хэш-функции заключается в том, что вы не можете обеспечить транзитивность по равенству. Обычно равенство считается транзитивным. То есть A = B и B = C означает, что A = C (что также подразумевает, что A, B и C будут иметь одинаковый хэш-код). Однако с вашим определением равенства вы могли бы иметь A = B, B = C и A! = C. В идеальном случае неравные элементы будут иметь разные хеш-коды, поэтому A и C будут иметь разные хэш-коды; но они не могут, потому что они оба равны B, поэтому они должны иметь один и тот же хэш-код.

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

Дело в том, что идея создания ящиков равенства состоит в том, что таких конфигураций может быть много. В качестве критерия выбора вы можете увеличить количество ящиков (чтобы улучшить производительность поиска в хэш-таблице). Дегенеративный случай (как указано в правильном ответе Рида Копси) состоит в том, что вы помещаете все в один и тот же ящик (хотя, как указывает суперкарт в комментариях ниже, название «ящики равенства» затем становится вводящим в заблуждение). Это не нарушает каких-либо ограничений хеш-значений, но это приведет к плохой производительности в алгоритмах, которые ожидают значения для создания негенеративного разбиения.

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

Answer 6

Видя, что ваша настоящая проблема связана с методом расширения, кроме того, Я решил предложить что-то для вас, хотя это и не совсем ответ.

public class EqualityComparer<T> : IEqualityComparer<T> 
{ 
    private readonly Func<T, T, bool> _comparer; 
    private readonly Func<T, int> _hashCoder; 

    public EqualityComparer(Func<T, T, bool> comparer, Func<T, int> hashCoder = null) 
    { 
     if (comparer == null) 
     { 
      throw new ArgumentNullException("comparer"); 
     } 

     this._comparer = comparer; 
     this._hashCoder = hashCoder ?? (x => 0); 
    } 

    public bool Equals(T x, T y) 
    { 
     return this._comparer(x, y); 
    } 

    public int GetHashCode(T obj) 
    { 
     return this._hashCoder(obj); 
    } 
} 

И тогда вы можете использовать его так:

arr1.Except(arr2, new EqualityComparer<dynamic>((x, y) => 
    { 
     if (ReferenceEquals(x, y)) 
      return true; 

     if (ReferenceEquals(x, null) || 
      ReferenceEquals(y, null)) 
      return false; 

     var matches = 0; 

     if (x.A == y.A) matches++; 
     if (x.B == y.B) matches++; 
     if (x.C == y.C) matches++; 

     return (matches > 1); 
    }));