Zusammengesetzter String-Schlüssel in HashMap

Question

Wir speichern einen String-Schlüssel in einer HashMap, die eine Verkettung von drei String-Feldern und einem booleschen Feld ist. Das Problem ist, dass doppelte Schlüssel erstellt werden können, wenn das Trennzeichen im Feldwert erscheint.

Um dies zu umgehen, wurde auf der Grundlage der Ratschläge in eine andere Post, ich plane, eine Schlüsselklasse zu erstellen, die als HashMap-Schlüssel verwendet werden soll:

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 ???;  
  }
}

Meine Fragen sind:

1. Welcher Wert von hashCode() zurückgegeben werden soll. Die Map wird insgesamt etwa 30 Werte enthalten. Von diesen 30 gibt es etwa 10 verschiedene Werte von k1 (einige Einträge haben denselben k1-Wert).
2. Um diese Schlüsselklasse als HashMap-Schlüssel zu speichern, muss man nur die Methoden equals() und hashCode() überschreiben? Ist noch etwas anderes erforderlich?

Answer 1

Nur hashCode und equals sollten ausreichen. Der HashCode könnte etwa so aussehen:

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;
}

Das setzt natürlich voraus, dass keiner der Schlüssel ungültig sein kann. Normalerweise könnte man 0 als "logischen" Hash-Code für eine Null-Referenz in der obigen Gleichung verwenden. Zwei nützliche Methoden für zusammengesetzten Gleichheits-/Hash-Code, der mit Nullen umgehen muss:

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();
}

Wenn Sie die letztgenannte Methode im Hash-Algorithmus am Anfang dieser Antwort verwenden, erhalten Sie etwa folgendes Ergebnis:

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;
}

Answer 2

In Eclipse können Sie HashCode und Equals mit Alt-Shift-S h erzeugen.

Answer 3

Die Implementierung Ihres hashCode() spielt keine große Rolle, es sei denn, Sie machen es super dumm. Sie könnten sehr gut einfach die Summe aller Strings Hash-Codes (abgeschnitten, um eine int) zurückgeben, aber Sie sollten sicherstellen, dass Sie dies beheben:

1. Wenn Ihre Hash-Code-Implementierung langsam ist, sollten Sie sie in der Instanz zwischenspeichern. Je nachdem, wie lange Ihre Schlüsselobjekte bleiben und wie sie mit der Hash-Tabelle verwendet werden, wenn Sie Dinge aus ihr herausholen, möchten Sie vielleicht nicht länger als nötig damit verbringen, den gleichen Wert immer wieder zu berechnen. Wenn Sie mit Jons Implementierung von hashCode() bleiben, gibt es wahrscheinlich keine Notwendigkeit für sie als String bereits Cache seine hashCode() für Sie.
   Dies ist jedoch eher ein allgemeiner Ratschlag, da ich seit Mitte der 90er Jahre gesehen habe, wie viele Entwickler durch langsame (und, was noch schlimmer ist, sich ändernde) hashCode()-Implementierungen gestochen wurden.

2. Seien Sie nicht schlampig, wenn Sie die equals()-Implementierung erstellen. Ihr equals() oben wird sowohl ineffektiv als auch fehlerhaft sein. Zunächst einmal brauchen Sie die Werte nicht zu vergleichen, wenn die Objekte unterschiedliche Hash-Codes haben. Außerdem sollten Sie false zurückgeben (und nicht eine Nullpointer-Exception), wenn Sie ein null als Argument erhalten.

Die Regeln sind einfach, diese Seite wird Sie durch diese führen.

Bearbeiten: Ich muss noch eine Frage stellen... Sie sagen: "Das Problem ist, dass doppelte Schlüssel erstellt werden können, wenn das Trennzeichen im Feldwert erscheint". Warum ist das so? Wenn das Format Schlüssel+Begrenzungszeichen+Schlüssel+Begrenzungszeichen+Schlüssel ist, spielt es eigentlich keine Rolle, ob ein oder mehrere Begrenzungszeichen in den Schlüsseln vorkommen, es sei denn, Sie haben wirklich Pech mit einer Kombination aus zwei Schlüsseln und in diesem Fall hätten Sie wahrscheinlich ein anderes Begrenzungszeichen wählen sollen (im Unicode gibt es eine ganze Reihe von Begrenzungszeichen zur Auswahl).

Wie auch immer, Jon hat in seinem Kommentar unten recht... Führen Sie kein Caching durch, "bis Sie bewiesen haben, dass es eine gute Sache ist". Es ist immer eine gute Praxis.

Answer 4

Bitten Sie Eclipse 3.5, die Hashcode- und Gleichheitsmethoden für Sie zu erstellen :)

Answer 5

So sollte eine wohlgeformte equals-Klasse mit equals und hashCode aussehen: (erzeugt mit intellij idea, mit aktivierter Nullprüfung)

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;
}
}