Umgang mit Karten, equals() und hashCodes(). Wie effizient ist das?

Question

Ich schreibe etwas, das eine ganze Reihe von Transaktionen pro Sekunde erhalten wird. Für jede Transaktion, die hereinkommt, wird auf eine Karte Bezug genommen, deren Schlüsselwerte die ID und eine Bean sind, die bei der Verarbeitung dieser bestimmten Transaktion helfen. Im Grunde kommt jede Transaktion mit einer ID, ein Nachschlagen wird an der Karte vorgenommen, um die entsprechende Bean zur Verarbeitung abzurufen. Der klebrige Teil kommt mit der Tatsache, dass die ID für jede Transaktion nicht genau mit der ID in der Karte übereinstimmen soll. Mehr von a beginnt mit der Operation. Zu diesem Zweck habe ich statt einer Zeichenfolge als ID ein einfaches Pojo namens MyId erstellt. Codes unten:

public class MyId 
{ 

    private static final int HASHCODE_CONSTANT = 1; 
    private String value; 

    public MyId(String value) 
    { 
     this.value = value; 
    } 

    @Override 
    public int hashCode() 
    { 
     //Returns the same hashcode value for all instances of this pojo 
     return HASHCODE_CONSTANT; 
    } 

    @Override 
    public boolean equals(Object obj) 
    { 
     //Checks for object type, forcibly casts and then compares the starts with 
     if(obj instanceof MyId) 
     { 
      if(!(obj == null || "".equals(obj))) 
      { 
       return this.value.startsWith(((MyId)obj).getValue()); 
      } 
     } 
     return false; 
    } 

    public String getValue() 
    { 
     return value; 
    } 

    public void setValue(String value) 
    { 
     this.value = value; 
    } 

    //Test 
    public static void main(String[] args) 
    { 
     Map map = new HashMap(); 
     map.put(new MyId("123456"), ""); 

     System.out.println("Result: " + map.containsKey(new MyId("12345677"))); 
     System.out.println("Result: " + map.containsKey(new MyId("11234567"))); 
    } 
} 

Der erste Test gibt True zurück und der zweite Test gibt false zurück, wie es sein sollte. Es scheint, dass die Methode map.containsKey() die Hashcode-Methode Ihres Objekts aufruft und vergleicht, bevor das equals() überhaupt aufgerufen wird. Wenn Ihre Hashes nicht übereinstimmen, werden Sie nicht einmal vergleichen. Während dies funktioniert, fühlt es sich ein wenig zweifelhaft an, die Hashcode-Methode auf diese Weise zu implementieren, um die Karte auszutricksen.

Ich frage mich, ob es einen effizienteren Weg gibt, dies zu tun. Wir sind Umgang mit einer ganzen Reihe von Transaktionen/Sekunde und damit eine ganze Reihe von Nachschlagen auf der Karte.

PS: Ich habe dieses Blind codiert, also bin ich sicher, dass es Syntaxfehler gibt. Bitte ignoriere diese. Ich versuche nur, die allgemeine Idee zu vermitteln.

Answer 1

Wenn hashCode() Methode einen konstanten Wert liefert alle Ihre Schlüssel zu den gleichen Eimern in den HashMap hash werden, effektiv Ihre HashMap Reduzieren eine verketteten Liste zu sein, mit der Zugriffszeit O (n) (anstelle O des Annäherns (1)).

Eine mögliche Lösung (nicht platzsparend): Für jeden String speichern mehrere Schlüssel entsprechend den möglichen String-Präferenzen, aber alle referenzieren den gleichen Wert. Zum Beispiel würden Sie für das Wort "Hallo" die Schlüssel "H", "He", "Hel", "Hell", "Hello" speichern. Dies würde natürlich mehr Speicherplatz verbrauchen, aber die Nachschlagezeit wäre sehr schnell und Sie müssten die Methode equals() der Klasse nicht verpfuschen, um einen "unscharfen" Vergleich durchzuführen. Sie könnten die Platzeffizienz verbessern, indem Sie eine benutzerdefinierte Klasse schreiben. z.B.

Answer 2

Ich denke, Sie zwingen zwei verschiedene Objekte, die gleiche Datenstruktur zu verwenden, und das macht Ihre Karte nicht so effizient.

Um eine bessere Lösung zu bieten, benötige ich möglicherweise weitere Informationen wie: Ist die ID in der Karte immer 6 Ziffern?

OK, dann können Sie zum Beispiel zwei Klassen erstellen.

public class MyIdMap { 

    private String value; 

    public MyIdMap(String value) { 
     this.value = value; 
    } 

    public String getValue() { 
     return value; 
    } 

