HashMap Cluster?

[Steve222]

Guten Tag,

mit HashMaps würde ich mich gerne besser auskennen. Vielleicht klärt mich jemand auf.
Schon jetzt vielen Dank dafür.

Laut API Doku besteht eine HashMap aus key-value Paaren, was (wohl) eindeutig jeweils ZWEI "Teile" sind.
Wenn in der Klasse Tag equals() und auch hashCode überschrieben wird, dann
ist die mit size() geprüfte Anzahl der key-value Paare geringer, als die Anzahl der Hinzufügungen über die put Anweisung.
DEAKTIVIERE ich die equals() und hashCode Überschreibung sind es 6 (soviel wie put Anweisungen)
Es verlockt zu glauben, dass da Cluster (=Anhäufungen) entstehen bei bestimmten einzelnen keys.
Denn das ist bei hash Tabellen üblich. Ich denke so eine hash Tabelle ist eine zur konkreten HashMap übergeordnet (paralell) existierende Verwaltungstabelle, eben eine andere.
Im Beispiel sind die keys jeweils Objekte und die haben einen hashCode und einige bekommen den gleichen hashCode
Aber dennoch sieht es so aus, als ob KEINE Cluster entstehen, sondern durch Überschreibung ein key-value Paar gelöscht wird, wenn ein key-value Paar dazu kommt und das key Objekt (hier Tag) davon ein gleiches, also bereits vorhandenes ist.

Oder wie funktioniert das?

import java.util.Iterator;
import java.util.HashMap;
import java.util.*;

class Tag{
    String day;
    Tag(String d) { day = d; }
    /*public boolean equals(Object o) {  
        return ((Tag)o).day == this.day;
    }
    
    public int hashCode(){   // uneffiziente hashCode()
        return day.length();
    }*/
}

class HashMapTest1{
    
    public static void main(String[] args){
      
        Map<Tag, String> hmp1 = new HashMap<Tag, String>();

        Tag t1 = new Tag("Monday"); // hc 6     
        Tag t2 = new Tag("Monday"); // hc 6   
        Tag t3 = new Tag("Tuesday");// hc 7 
        Tag t4 = new Tag("Montag"); // hc 6 
        Tag t5 = new Tag("Monday"); // hc 6
        Tag t6 = new Tag("Donnerstag"); // hc 10
     
        hmp1.put(t6, "donnern");  
        hmp1.put(t3, "dienen");
        hmp1.put(t4, "mal ausschlafen");
        hmp1.put(t5, "blau machen"); 
        hmp1.put(t1, "nicht zum Friseur"); 
        hmp1.put(t2, "gesund frühstücken");  
        
        System.out.println(" Groesse der hashMap (Anzahl der key-value Paare) ist nun : "+hmp1.size());System.out.println();  
                           
            Set<Map.Entry<Tag, String>> entrySet = hmp1.entrySet();
            for (Map.Entry<Tag, String> anEntry : entrySet)
            {
             System.out.println(" X--> "+anEntry);           
            }
    }
}

 

[Matthias Reitinger]

Laut API Doku besteht eine HashMap aus key-value Paaren, was (wohl) eindeutig jeweils ZWEI "Teile" sind.
Wenn in der Klasse Tag equals() und auch hashCode überschrieben wird, dann
ist die mit size() geprüfte Anzahl der key-value Paare geringer, als die Anzahl der Hinzufügungen über die put Anweisung.
DEAKTIVIERE ich die equals() und hashCode Überschreibung sind es 6 (soviel wie put Anweisungen)

Das liegt im wesentlichen daran, dass eine HashMap die equals-Methode verwendet, um gleiche Objekte zu identifizieren. Wird ein put mit einem Key ausgeführt, für den schon einen identischer Key abgelegt ist, wird dieser überschrieben (steht auch in der API-Dokumentation). Mit evtl. auftretendem Clustering hat das überhaupt nichts zu tun.

