Java hashCode для класса Point

У меня есть простой пользовательский класс Point, как показано ниже, и я хотел бы знать, можно ли улучшить мою реализацию hashCode или это лучшее, что она получит.

public class Point 
{
    private final int x, y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public int getX() 
    {
        return x;
    }

    public int getY()
    {
        return y;
    }

    @Override
    public boolean equals(Object other) 
    {
        if (this == other)
          return true;

        if (!(other instanceof Point))
          return false;

        Point otherPoint = (Point) other;
        return otherPoint.x == x && otherPoint.y == y;
    }


    @Override
    public int hashCode()
    {
        return (Integer.toString(x) + "," + Integer.toString(y)).hashCode();
    }

}
Источник

8 ответов

Решение

Пожалуйста, не используйте строки. За этим стоит множество теорий и несколько реализаций (метод деления, умножение и т. Д.). Если у вас есть около часа, вы можете посмотреть этот MIT-класс

При этом Netbeans 7.1 предлагает следующее:

@Override
public int hashCode() {
    int hash = 7;
    hash = 71 * hash + this.x;
    hash = 71 * hash + this.y;
    return hash;
}

Октябрь 2015 г. Править

Я начал использовать IntelliJ некоторое время назад, теперь я живу счастливее. Это то, что производит его автоматическая генерация hashCode. Это немного менее многословно. Обратите внимание на использование простых чисел.

@Override
public int hashCode() {
    int result = x;
    result = 31 * result + y;
    return result;
}
Источник

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

import java.util.Objects;

...

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

... или в библиотеке гуавы:

import com.google.common.base.Objects;

....

@Override
public int hashCode() {
    return Objects.hashCode(x, y);
}

Оба эти метода varags просто делегируют Arrays.hashCode (Object [] a), так что это оказывает небольшое влияние на производительность из-за автобокса целых и создания массива ссылок на объекты, но это должно быть гораздо менее значительным, чем использование отражения,

И читаемость просто великолепна, поскольку вы просто видите, какие поля используются для вычисления хеш-кода, а весь синтаксис умножения и сложения просто скрыт под капотом Arrays.hashCode(Object[] a):

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}
Источник

Я бы порекомендовал использовать более простой и более производительный метод без строк, возможно, метод Джоша Блоха из этого ответа, в вашем случае просто:

return 37 * x + y;

РЕДАКТИРОВАТЬ: nybbler правильно. Что на самом деле рекомендуется:

int result = 373; // Constant can vary, but should be prime
result = 37 * result + x;
result = 37 * result + y;
Источник

Действительно хороший способ хэширования 2D-точки в одно целое число - это использовать числовую спираль!

http://ulamspiral.com/images/IntegerSpiral.gif

@Override
public int hashCode() {
    int ax = Math.abs(x);
    int ay = Math.abs(y);
    if (ax>ay && x>0) return 4*x*x-3*x+y+1;
    if (ax>ay && x<=0) return 4*x*x-x-y+1;
    if (ax<=ay && y>0) return 4*y*y-y-x+1;
    return 4*y*y-3*y+x+1;
}

Хотя этот метод требует еще нескольких вычислений, непредсказуемых коллизий не будет. Он также имеет свойство nice, которое указывает, что точки ближе к источнику в общем случае будут иметь меньшее значение хеш-функции. (Тем не менее, может переполниться с x или y > sqrt(MAX_VALUE), однако)

Источник

Раньше я писал свои собственные хэш-функции и функции равенства, потом я нашел это:)

import org.apache.commons.lang.builder.HashCodeBuilder;
import org.apache.commons.lang.builder.EqualsBuilder;

@Override
public boolean equals(Object obj) {
   return EqualsBuilder.reflectionEquals(this, obj);
 }
@Override
public int hashCode() {
   return HashCodeBuilder.reflectionHashCode(this);
 }

конечно, имейте в виду следующее:

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

Источник

Вы можете взглянуть на существующие реализации классов типов Point:

/**
343      * Returns the hashcode for this <code>Point2D</code>.
344      * @return a hash code for this <code>Point2D</code>.
345      */
346     public int hashCode() {
347     long bits = java.lang.Double.doubleToLongBits(getX());
348     bits ^= java.lang.Double.doubleToLongBits(getY()) * 31;
349     return (((int) bits) ^ ((int) (bits >> 32)));
350     }

от: http://kickjava.com/src/java/awt/geom/Point2D.java.htm

Простое руководство по реализации hashCode можно найти здесь

Источник

Из класса Point JDK (унаследованного от Point2d):

public int hashCode() {
    long bits = java.lang.Double.doubleToLongBits(getX());
    bits ^= java.lang.Double.doubleToLongBits(getY()) * 31;
    return (((int) bits) ^ ((int) (bits >> 32)));
}

Это выглядит немного лучше, чем ваша реализация.

Источник

По умолчанию Eclipse будет использовать функцию hashCode() для вашего класса Point, например:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + getOuterType().hashCode();
    result = prime * result + x;
    result = prime * result + y;
    return result;
}

По крайней мере, включение простого числа в ваш алгоритм hashCode поможет с его "уникальностью".

Источник
Другие вопросы по тегам