среда, 28 сентября 2011 г.

Баг в реализации HashSet<>::CreateSetComparer()

Не правильно работает компаратор, возвращаемый методом CreateSetComparer класса HashSet<>. Пример кода, демонстрирующий ошибку:

using System;
using System.Collections.Generic;
using System.Diagnostics;

internal sealed class MyItem
{
  public MyItem(int number, string text) {
    Number = number;
    Text = text ?? String.Empty;
  }

  public int Number { get; private set; }
  public string Text { get; private set; }
}

internal sealed class MyItemComparer : EqualityComparer<MyItem>
{
  public override bool Equals(MyItem x, MyItem y) {
    if(x == null) {
      return y == null;
    } else if(y == null) {
      return false;
    } else {
      return EqualityComparer<int>.Default.Equals(x.Number, y.Number);
    }//if
  }

  public override int GetHashCode(MyItem obj) {
    if(obj == null) {
      return 0;
    }//if

    return EqualityComparer<int>.Default.GetHashCode(obj.Number);
  }
}

internal static class Program
{
  private static void Main() {
    var itemComparer = new MyItemComparer();

    var set1 = new HashSet<MyItem>(itemComparer) { new MyItem(1, "One"), };
    var set2 = new HashSet<MyItem>(itemComparer) { new MyItem(1, "1"), };

    var test = set1.SetEquals(set2);
    Debug.Assert(test); // OK

    var setComparer = HashSet<MyItem>.CreateSetComparer();
    var equals = setComparer.Equals(set1, set2);
    Debug.Assert(equals); // OK

    var hash1 = setComparer.GetHashCode(set1);
    var hash2 = setComparer.GetHashCode(set2);
    Debug.Assert(hash1 == hash2, "hash1 == hash2"); // Failed
  }
}


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

Для решения моей проблемы будет достаточным написать свой аналог компаратора, в который можно будет передать кастомный компаратор элементов.

Update: Желающие могут проголосовать за этот баг на коннекте.

2 комментария:

  1. m.connect>We will consider adding an overload in the future that has different semantics.

    Интересно, на что это будет похоже :)

    ОтветитьУдалить
  2. На самом деле там всего лишь два варианта (а даже не один как сейчас) этой самой семантики, скоро их опишу. Предложенная реализация воркэраунда так же лишь половинчатое решение (в некоторых случаях можно сделать пооптимальнее).

    Кстати, с компаратором в СортедСет тоже не сложилось :о) http://social.msdn.microsoft.com/Forums/en-US/netfxbcl/thread/6826304a-eda9-4af8-bd60-6db03b89e41e

    ОтветитьУдалить