Der Unterschied zwischen nicht-Überschreiben und Überschreiben ist folgender: überschreibst du equals nicht, wird die Standardimplementierung aus der Klasse Object verwendet. Diese gibt nur true zurück, wenn ein Objekt mit sich selbst verglichen wird. Also gilt konkret:

(new Tag("Monday")).equals(new Tag("Monday")) == false

Verwendest du deine Überschreibung, gilt stattdessen:

(new Tag("Monday")).equals(new Tag("Monday")) == true

Aus diesem Grund treten ohne Überschreibung keine Ersetzungen auf (da alle Keys unterschiedlich sind), andernfalls jedoch schon (da es einige Keys gibt, die identisch sind).

Grüße,
Matthias

 

[Steve222]

Das liegt im wesentlichen daran, dass eine HashMap die equals-Methode verwendet, um gleiche Objekte zu identifizieren. Wird ein put mit einem Key ausgeführt, für den schon einen identischer Key abgelegt ist, wird dieser überschrieben (steht auch in der API-Dokumentation). Mit evtl. auftretendem Clustering hat das überhaupt nichts zu tun.

Der Unterschied zwischen nicht-Überschreiben und Überschreiben ist folgender: überschreibst du equals nicht, wird die Standardimplementierung aus der Klasse Object verwendet. Diese gibt nur true zurück, wenn ein Objekt mit sich selbst verglichen wird. Also gilt konkret:

(new Tag("Monday")).equals(new Tag("Monday")) == false

Verwendest du deine Überschreibung, gilt stattdessen:

(new Tag("Monday")).equals(new Tag("Monday")) == true

Aus diesem Grund treten ohne Überschreibung keine Ersetzungen auf (da alle Keys unterschiedlich sind), andernfalls jedoch schon (da es einige Keys gibt, die identisch sind).

Grüße,
Matthias

Vielen Dank für Deine Antwort.
Dass es mit Clustering nichts zu tun hat, war für mich zwar noch nicht so ganz sicher, aber immerhin sehr wahrscheinlich.
Nun besteht wenigstens Sicherheit diesbezüglich.
Aber wie und wo gibt es das Clustering [auch Kolllision genannt]?
Es heisst doch, dass bei einem uneffizenten hashing so vielen Clustern kommt, also bei einem einzigen hashCode-Wert
mehrere verschiedene Objekte abgelegt sind, also ein Cluster innerhalb eines sogenannten "bucket" ensteht.

Die Anwendung von Hashing geht doch grundsätzlich so:
1.Finde mit dem hashCode-Wert den richtigen "bucket".
2.Nutze die equals() Methode um innerhalb eines "bucket" das gewünschte Objekt zu identifizieren.

Ich stelle mir vor, dass es eine Art von Verwaltungstabelle (Hashtabelle) gibt, die paralell zur konkreten HashMap existiert.
Da jedes Objekt einen internen hashCode erhält und in konkreten HashMap als key fungieren kann, besteht
die Gefahr, dass da etwas verwechselt wird, nämlich dass in der konkreten HashMap bei einem einzigen key
mehrere verschiedene Objekte abgelegt sind.

Ist die Tabelle, in der diese Cluster enstehen können, eine Art von dazugehöriger Verwaltungstabelle (Hashtabelle) die
pro konkreter HashMap geführt wird?

(Was nicht gerade zur Klarheit beiträgt ist, dass viele Leute unter einem "Schlüssel" einen einzigen Wert verstehen,
während andere darunter die komplette Verschlüsselung, also den kompletten Verschlüsselungsalgorithmus damit meinen.)

freundlicher Gruß

Steve222

 

[Matthias Reitinger]

Aber wie und wo gibt es das Clustering [auch Kolllision genannt]?

Kollision und Clustering sind keine Synonyme. Eine Kollision tritt auf, wenn die verwendete Hashfunktion zwei Schlüssel auf den selben Hashwert abbildet. Unter Clustering versteht man die Bildung von längeren Sequenzen von belegten Feldern in einer Hashtabelle mit offener Adressierung. Wie und ob bei der HashMap von Java Clustering auftritt, kann ich dir nicht sagen.

