Конфликт Apache Commons Lang HashCodeBuilder

У меня конфликт с использованием Apache Commons Lang HashCodeBuilder с использованием версии 3.4. Я хеширую объект Route, который содержит два объекта Cell, начало и конец. В конце я привожу пример столкновения. Оба класса переопределяют методы hashCode и equals. Сначала класс Cell:

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

public class Cell {
    private int east;
    private int south;

    public Cell(int east, int south) {
        this.east = east;
        this.south = south;
    }

    public int getEast() {
        return east;
    }

    public void setEast(int east) {
        this.east = east;
    }

    public int getSouth() {
        return south;
    }

    public void setSouth(int south) {
        this.south = south;
    }

    @Override
    /**
     * Compute hash code by using Apache Commons Lang HashCodeBuilder.
     */
    public int hashCode() {
        return new HashCodeBuilder(17, 31)
                .append(this.south)
                .append(this.east)
                .toHashCode();
    }

    @Override
    /**
     * Compute equals by using Apache Commons Lang EqualsBuilder.
     */
    public boolean equals(Object obj) {
        if (!(obj instanceof Cell))
            return false;
        if (obj == this)
            return true;

        Cell cell = (Cell) obj;
        return new EqualsBuilder()
                .append(this.south, cell.south)
                .append(this.east, cell.east)
                .isEquals();
    }
}

И класс Route:

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

import java.util.*;

public class Route {
    private Cell startCell;
    private Cell endCell;

    public Route(Cell startCell, Cell endCell) {
        this.startCell = startCell;
        this.endCell = endCell;
    }

    public Cell getStartCell() {
        return startCell;
    }

    public void setStartCell(Cell startCell) {
        this.startCell = startCell;
    }

    public Cell getEndCell() {
        return endCell;
    }

    public void setEndCell(Cell endCell) {
        this.endCell = endCell;
    }


    @Override
    public int hashCode() {
        return new HashCodeBuilder(43, 59)
                .append(this.startCell)
                .append(this.endCell)
                .toHashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Route))
            return false;
        if (obj == this)
            return true;

        Route route = (Route) obj;
        return new EqualsBuilder()
                .append(this.startCell, route.startCell)
                .append(this.endCell, route.endCell)
                .isEquals();
    }
}

Пример столкновения:

public class Collision {
    public static void main(String[] args) {
        Route route1 = new Route(new Cell(154, 156), new Cell(154, 156));
        Route route2 = new Route(new Cell(153, 156), new Cell(151, 158));

        System.out.println(route1.hashCode() + " " + route2.hashCode());
    }
}

Вывод: 1429303 1429303. Теперь, если я изменю начальное нечетное число и нечетное число множителя одинаковыми для обоих классов, то этот пример не будет конфликтовать. Но в документации для HashCodeBuilder четко указано:

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

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


person Jernej Jerin    schedule 07.05.2015    source источник


Ответы (2)


Возможно, вы сможете более оптимально распределять сгенерированные хэш-коды, добавив дополнительные параметры при генерации хэш-кода (это не зависит от библиотеки Apache Commons). В этом примере вы можете предварительно вычислить одно или несколько свойств класса Route и использовать это свойство при генерации хэш-кода. Например, вычислите наклон линии между двумя Cell объектами:

double slope = (startCell.getEast() - endCell.getEast());
if ( slope == 0 ){//prevent division by 0
    slope = startCell.getSouth() - endCell.getSouth();
}else{
    slope = (startCell.getSouth() - endCell.getSouth()) / slope;
}

return new HashCodeBuilder(43, 59)
   .append(this.startCell)
   .append(this.endCell)
   .append(slope)
   .toHashCode();

Создает 83091911 83088489 с вашим примером. В качестве альтернативы (или вместе с) используйте расстояние между двумя Cell объектами:

double length = Math.sqrt(Math.pow(startCell.getSouth() - endCell.getSouth(), 2) + Math.pow(startCell.getEast() - endCell.getEast(), 2));
return new HashCodeBuilder(43, 59)
   .append(this.startCell)
   .append(this.endCell)
   .append(length)
   .toHashCode();

То, что используется только в вашем примере, дает 83091911 и -486891382.

И чтобы проверить, предотвращает ли это столкновение:

List<Cell> cells = new ArrayList<Cell>();
for ( int i = 0; i < 50; i++ ){
    for ( int j = 0; j < 50; j++ ){
        Cell c = new Cell(i,j);
        cells.add(c);

    }
}
System.out.println(cells.size() + " cells generated");
System.out.println("Testing " + (cells.size()*cells.size()) + " number of Routes");
Set<Integer> set = new HashSet<Integer>();
int collisions = 0;
for ( int i = 0; i < cells.size(); i++ ){
    for ( int j = 0; j < cells.size(); j++ ){
        Route r = new Route(cells.get(i), cells.get(j));
        if ( set.contains(r.hashCode() ) ){
            collisions++;
        }
        set.add(r.hashCode());
    }
}
System.out.println(collisions);

Из 6 250 000 сгенерированных маршрутов:

  1. Без длины и наклона: 6 155 919 столкновений.
  2. С длиной и наклоном: 873 047 столкновений.
person copeg    schedule 07.05.2015
comment
Интересное решение с добавлением дополнительных параметров, таких как уклон или расстояние. Но приводит ли добавление дополнительных параметров к снижению вероятности столкновения? - person Jernej Jerin; 07.05.2015
comment
But does adding more parameters result in lower probability in collision Да - см. Пример в отредактированном. (Как упоминалось в другом ответе, вы не можете устранить коллизии, но распределение можно улучшить, чтобы уменьшить их) - person copeg; 07.05.2015

В java хеш-код привязан к диапазону Integer (32-битный), поэтому это означает, что у вас будут коллизии, если у вас будет более 2 ^ 62 объектов (событие, если у вас идеальное распределение). Но на практике коллизия случается чаще из-за того, что хэш-код не обеспечивает идеального распределения.

person nkukhar    schedule 07.05.2015
comment
На практике вы, скорее всего, получите коллизию после того, как будут использованы 50% доступных хэш-кодов, потому что существует 50% -ная вероятность попадания в хэш, который уже был использован. - person rossum; 07.05.2015
comment
@rossum На самом деле столкновение произойдет намного раньше из-за парадокса дня рождения. - person ntysdd; 06.09.2017