Wandelbar hashmap keys eine gefährliche Praxis?

Ist es schlechte Praxis zu verwenden veränderliche Objekte als Hashmap keys? Was passiert, wenn Sie versuchen zum abrufen eines Wertes aus einer Hashmap mit einem Schlüssel, der geändert wurde, genug zu ändern, seinen hashcode?

Beispielsweise gegeben

class Key
{
    int a; //mutable field
    int b; //mutable field

    public int hashcode()
        return foo(a, b);
    //setters setA and setB omitted for brevity
}

mit code

HashMap<Key, Value> map = new HashMap<Key, Value>();

Key key1 = new Key(0, 0);
map.put(key1, value1); //value1 is an instance of Value

key1.setA(5);
key1.setB(10);

Was passiert, wenn wir jetzt rufen map.get(key1)? Ist dies sicher oder ratsam? Oder ist das Verhalten abhängig von der Sprache?

InformationsquelleAutor donnyton | 2011-10-20

  1. 69

    Es wurde von vielen bemerkt ANGESEHENE Entwickler wie Brian Goetz und Josh Bloch :

    Wenn ein Objekt die hashCode () - Wert ändern können, basierend auf Ihren Zustand, dann wir
    müssen vorsichtig sein bei der Verwendung solcher Objekte als Schlüssel in hash-basierten
    Sammlungen, um sicherzustellen, dass wir uns nicht erlauben, Ihren Zustand zu ändern, wenn
    Sie werden als hash-Schlüssel. Alle hash-basierten Sammlungen übernehmen
    dass ein Objekt der hash-Wert nicht ändern, während es in Gebrauch als
    key in die collection. Wenn eine key-hash-code zu ändern, während es
    war in einer Sammlung, einige unberechenbar und verwirrend Folgen
    Folgen könnten. Dies ist in der Regel nicht ein problem in der Praxis ist es nicht
    üblich ein veränderliches Objekt wie eine Liste, die als Schlüssel in einer
    HashMap.

    Kannst du die Quelle?
    Wahrscheinlichste Quelle: Aus der Serie "Java-Theorie und Praxis" - Hashing es von Brian Goetz, May 27, 2003

    InformationsquelleAutor aleroot

  2. 21

    Dies ist nicht sicher oder ratsam ist. Der Wert zugeordnet, indem key1 nie abgerufen werden können. Wenn Sie einen Abruf, die meisten hash-maps etwas wie

    Object get(Object key) {
    int hash = key.hashCode();
    //simplified, ignores hash collisions,
    Entry entry = getEntry(hash);
    if(entry != null && entry.getKey().equals(key)) {
        return entry.getValue();
    }
    return null;
}

    In diesem Beispiel, key1.hashcode() verweist nun auf die falsche bucket der Hashtabelle, und Sie werden nicht in der Lage zum abrufen von Wert1 mit key1.

    Wenn Sie hatte etwas getan, wie,

    Key key1 = new Key(0, 0);
map.put(key1, value1);
key1.setA(5);
Key key2 = new Key(0, 0);
map.get(key2);

    Wird diese auch nicht abrufen, Wert1, als key1 und key2 sind nicht mehr gleich, so dass diese Prüfung

        if(entry != null && entry.getKey().equals(key))

    fehl.

    InformationsquelleAutor sbridges

  3. 5

    Wird dies nicht funktionieren. Ändern Sie den Wert des Schlüssels, so sind Sie im Grunde werfen es Weg. Es ist wie ein echtes Leben von Schlüssel und Schloss, und dann ändern Sie den Schlüssel und versuchen, es wieder zurück in das Schloss.

    InformationsquelleAutor onit

  4. 5

    Hash-maps verwenden hash-code und Vergleiche auf Gleichheit zu identifizieren, die ein bestimmtes Schlüssel-Wert-paar mit einem bestimmten Schlüssel. Wenn die Karte hält, der Schlüssel als Hinweis auf das veränderliche Objekt, es in den Fällen, in denen die gleiche Instanz wird verwendet, um den Wert abzurufen. Bedenken Sie jedoch, folgenden Fall: 

    T keyOne = ...;
T keyTwo = ...;

//At this point keyOne and keyTwo are different instances and 
//keyOne.equals(keyTwo) is true.

HashMap myMap = new HashMap();

myMap.push(keyOne, "Hello");

String s1 = (String) myMap.get(keyOne); //s1 is "Hello"
String s2 = (String) myMap.get(keyTwo); //s2 is "Hello" 
                                        //because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap.get(keyOne); //returns "Hello"
s2 = myMap.get(keyTwo); //not found

    Den oben genannten ist wahr, wenn der Schlüssel gespeichert ist, als eine Referenz. In Java-in der Regel ist dies der Fall. In .NET zum Beispiel, wenn der Schlüssel einen Wert geben (immer durch Wert übergeben), wird das Ergebnis anders sein wird:

    T keyOne = ...;
T keyTwo = ...;

//At this point keyOne and keyTwo are different instances 
//and keyOne.equals(keyTwo) is true.

Dictionary myMap = new Dictionary();

myMap.Add(keyOne, "Hello");

String s1 = (String) myMap[keyOne]; //s1 is "Hello"
String s2 = (String) myMap[keyTwo]; //s2 is "Hello"
                                    //because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap[keyOne]; //not found
