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

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

11 голосов
/ 07 марта 2011

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

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 включает 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)));
}

Ответы [ 5 ]

19 голосов
/ 07 марта 2011

У Джона Скита есть это:

Какой наилучший алгоритм для переопределенного 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, вы можете позволить ему делать свое дело

6 голосов
/ 07 марта 2011

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

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

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

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

1 голос
/ 07 марта 2011

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

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

const SOME_LARGE_NUMBER = 100000; вернуть SOME_LARGE_NUMBER * x + y;

0 голосов
/ 08 января 2015

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

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

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

0 голосов
/ 07 марта 2011

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

...