Die Anwendung von Hashing geht doch grundsätzlich so:
1.Finde mit dem hashCode-Wert den richtigen "bucket".
2.Nutze die equals() Methode um innerhalb eines "bucket" das gewünschte Objekt zu identifizieren.

Bei geschlossener Adressierung, ja. Bei offener Adressierung verwendet man eine Sondierungsverfahren, falls das Feld in der Hashtabelle einen anderen Schlüssel enthält.

Ich stelle mir vor, dass es eine Art von Verwaltungstabelle (Hashtabelle) gibt, die paralell zur konkreten HashMap existiert.
Da jedes Objekt einen internen hashCode erhält und in konkreten HashMap als key fungieren kann, besteht
die Gefahr, dass da etwas verwechselt wird, nämlich dass in der konkreten HashMap bei einem einzigen key
mehrere verschiedene Objekte abgelegt sind.

Ist die Tabelle, in der diese Cluster enstehen können, eine Art von dazugehöriger Verwaltungstabelle (Hashtabelle) die
pro konkreter HashMap geführt wird?

Was meinst du mit der „konkreten HashMap“? Eine HashMap ist eine mögliche Implementierung des abstrakten Datentyps Map, die intern eine Hashtabelle verwendet. Ich verstehe nicht, wo dort die „Gefahr, dass da etwas verwechselt wird“ besteht. Ob Cluster entstehen können oder nicht kann dir ziemlich egal sein, da du davon nichts mitkriegst (rein funktionell betrachtet).

Grüße,
Matthias

 

[Steve222]

Hallo Matthias,

und vielen Dank für die Antwort.

Was meinst du mit der „konkreten HashMap“?

Damit meine ich eine Instanz, also ein Objekt der class HashMap.

Eine HashMap ist eine mögliche Implementierung des abstrakten Datentyps Map, die intern eine Hashtabelle verwendet.

So habe ich es vermutet. Also intern wird Verwaltungstabelle, "Hashtabelle" genannt, verwendet, die bei der Arbeit (Lesen/Schreiben) mit einem HashMap-Objekt hmObj4811 für schnellen Zugriff auf die Elemente von hmObj4811 sorgt.

Ich schrieb: >>Aber wie und wo gibt es das Clustering [auch Kolllision genannt]?<<
Das war natürlich zu ungenau die beiden Begriffe als Synonyme zu deklarien.
Ich denke es ist so, dass eine unbehandelte nicht aufgelöste Kollision zu einem Cluster führt. Oder?

Wie und ob bei der HashMap von Java Clustering auftritt, kann ich dir nicht sagen.

So weit ich weiß, wird Clustering (manchmal) in Kauf genommen, da es eher selten ist und wenn es mal auftritt bzw. vorliegt, dann nur wenig Probleme macht.

Mit freundlichem Gruß
Steve222

 

[Matthias Reitinger]

Ich schrieb: >>Aber wie und wo gibt es das Clustering [auch Kolllision genannt]?<<
Das war natürlich zu ungenau die beiden Begriffe als Synonyme zu deklarien.
Ich denke es ist so, dass eine unbehandelte nicht aufgelöste Kollision zu einem Cluster führt. Oder?

Nein. Kollisionen müssen bei offener Adressierung immer irgendwie behandelt werden, da die Hashtabelle sonst nicht funktionieren würde. Clustering tritt auf, gerade weil man Kollisionen auflöst.

So weit ich weiß, wird Clustering (manchmal) in Kauf genommen, da es eher selten ist und wenn es mal auftritt bzw. vorliegt, dann nur wenig Probleme macht.