s2 = myMap[keyTwo]; //returns "Hello"

    Andere Technologien vielleicht haben andere unterschiedliche Verhaltensweisen. Allerdings, fast alle von Ihnen kommen würde, zu einer situation, wo das Ergebnis mit mutable keys ist nicht deterministisch, das ist sehr sehr schlechte situation, die in einer Anwendung - eine schwer zu Debuggen und noch schwerer zu verstehen.

    InformationsquelleAutor Ivaylo Slavov

  5. 4

    Wenn key hash-code änderungen, die nach dem Schlüssel-Wert-paar (Eintrag) gespeichert ist, in HashMap, die Karte wird nicht in der Lage zum abrufen der Eintrag.

    Schlüssel hashcode ändern kann, wenn das key-Objekt ist veränderlich. Mutable keys in HahsMap kann zu Datenverlust führen.

    InformationsquelleAutor Vishal

  6. 2

    Als andere erklärt, es ist gefährlich.

    Einen Weg, um zu vermeiden, dass ein const-Feld geben Sie explizit den Hashwert in Ihre veränderliche Objekte (also Sie würden hash Sie auf Ihrer "Identität", nicht Ihren "Staat"). Man könnte sogar initialisieren, hash-Feld mehr oder weniger zufällig.

    Ein weiterer trick wäre, um die Adresse ein, z.B. (intptr_t) reinterpret_cast<void*>(this) als Grundlage für die hash.

    In allen Fällen, Sie müssen aufgeben, hashing den wechselnden Zustand des Objekts.

    Vorausgesetzt, dieser ist Java, die von code-snippets für Programmierer kann sicher verlassen sich auf das systemeigene Objekt.hashcode(). Es darf erzeugen ein int-Wert mit Sitz in Ordnung, oder andere einfache, nicht veränderlich und einzigartigen Wert.

    InformationsquelleAutor Basile Starynkevitch

  7. 0

    Verhalten der Karte nicht angegeben, wenn der Wert eines Objektes wird geändert, in einer Art und Weise betrifft, entspricht Vergleich beim Objekt(Veränderlich) ist ein Schlüssel. Auch für die Set mit veränderlichen Objekt als Schlüssel ist nicht eine gute Idee.

    Können sehen, ein Beispiel hier :

    public class MapKeyShouldntBeMutable {

/**
 * @param args
 */
public static void main(String[] args) {
    //TODO Auto-generated method stub
    Map<Employee,Integer> map=new HashMap<Employee,Integer>();

    Employee e=new Employee();
    Employee e1=new Employee();
    Employee e2=new Employee();
    Employee e3=new Employee();
    Employee e4=new Employee();
    e.setName("one");
    e1.setName("one");
    e2.setName("three");
    e3.setName("four");
    e4.setName("five");
    map.put(e, 24);
    map.put(e1, 25);
    map.put(e2, 26);
    map.put(e3, 27);
    map.put(e4, 28);
    e2.setName("one");
    System.out.println(" is e equals e1 "+e.equals(e1));
    System.out.println(map);
    for(Employee s:map.keySet())
    {
        System.out.println("key : "+s.getName()+":value : "+map.get(s));
    }
}

  }
 class Employee{
String name;

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}

@Override
public boolean equals(Object o){
    Employee e=(Employee)o;
    if(this.name.equalsIgnoreCase(e.getName()))
            {
        return true;
            }
    return false;

}

public int hashCode() {
    int sum=0;
    if(this.name!=null)
    {
    for(int i=0;i<this.name.toCharArray().length;i++)
    {
        sum=sum+(int)this.name.toCharArray()[i];
    }
    /*System.out.println("name :"+this.name+" code : "+sum);*/
    }
    return sum;

}

}

    Hier versuchen wir hinzufügen veränderliche Objekt "Mitarbeiter" auf eine Karte. Es funktioniert gut, wenn alle Tasten Hinzugefügt werden, unterscheiden.Hier habe ich überschriebenen equals und hashcode für die Mitarbeiter-Klasse.

    Sehen ersten habe ich Hinzugefügt, "e" und dann "e1". Für beide von Ihnen, equals() true und hashcode gleich. Also map sieht aus, als wenn der gleiche Schlüssel ist, Hinzugefügt, so dass Sie ersetzt werden soll der alte Wert bei e1 Wert. Dann haben wir Hinzugefügt, e2,e3,e4, wir sind in Ordnung jetzt.

    Aber wenn wir ändern den Wert eines bereits hinzugefügten Schlüssel ich.e "e2", es wird ein Schlüssel (ähnlich einer zuvor Hinzugefügt haben. Jetzt ist die Karte verhält sich WLAN. Idealerweise e2 ersetzen Sie den vorhandenen gleichen key hab ich.e e1.Aber jetzt Karte nimmt diese als gut. Und Sie erhalten diese in o/p :

     is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@142=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : one:value : 25

    Sehen, hier sind beide Schlüssel mit einer mit demselben Wert auch. So seine unerwartete.Nun führen Sie das gleiche Programm noch einmal durch ändern e2.setName("diffnt"); die e2.setName("one"); hier ...Nun die o/p wird so sein :

     is e equals e1 true
{Employee@1aa=28, Employee@1bc=27, Employee@142=25, Employee@27b=26}
key : five:value : 28
key : four:value : 27
key : one:value : 25
key : diffnt:value : null

    Also durch hinzufügen ändern des veränderlichen Schlüssels in einer map ist nicht zu empfehlen.

    InformationsquelleAutor smruti ranjan

Schreibe einen Kommentar