    public void setValue(String value) { 
     this.value = value; 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((value == null) ? 0 : value.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
     return true; 
     if (obj == null) 
     return false; 
     if (getClass() != obj.getClass()) 
     return false; 
     MyIdMap other = (MyIdMap) obj; 
     if (value == null) { 
     if (other.value != null) 
      return false; 
     } else if (!value.equals(other.value)) 
     return false; 
     return true; 
    } 
} 


public class MyId { 

    private String value; 

    public MyId(String value) { 
     this.value = value; 
    } 

    public String getValue() { 
     return value; 
    } 

    public void setValue(String value) { 
     this.value = value; 
    } 

    public MyIdMap getMyIDMap() { 
     return new MyIdMap(value.substring(0, 6)); 
    } 
} 

Setzen Sie die MyIdMap in einer Karte, dann, wenn Sie es suchen, nur map.get verwenden (myId.getMyIdMap())

Answer 3

Warum Sie HashMap in einer solchen Art und Weise ineffizient verwenden Sie. Die gleiche Sache, die Sie mit TreeMap viel schneller bekommen können - es genau gemacht, was Sie wollen. Auch const in Hash-Code zeigt O (n) Leistung, während TreeMap gibt Ihnen ln (n).

Answer 4

dieses Objekt folgt nicht einmal the general contract of hashCode:

• Wenn zwei Objekte die Gleichen nach (Object) -Methode gleich sind, dann auf jeder der beiden Objekte die hashCode-Methode aufrufen müssen die gleiche ganze Zahl produzieren Ergebnis.

• Wenn zwei Objekte ungleich der Methode equals (java.lang.Object) sind, ist es nicht erforderlich, dass der Aufruf der Methode hashCode für jedes der beiden Objekte eindeutige ganzzahlige Ergebnisse liefert.

Allerdings sollte der Programmierer bewusst sein, dass verschiedene Integer-Ergebnisse für ungleiche Objekte produzieren, kann die Leistung von Hash-Tabellen verbessern.

Sie vielleicht Ihre Implementierung testen (ein Stub, immer eine konstante zurückgibt) und ein „normales“ Object, wie ein String. Bitte Test, Test, Test, denken, Test, Test, Test, ...

Answer 5

Wenn Ihr Komparator verwendet startsWith(), dann eine Hash-Karte ist die falsche Datenstruktur. Du benötigst etwas, wo du Schlüssel schnell durch ihre ersten Buchstaben finden kannst: Du brauchst eine Baumkarte.

Im Gegensatz zu einer Hash-Map ist eine Baumstruktur angeordnet. Anstatt also blind in einen mathematischen Raum mit merkwürdig verteilten Zahlen einzutauchen, können Sie mit der Suche an der Wurzel beginnen und die Leistung wird O (log (n)) sein. Das Hauptproblem bei der Java-Implementierung: Es ist geschlossen und gesperrt. Sie können es nicht wirklich auf die Suche mit erweitern.

In Ihrem Fall scheint die Anzahl der Transaktionsprozessoren stabil zu sein (was bedeutet, dass Sie nicht ständig neue anlegen). Wenn dies nicht der Fall ist, sollte die Anzahl der Prozessoren relativ klein sein (z. B. < 1000).

Mein Vorschlag ist, ein Array zu verwenden und alle Prozessoren in diesem Array zu setzen. Sortiere sie nach ihrer ID.

Jetzt können Sie Arrays.binarySearch(T[] a, T key, Comparator<? super T> c) verwenden, um Elemente mit dem Code von equals() im Komparator effizient nachzuschlagen.

Answer 6

Ihre equals() -Methode gehorcht nicht dem Vertrag von Object.equals() - es ist nicht transitiv. Es hätte "a" .equals ("ab") return true und "a" .equals ("ac") gibt true zurück, aber "ab" .equals ("ac") gibt false zurück.

Wenn Sie versuchen, Zeichenfolgenobjekte basierend auf Zeichenfolgenpräfixen zu speichern, möchten Sie möglicherweise eine Art von trie verwenden.

Answer 7

Ich glaube nicht, dass Hash-Tabellen eine gute Lösung sind. @Adamskis Idee, die Hashtabelle mit Präfixen zu laden, ist interessant, aber ich denke, dass es chaotisch wird, wenn Schlüssel Präfixe teilen oder wenn man Einträge on the fly einfügen/löschen muss.

Wenn Ihre Einträge in map/lookup table nicht geändert werden, ist die Verwendung eines vorsortierten Arrays und Arrays.binarySearch(...) (von @Aaron empfohlen) eine gute Lösung. Es sollte Ihnen O (log (N)) Lookup geben.

Wenn Sie jedoch im laufenden Betrieb Karteneinträge einfügen oder entfernen müssen, sind diese Operationen O (N) für eine Array-basierte Lösung. Stattdessen sollten Sie eine TreeMap verwenden und die Methoden in der NavigableMap-API verwenden, z. B. 'lowerKey() , floorKey() and higherKey() `, um die" nächste "Übereinstimmung in der Tabelle zu finden. Das sollte O (log (N)) zum Nachschlagen, Einfügen und Löschen geben.

Answer 8

Ok danke für die Eingabe fellas. Einer der größten Faktoren in der Problemstellung ist, dass die gespeicherten Schlüssel fast immer kürzer sind als der Vergleich. Zu diesem Zweck kam mit zwei unterschiedlichen Ansätzen auf, die die Problemstellung lösen nur für den Fall jemand eine Referenz muss, wenn sie sich über etwas ähnliches in der Zukunft kommen:

1. eine Karte verwenden, wie pro normal. Wenn der Eingabevergleich eingeht, vergleichen Sie. Wenn es keinen Treffer gibt, trimmen Sie die Zeichenfolge und vergleichen Sie erneut.

2. Dieser ist ein kleiner Züchter. Mir hat gefallen, was ich über Don Knuth's Trie gelesen habe (danke für den Ref Avi) und ich habe mir eine sehr einfache Implementierung ausgedacht. (Nur FYI, das Format der Ids wäre etwas wie 1.1.1.2. Das muss man beachten, damit der Beispielcode nicht zu komisch aussieht).

public class Trie { Privat HashMap Karte = new HashMap();

public Trie() 
{ 
} 

public Object get(String key) 
{ 
    return recurse(key.split("\\."), map, 0); 
} 

protected Object recurse(String[] key, Map map, int location) 
{ 
    Object value = map.get(key[location]); 
    if(value instanceof Map) 
     return recurse(key, (Map)value, location+1); 
    else 
     return value; 
} 

public void addKey(String key, Object value) 
{ 
    String[] keys = key.split("\\."); 
    addKey(keys, map, 0, value); 
} 

protected void addKey(String[] key, Map map, int location, Object value) 
{ 
    if((location+1) == key.length) 
    { 
     //end of the road. value insertion 
     map.put(key[location], value); 
    } 
    else 
    { 
     Map hashMap = (Map) map.get(key[location]); 
     if(!(map.containsKey(key[location]))) 
     { 
      hashMap = new HashMap(); 
      map.put(key[location], hashMap); 
     } 
     addKey(key, hashMap, location+1, value); 
    } 
} 

public static void main(String[] args) 
{ 
    Trie trie = new Trie(); 
    trie.addKey("1.1.2.1", "1.1.2.1"); 
    trie.addKey("1.1.2.2", "1.1.2.2"); 
    trie.addKey("1.1.2.3.1", "1.1.2.3.1"); 
    trie.addKey("1.1.2.3.2", "1.1.2.3.2"); 
    trie.addKey("1.1.2.4", "1.1.2.4"); 

    System.out.println(trie.get("1.1.2.1.0")); //returns 1.1.2.1 
    System.out.println(trie.get("1.1.2.3.1.0")); //returns 1.1.2.3.1 
    System.out.println(trie.get("1.1.2.4.1.0")); //returns 1.1.2.4 
} 

}

In meinem Anwendungsfall, ich erwarte nicht, die Trie mehr als 2-3 Stufen in der Tiefe wächst also, wenn Ihre Baumstruktur sehr komplex bekommt man Performance-Probleme analysieren möchte und Prüfen Sie, ob die zusätzlichen Suchvorgänge zu viel Aufwand verursachen. Oh und beide Ansätze erfordern keine dubiosen Änderungen am hashCode oder equals-Vertrag, da es sich nur um String-Objekte handelt.

Überlegungen:

auf nicht entschieden hat, die eine anhängige Verhaltensanalyse zu verwenden. Die Sache ist die meiste Zeit, die Vergleichswerte sind genau jene der in der Karte gespeicherten, so dass ein einfaches Nachschlagen ausreicht. Es ist nur die anderen "speziellen" Fälle, die berücksichtigt werden müssen. Zusammenfassend, wenn die besonderen Vorkommnisse dazu tendieren, sehr, sehr niederfrequent zu sein, würde ich versucht sein, den ersten Schritt zu gehen (# 1). Die große Mehrheit der Suchen wird schnell sein und wenn ein spezieller Fall hereinkommt, werde ich mit dem Schmerz der Stringmanipulation leben. Wenn das Gegenteil der Fall ist, könnte # 2 attraktiver sein.

PS: Kommentare begrüßen