Что является подходящим алгоритмом GetHashCode() для двумерной точечной структуры (избегая столкновений)

Рассмотрим следующий код:

struct Vec2 : IEquatable<Vec2>
{
    double X,Y;

    public bool Equals(Vec2 other)
    {
        return X.Equals(other.X) && Y.Equals(other.Y);
    }

    public override bool Equals(object obj)
    {
        if (obj is Vec2)
        {
            return Equals((Vec2)obj);
        }
        return false;
    }

    // this will return the same value when X, Y are swapped
    public override int GetHashCode()
    {
        return X.GetHashCode() ^ Y.GetHashCode();
    }

}

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

Vec2 A = new Vec2() { X=1, Y=5 };
Vec2 B = new Vec2() { X=5, Y=1 };

bool test1 = A.Equals(B);  // returns false;
bool test2 = A.GetHashCode() == B.GetHashCode() // returns true !!!!!

который должен разрушить хаос в коллекции словарей. Поэтому вопрос заключается в том, как свойство формирует функцию GetHashCode() для 2,3 или даже 4 значений с плавающей запятой, так что результаты не симметричны, а хеши не сталкиваются.

Изменить 1:

Point реализует неподходящее решение x ^ y и PointF wraps ValueType.GetHashCode().

Rectangle имеет очень своеобразное выражение (((X ^ ((Y << 13) | (Y >> 19))) ^ ((Width << 26) | (Width >> 6))) ^ ((Height << 7) | (Height >> 25))) для хеш-кода, который, как представляется, выполняет, как ожидалось.

Изменить 2:

"System.Double" имеет приятную реализацию, так как не учитывает каждый бит одинаково важный

public override unsafe int GetHashCode() //from System.Double
{
    double num = this;
    if (num == 0.0)
    {
        return 0;
    }
    long num2 = *((long*) &num);
    return (((int) num2) ^ ((int) (num2 >> 32)));
}

Ответы

Ответ 1

Джон skeet получил это:

Каков наилучший алгоритм для переопределенного System.Object.GetHashCode?

   public override int GetHashCode()
   {
       unchecked // Overflow is fine, just wrap
       {
           int hash = 17;
           // Suitable nullity checks etc, of course :)
           hash = hash * 23 + X.GetHashCode();
           hash = hash * 23 + Y.GetHashCode();
           return hash;
       }
   }

~~Кроме того, измените реализацию Equals(object) на:~~

return Equals(obj as FVector2);

Обратите внимание, однако, что это может воспринимать производный тип равным. Если вы этого не хотите, вам придется сравнивать тип времени выполнения other.GetType() с typeof(FVector2) (и не забывать проверки недействительности) Спасибо за указание на структуру, LukH

У Resharper есть хорошая генерация кода для равенства и хеш-кода, поэтому, если у вас есть resharper, вы можете позволить этому сделать свою вещь

Ответ 2

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

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

Обратите внимание, что реализовать Vec2 невозможно без столкновений - возможны только 2 ³² возможные значения возврата из GetHashCode, но есть более вероятные значения X и Y, даже после удаления NaN и бесконечных значений...

Эрик Липперт имеет последнее сообщение в блоге в GetHashCode, которое может показаться вам полезным.

Ответ 3

Каковы разумные оценки для координат?

Если это не могут быть все возможные целые значения, вы можете просто:

const SOME_LARGE_NUMBER = 100000; return SOME_LARGE_NUMBER * x + y;

Ответ 4

Если размер вашего хеш-кода меньше размера вашей структуры, тогда столкновения неизбежны в любом случае.

Ответ 5

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

Сортированная последовательность - это сбалансированное двоичное дерево с листовой версией.

Здесь ключи будут координатами точки.