Составной строковый ключ в HashMap - PullRequest
2 голосов
/ 04 октября 2009

Мы храним ключ String в HashMap, который является объединением трех полей String и логического поля. Проблема в том, что дубликаты ключей могут быть созданы, если в значении поля появляется разделитель.

Итак, чтобы обойти это, основываясь на совете в другой публикации, я планирую создать класс ключей, который будет использоваться в качестве ключа HashMap:

class TheKey {
  public final String k1;
  public final String k2;
  public final String k3;
  public final boolean k4;

  public TheKey(String k1, String k2, String k3, boolean k4) {
    this.k1 = k1; this.k2 = k2; this.k3 = k3; this.k4 = k4;
  }

  public boolean equals(Object o) {
      TheKey other = (TheKey) o;
      //return true if all four fields are equal
  }

  public int hashCode() {
    return ???;  
  }
}

Мои вопросы:

  1. Какое значение должно быть возвращено из hashCode (). Карта будет содержать в общей сложности около 30 значений. Из этих 30 существует около 10 различных значений k1 (некоторые записи имеют одинаковое значение k1).
  2. Чтобы сохранить этот класс ключей как ключ HashMap, нужно только переопределить методы equals () и hashCode ()? Что-нибудь еще требуется?

Ответы [ 9 ]

12 голосов
/ 04 октября 2009

Просто hashCode и equals должны быть в порядке. Хэш-код может выглядеть примерно так:

public int hashCode() {
  int hash = 17;
  hash = hash * 31 + k1.hashCode();
  hash = hash * 31 + k2.hashCode();
  hash = hash * 31 + k3.hashCode();
  hash = hash * 31 + k4 ? 0 : 1;
  return hash;
}

Это предполагает, что ни один из ключей не может быть нулевым, конечно. Обычно вы можете использовать 0 в качестве «логического» хеш-кода для нулевой ссылки в приведенном выше уравнении. Два полезных метода для составного равенства / хеш-кода, которые должны иметь дело с нулями:

public static boolean equals(Object o1, Object o2) {
  if (o1 == o2) {
    return true;
  }
  if (o1 == null || o2 == null) {
    return false;
  }
  return o1.equals(o2);
}

public static boolean hashCode(Object o) {
  return o == null ? 0 : o.hashCode();
}

Используя последний метод в алгоритме хеширования в начале этого ответа, вы получите что-то вроде:

public int hashCode() {
  int hash = 17;
  hash = hash * 31 + ObjectUtil.hashCode(k1);
  hash = hash * 31 + ObjectUtil.hashCode(k2);
  hash = hash * 31 + ObjectUtil.hashCode(k3);
  hash = hash * 31 + k4 ? 0 : 1;
  return hash;
}
10 голосов
/ 04 октября 2009

В Eclipse вы можете создать hashCode и равно Alt-Shift-S h.

2 голосов
/ 04 октября 2009

Вот так должен выглядеть правильно сформированный класс equals с equals и hashCode: (генерируется с идеей intellij, с включенными проверками нуля)

class TheKey {
public final String k1;
public final String k2;
public final String k3;
public final boolean k4;

public TheKey(String k1, String k2, String k3, boolean k4) {
    this.k1 = k1;
    this.k2 = k2;
    this.k3 = k3;
    this.k4 = k4;
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    TheKey theKey = (TheKey) o;

    if (k4 != theKey.k4) return false;
    if (k1 != null ? !k1.equals(theKey.k1) : theKey.k1 != null) return false;
    if (k2 != null ? !k2.equals(theKey.k2) : theKey.k2 != null) return false;
    if (k3 != null ? !k3.equals(theKey.k3) : theKey.k3 != null) return false;

    return true;
}

@Override
public int hashCode() {
    int result = k1 != null ? k1.hashCode() : 0;
    result = 31 * result + (k2 != null ? k2.hashCode() : 0);
    result = 31 * result + (k3 != null ? k3.hashCode() : 0);
    result = 31 * result + (k4 ? 1 : 0);
    return result;
}
}
2 голосов
/ 04 октября 2009

Попросите Eclipse 3.5 создать для вас хеш-код и методы equals:)

2 голосов
/ 04 октября 2009

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

  1. Если реализация хеш-кода идет медленно, рассмотрите возможность кэширования его в экземпляре. В зависимости от того, как долго остаются ваши ключевые объекты и как они используются с хэш-таблицей, когда вы получаете из нее что-то, вы можете не захотеть тратить больше времени, чем необходимо, вычисляя одно и то же значение снова и снова. Если вы придерживаетесь реализации Jon hashCode (), то, вероятно, в этом нет необходимости, поскольку String уже кеширует свой hashCode () для вас.
    Это, однако, скорее общий совет, так как с середины 90-х я видел, как довольно много разработчиков зацикливались на медленных (и еще хуже, меняющихся) реализациях hashCode ().

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

Правила просты, эта страница проведет вас через них.

Edit: Я должен спросить еще одну вещь ... Вы говорите: «Проблема в том, что дублирующие ключи могут быть созданы, если в значении поля появляется разделитель». Это почему? Если формат «ключ + разделитель + ключ + разделитель + ключ», то на самом деле не имеет значения, есть ли в ключах один или несколько разделителей, если вам не очень не повезло с комбинацией двух клавиш, и в этом случае вам, вероятно, следовало бы выбрать другую разделитель (в Юникоде есть из чего выбирать).

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

1 голос
/ 05 октября 2009

Я думал, что ваша основная проблема была в скорости (на основе вашего исходного поста)? Почему бы вам просто не убедиться, что вы используете разделитель, который не встречается в значениях вашего (handfull of) поля? Затем вы можете просто создать ключ String, используя конкатенацию, и покончить со всем этим фокус-фокусом «key-class». Пахнет как серьезная чрезмерная инженерия для меня.

1 голос
/ 04 октября 2009

Для хэш-кода вы можете использовать что-то вроде

k1.hashCode () ^ k2.hashCode () ^ k3.hashCode () ^ k4.hashCode ()

XOR сохраняет энтропию, и это включает хэш-код k4 гораздо лучше, чем предыдущие предложения. Наличие только одного бита информации из k4 означает, что если все ваши составные ключи имеют идентичные k1, k2, k3 и только разные k4s, все ваши хеш-коды будут идентичны, и вы получите вырожденный HashMap.

1 голос
/ 04 октября 2009

Я не знаю, подходит ли вам этот вариант, но библиотека Apache Commons предоставляет реализацию для MultiKeyMap

1 голос
/ 04 октября 2009

Вы смотрели на характеристики hashCode()? Возможно, это даст вам лучшее представление о том, что должна возвращать функция.

...