Clustering wirkt sich immer negativ auf die Laufzeit eines Zugriffs aus. Je größer die Cluster, desto langsamer wird der Zugriff. Eine Methode um Clustering zu vermeiden ist die Verwendung einer möglichst guten Hashfunktion. Eine zweite Maßnahme (auf die man bei einer HashMap aber keinen Einfluss hat) wäre die Wahl eines guten Sondierungsverfahrens (z.B. Double Hashing). Schließlich sollte der Belegungsfaktor der Hashtabelle möglichst klein gehalten werden, da sonst selbst bei der besten Hashfunktion und dem besten Sondierungsverfahren große Cluster auftreten können. Diesen Wert hat man bei Javas HashMap über den Konstruktor HashMap(int, float) steuern.

Grüße,
Matthias

 

[Anime-Otaku]

Das liegt im wesentlichen daran, dass eine HashMap die equals-Methode verwendet, um gleiche Objekte zu identifizieren.

Tut mir leid, aber das ist nicht richtig.
Eine HashMap, wie der Name schon sagt schaut nur auf die hashCode Methode. Allerdings sollte immer hashCode und equals implementiert sein und das gleiche Ergebnisse bezüglich Gleichheit liefern.

Wenn du keine equals/hashCode Methode implementiert hast, wird die der übergeordneten Klasse benutzt. Was letztendlich auf Object hinausläuft. Hier ist der hashCode normalerweise die Speicheradresse des Objekts und equals überprüft auch nur diesen.


Dann gibt es noch das Interface Comparable, was am besten auch noch gleich implementiert werden sollte, wenn nach dem Inhalt sortiert werden soll.
Ein Vergleich über hashes ist oftmals schneller, als ein Vergleich über compareTo. Allerdings ist die Frage, ob man die Daten zu jeder Zeit sortiert vorliegen haben will oder nicht. Das kommt auf den Anwendungsfall an.

Ich hoffe ich war nicht zu sehr Off Topic

 

[Matthias Reitinger]

Tut mir leid, aber das ist nicht richtig.
Eine HashMap, wie der Name schon sagt schaut nur auf die hashCode Methode. Allerdings sollte immer hashCode und equals implementiert sein und das gleiche Ergebnisse bezüglich Gleichheit liefern.

So ein Unsinn. Lies die Dokumentation oder probier es selbst aus. Objekte mit unterschiedlichem Hashcode dürfen zwar nicht equals sein, aber Objekte mit gleichem Hashcode müssen nicht equals sein.

Grüße,
Matthias

 

[Anime-Otaku]

So ein Unsinn. Lies die Dokumentation oder probier es selbst aus. Objekte mit unterschiedlichem Hashcode dürfen zwar nicht equals sein, aber Objekte mit gleichem Hashcode müssen nicht equals sein.

Grüße,
Matthias

Ich habe da lieber in den Code geschaut
Ich gebe dir Recht. Das equals zusätzlich zur Überprüfung bei get() benutzt wird war mir nicht klar. Aber ich finde Objekte mit gleichem Hashcode sollten equals sein.

Ich war mir einfach sehr sicher bei der Antwort, ich wusste nicht, dass hier noch zusätzlich zur Absicherung die equals Methode benutzt wird. Nobody is perfect.

 

[Steve222]

Nein. Kollisionen müssen bei offener Adressierung immer irgendwie behandelt werden, da die Hashtabelle sonst nicht funktionieren würde. Clustering tritt auf, gerade weil man Kollisionen auflöst.

Hallo Matthias,
und Danke.
Ich stimme Dir zu, dass Clustering auftritt, gerade weil man Kollisionen auflöst.

Für mich hatte ein Cluster, auch den Charakter einer Kollision, weil eben mehrere Objekte sich an einer Stelle, d.h.
bei einem HashCode befinden.

Ich nahm an, dass unter einer „nicht aufgelösten Kollision“ der Zustand
verstanden wird, dass unter einem bestimmten hashCode, mehr als ein Objekt, also mehrere Objekte, in der Hashtabelle abgelegt werden.
Aber es ist wohl so, dass wenn es so gehandhabt wird, dass mehrere Objekte mit gleichem hashCode zusammen unter einem gleichem hashCode so abgelegt werden, dass die Hashtabelle dennoch nutzbar ist, man von einer „aufgelösten Kollision“ spricht.

Gruß
Steve222