Требование сложности hashCode

Question

Я работаю над непреложным классом Board, который представляет собой плату N-by-N из 15 игра-головоломка (в случае N-by-N это будет игра N^2 - 1) , Я переопределены equals()(как показано ниже) и, следовательно, hashCode() метод для того, чтобы сохранить контракт Object, однако метод Hashcode, , который я хочу реализовать, занимает квадратичное время (он должен проверить все N^2 - 1 записей).

Так что мой вопрос: считается ли это плохой практикой, если hashCode не принимает постоянного времени, так как это может ухудшить производительность HashMap/ (что я не буду использовать в любом случае)? Должен ли я выбирать что-то более простое, например, каждый раз возвращать одно и то же простое, даже если оно увеличит вероятность столкновения?

Образец 3-на-3 совета (из метода ToString())

1 2 3 
4 5 6 
7 0 8 

Два Boards считаются равные IFF, все записи матча.

Отрывки кода из класса Board:

public class Board { 

    private final int[][] tilesCopy; // tiles 
    private final int N;    // size of the board 

... code... 


@Override 
    public boolean equals(Object y) { 
     if (!(y instanceof Board)) return false; 
     Board that = (Board) y; 
     if (this.size() != that.size()) return false; 

     for (int i = 0; i < this.size(); i++) { 
      for (int j = 0; j < this.size(); j++) { 
       if (this.tileAt(i, j) != that.tileAt(i, j)) return false; 
      } 
     } 
     return true; 
    } 

@Override 
public int hashCode() { 
    ...code... 
    } 

Answer 1

Хорошая практика должна быть как можно быстрее, от причин, о которых Вы упомянули. Но важнее для hashCode быть дискриминационным.

Совершенно очевидно, что когда у вас есть элементы N*N, хеш должен учитывать их все. Когда вы попытаетесь проигнорировать что-то, это приведет к большему количеству столкновений, которое для HashMaps и т. Д. Приведет к более чем звонящим equals вызовам, которые будут еще более дорогими (даже если вы можете быстро return false, когда вы найдете несоответствие, сумма equals будет асимптотически больше, чем вызовы hashCode).

Когда hashCode собирается назвать несколько раз на экземпляре, и дорого, чтобы вычислить, вы должны eveluate это только один раз, и кэша он для дальнейших вызовов (конечно, ваш объект должен быть неизменным, или вам придется аннулировать кешированный хэш-код при мутации объекта).

---

Обновление: как вдохновение, коллекции Java (Lists, Sets и т.д.) хэш-коды расчеты включают в себя цикл через все элементы тоже. Хотя было бы хорошо (с точки зрения контракта API) использовать только размер коллекции как хеш-код.

Update 2: Если вы не собираетесь использовать окрошка коллекции, вы можете реализовать return 0 хэш-код, так как он не будет использоваться в любом случае. Но вы должны реализовать его, если вы делитесь этой реализацией с кем-то другим, поскольку они могут захотеть поместить ее в такие коллекции.

Answer 2

Это не считается «плохой практикой». Хорошая или плохая практика действительно не влезает в нее.

Что вам действительно нужно учитывать, является ли это наилучшим решением. Есть ли способ вычислить хэш-код, который не O(N^2)? Вы собираетесь рассчитать эти хэш-коды достаточно часто, чтобы O(N^2) был значимым всего? Можете ли вы избежать (повторного) вычисления хэш-кода для того же состояния?

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

Например, функция XOR обладает свойством обратимости; т.е. если A XOR B является C, то C XOR B является A. Поэтому, если хэш-код состояния платы составлен из XOR хэша элементов, вы можете перейти от hashcode(state S) в hashcode(state S + 1) посредством XORing только в хэш-кодах для которые изменились.

Конечно, вам нужно кэшировать хэш-коды в объектах, представляющих состояния платы. Но если вы это сделаете, вы сможете вычислить хэш-код в O(1), а не O(N^2).