Как эффективно хешировать двумерный массив (для хранения в HashSet)? - PullRequest
Новая
       7

Как эффективно хешировать двумерный массив (для хранения в HashSet)?

2 голосов
/ 23 октября 2010

Я написал класс под названием PuzzleBoard, представляющий доску nxn.Я буду хранить несколько объектов PuzzleBoard в HashSet, поэтому мне придется перезаписать метод int hashCode ().

Ниже приведены поля моего класса: 

 private int N;
 private int[][] puzzle;
 private int blankCellX;
 private int blankCellY;
 private int cost;

What Eclipseдля меня автоматически сгенерировано: 

 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + N;
  result = prime * result + blankCellX;
  result = prime * result + blankCellY;
  result = prime * result + cost;
  result = prime * result + Arrays.hashCode(puzzle);
  return result;
 }

Думая, что этот метод не учитывает содержимое 2-го массива, я изменил его на следующее: 

 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + N;
  result = prime * result + blankCellX;
  result = prime * result + blankCellY;
  result = prime * result + cost;
  for (int i = 0; i < N; ++i)
   result = prime * result + Arrays.hashCode(puzzle[i]);
  return result;
 }

Однакопроблема этого метода в том, что для его завершения требуется слишком много времени: O (N ^ 2) Кроме того;переменная 'result', скорее всего, переполнится.

Теперь мой вопрос: как мне написать эффективный метод хеширования, выполнение которого не займет слишком много времени.Более того;вставка или поиск объекта в HashSet должен быть эффективным (почти постоянным временем).

В худшем случае N будет равно 10, а HashSet будет содержать ~ 1000 PuzzleBoards.

Зачем я все это делаю? Я реализую решение проблемы N-Puzzle с помощью алгоритма A *.Таким образом, в некоторой фазе алгоритма, учитывая текущий узел (конфигурацию платы), я перемещаю пустую ячейку вверх, вниз, вправо или влево, чтобы сгенерировать новые дочерние узлы.Из-за этого конфигурации головоломки обычно отличаются на 1 или 2 ячейки.Я храню все исследованные узлы в HashSet.

Заранее спасибо =)

Ответы [ 2 ]

1 голос
/ 23 октября 2010

этот метод не учитывает содержимое 2-го массива

Вы также можете использовать util.Arrays#deepHashCode().

Однако проблема этого метода в том, что для его завершения требуется слишком много времени: O (N ^ 2)

Вы не можете идти быстрее, если хотите хэшировать все N ^ 2 целых в нем? Если N не больше 10, что в любом случае с обозначением Big-O? O(n^2) не значит медленный. Я не думаю, что ваш метод hashCode неэффективен. Неэффективность или некоторая O(n^2), скорее всего, где-то еще ... Тем не менее, если этот метод вызывается часто (и PuzzleBoard является неизменяемым), вы можете кэшировать значение hashCode.

переменная 'result' может быть переполнена.

Нет проблем! Переполнения определены в Java.

* * 1 022 Кроме того, вставка или поиск объекта в HashSet должен быть эффективным (почти постоянным временем).

Вставка, скорее всего, только амортизируется постоянное время. Когда HashSet заполнится, будет создан новый более крупный HashSet. В него копируются все элементы, все хеш-коды должны быть рассчитаны заново. Попробуйте установить initialCapacity для HashSet? 

result = prime * result + cost;

Вы уверены, что хотите, чтобы стоимость (я предполагаю, что это глубина) была включена в equals и hashCode? Две конфигурации одинаковы, независимо от того, сколько шагов мне понадобилось, чтобы добраться туда, верно?

~ 1000 PuzzleBoards

Если я правильно помню, в прошлый раз, когда я решил эту головоломку, у меня было много более 1000 конфигураций.

1 голос
/ 23 октября 2010

Хеш-коды не нужны , чтобы быть уникальными, просто лучше, если они есть. Поскольку у вас есть относительно небольшое количество элементов в HashSet (~ 1000), вы можете выбрать небольшое количество подходящих данных для хеширования. Например, может быть, вам нужен только первый ряд таблицы «головоломки», или, возможно, переменная «стоимость» достаточно различна для разных случаев, и вы можете использовать ее как хороший источник различий.

Не имеет значения, если результат переполнен: все, что вам нужно, это чтобы разные объекты возвращали разные хеш-коды, если это возможно. Фактическое значение хеша не имеет значения.

...