суббота, 5 ноября 2011 г.

Компараторы для HashSet<>

Как я попробовал показать в предыдущем сообщении, стандартная реализация компаратора для HashSet<> содержит ошибку, которая состоит в том, что при сравнении элементов хешсета может использоваться внутренний компаратор хешсета, а при расчёте хешкода всегда используется стандартный (EqualityComparer<>.Default).

Настало время эту ошибку исправить. Вдаваясь в долгие и скучные объяснения с различными примерами можно показать, что одним методом без параметров для получения компаратора, как HashSet<>::CreateSetComparer(), нельзя вернуть универсальный компаратор на все случаи жизни. Поэтому придётся использовать два метода:

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

Вот эти методы (класс Comparers у меня содержит всякое безобразие для всевозможных компараторов, например, ещё это и это):

public static partial class Comparers
{
 public static EqualityComparer<HashSet<T>> HashSetComparer<T>() {
   return HashSetEqualityComparer<T>.Default;
 }

 public static EqualityComparer<HashSet<T>> HashSetCustomComparer<T>(IEqualityComparer<T> comparer = null) {
   return new HashSetCustomEqualityComparer<T>(comparer);
 }
}

Первый метод всегда возвращает один и тот же объект, так логика работы этого компаратора не зависит от каких либо внешних факторов. Второй метод возвращает компаратор, параметризованный другим компаратором, который будет использоваться для сравнения элементов хешсета, поэтому каждый раз создаётся новый объект. Рассмотрим устройство и особенности этих объектов.

Первый компаратор:

public static partial class Comparers
{
 [Serializable]
 private sealed class HashSetEqualityComparer<T> : EqualityComparer<HashSet<T>>
 {
   private const int MagicNumber = 13;

   static HashSetEqualityComparer() {
     Default = new HashSetEqualityComparer<T>();
   }

   public static new HashSetEqualityComparer<T> Default { get; private set; }

   public override bool Equals(HashSet<T> x, HashSet<T> y) {
     if(x == null) {
       return y == null;
     } else if(y == null) {
       return false;
     } else if(!Equals(x.Comparer, y.Comparer)) {
       return false;
     }//if

     return x.SetEquals(y);
   }

   public override int GetHashCode(HashSet<T> obj) {
     if(obj == null) {
       return 0;
     }//if

     return obj.Aggregate(0, (hash, item) =>
       hash ^ (obj.Comparer.GetHashCode(item) & 0x7FFFFFFF));
   }

   public override bool Equals(object obj) {
     return obj is HashSetEqualityComparer<T>;
   }

   public override int GetHashCode() {
     return MagicNumber;
   }
 }
}

Особенности:

  • Данный компаратор умеет сравнивать только хешсеты с одинаковыми компараторами, зато достаточно оптимально.
  • При вычислении хешкода для получения хешкода элемента хешсета используется внутренний компаратор хешсета.
  • Любые два экземпляра этого компаратора всегда равны между собой (а экземпляров может быть несколько, так как конструктор открытый). Вообще, реализация сравнения в компараторах - отдельная тема. Обратите внимание, что для сравнения компараторов здесь используется метод Object::Equals(object, object), а не оператор сравнения (как, например, в родной реализации компаратора).
  • MaficNumber, не равный нулю, используется из-за того, что равный нулю хешкод обычно возвращается для объектов, имеющих значение null.

Второй компаратор:

public static partial class Comparers
{
 [Serializable]
 private sealed class HashSetCustomEqualityComparer<T> : EqualityComparer<HashSet<T>>
 {
   public HashSetCustomEqualityComparer(IEqualityComparer<T> comparer = null) {
     Comparer = comparer ?? EqualityComparer<T>.Default;
   }

   private IEqualityComparer<T> Comparer { get; set; }

   public override bool Equals(HashSet<T> x, HashSet<T> y) {
     if(x == null) {
       return y == null;
     } else if(y == null) {
       return false;
     } else if(Equals(x.Comparer, y.Comparer) && Equals(x.Comparer, Comparer)) {
       return x.SetEquals(y);
     }//if

     var set = new HashSet<T>(x, Comparer);
     return set.SetEquals(y);
   }

   public override int GetHashCode(HashSet<T> obj) {
     if(obj == null) {
       return 0;
     }//if

     return obj.Aggregate(0, (hash, item) =>
       hash ^ (Comparer.GetHashCode(item) & 0x7FFFFFFF));
   }

   public override bool Equals(object obj) {
     var other = obj as HashSetCustomEqualityComparer<T>;
     return other != null && Equals(other.Comparer, Comparer);
   }

   public override int GetHashCode() {
     return Comparer.GetHashCode();
   }
 }
}

Особенности:

  • Если компараторы сравниваемых хешсетов эквивалентны как между собой, так и с внутренним компаратором, будет использован более оптимальный способ сравнения.
  • При вычислении хешкода для получения хешкода элемента хешсета используется собственный компаратор.

Конечно, можно было бы обойтись и одним методом и одним классом компаратора, но было бы больше проверок и ветвлений, поэтому я выбрал небольшое дублирование кода (реализация GetHashCode() у компараторов отличается только используемым внутри компаратором), но более простые классы.

В заключении надо сказать, что похожие проблемы есть и у компаратора, который стандартная библиотека предоставляет для SortedSet<>. Я, как мог, постарался описать их на форуме BCL (здесь) и узнал, что, оказывается, это всё by design, то есть "так и задумано". Хотя это может быть и ошибочным мнением. Отдельно на коннект сообщать об этой, второй, похожей проблеме нет желания - много писанины с заранее известным результатом. Буду надеяться, что справившись с опубликованной багой они просмотрят аналогичный код и приведут его в соответствие.