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

Question

У меня есть простой пользовательский класс 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();
    }

}

Answer 1

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

Как говорится, вот что предлагает Netbeans 7.1:

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

Октябрь 2015Edit

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

@Override
public int hashCode() {
    int result = x;
    result = 31 * result + y;
    return result;
}

Answer 2

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

import java.util.Objects;

...

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

..., либо в библиотеке Guava :

import com.google.common.base.Objects;

....

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

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

И удобочитаемость просто великолепна, поскольку вы просто видите, какие поля используются для вычисления хеш-кода, а весь синтаксис умножения и сложения просто скрыт под капотом 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;
}

Answer 3

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

return 37 * x + y;

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

int result = 373; // Constant can vary, but should be prime
result = 37 * result + x;
result = 37 * result + y;

Answer 4

Действительно хороший способ хэширования 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), однако)

Answer 5

По умолчанию 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 поможет с его «уникальностью».

Answer 6

Вы можете взглянуть на существующие реализации классов типов 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     }

from: http://kickjava.com/src/java/awt/geom/Point2D.java.htm#ixzz1lMCZCCZw

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

Answer 7

Из класса 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)));
}

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

Answer 8

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

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