Hash Map

Diskutiere Hash Map im Allgemeine Java-Themen Bereich.
Kirby_Sike

Kirby_Sike

Alsoo wir sollen eine Hash Map implementieren, verstehe ich es richtig, dass man im Grunde einen Container hat welcher anzahl von capacity buckets hat, welche wiederrum beliebig viele Objekte enthalten?

Ein Bucket wäre in diesem Fall ja ein Container wie z.B. dieser:

Java:
class Entry<Key, Value> {
    
    private final Key key;
    private Value value;
    private Entry<Key, Value> next;
    
    public Entry(Key key, Value value) {
        this.key = key;
        this.value = value;
    }
    
    public Key getKey() {
        return key;
    }
    
    public Value getValue() {
        return value;
    }
    
    public void setNext(Entry<Key, Value> next){
        this.next = next;
    }
    
    public Entry<Key, Value> getNext(){
        return  next;
    }
}
Der Container für diese Buckets könnte ja z.B. eine ArrayList oder ein Array sein.
Meine Frage ist nun, ist es korrekt, dass die sortierung in den bucket vom hashwert abhängt und im einzelnen bucket wird dann anhand des keys compared? :)
 
Kirby_Sike

Kirby_Sike

Edit: Es ist nur ein Art "Bucket", da ja Entry auf den nächsten Entry Container refrenziert :)
 
MoxxiManagarm

MoxxiManagarm

Ich finde deine Benennungen total irreführend :D

Du kannst getrost ein Linked davor setzen, denn das hast du hier - eine LinkedHashMap

dass man im Grunde einen Container hat welcher anzahl von capacity buckets hat
Du hast oben noch keinen Container. Einen Container hast du, sofern du wie bei LinkedList eine Klasse mit einem Head hast. Die Klasse ist dann quasi der Container. buckets finde ich dahingehend irreführend, da bei linked Implementierungen eher von Nodes gesprochen wird. Ein Entry ist hier wie ein Node von der LinkedList.

welche wiederrum beliebig viele Objekte enthalten?
Klar, der Value kann alles sein, auch wiederum Container von Elementen wie Listen

Der Container für diese Buckets könnte ja z.B. eine ArrayList oder ein Array sein.
Nein, der Container ist wie bei LinkedList eine Klasse mit einem Head, wie oben erwähnt

Meine Frage ist nun, ist es korrekt, dass die sortierung in den bucket vom hashwert abhängt und im einzelnen bucket wird dann anhand des keys compared? :)
So hast du erstmal überhaupt keine Sortierung. Du kannst natürlich beim hinzufügen in die LinkedHashMap sortiert einfügen.
 
Zuletzt bearbeitet:
Kirby_Sike

Kirby_Sike

Ja gut dann war ich verwirrt, haben nämlich so gut wie kein Input bekommen...Nur die Methoden namen xD habe dann etwas gegooglet und Implementierungen mit Arrays etc gesehen :) Ich verstehe dennoch nicht wie eine Hash Map dann funktioniert :( Ich dachte nämlich, dass man eine „Haupt“ Listen hat, welche nach Hashwert einordnet und die Platzhalter der „Hauptliste“ auf das erste Entry Objekt zeigen und dieses halt immer seinen next Entry kennt etc :) Ich muss sagen diese Woche verwirrt mich die Aufgabe total :)
 
T

thecain

Du kannst getrost ein Linked davor setzen, denn das hast du hier - eine LinkedHashMap
Wenn eine HashMap implementiert werden soll würde ich schon Buckets erwarten. LinkedHashMap findet eher selten Anwendung. Daher würde ich eher den Verweis auf next streichen.

Wie HashMaps funkionieren werde ich jetzt nicht erklären. Das steht ja schon zuhauf im Internet
 
Kirby_Sike

Kirby_Sike

Ok, was ich jedoch nicht verstehe wie ich die Buckets erstellen soll...Sprich wie verwende ich ein Array für Generics? Ich habe etwas gegooglet und dort wurde gesagt, dass man zwischen unchecked und checked Type unterscheiden muss. Bei checked Type soll man es so machen:

Java:
public class GenSet<E> {

    private E[] a;

    public GenSet(Class<E> c, int s) {
        // Use Array native method to create array
        // of a type only known at run time
        @SuppressWarnings("unchecked")
        final E[] a = (E[]) Array.newInstance(c, s);
        this.a = a;
    }

    E get(int i) {
        return a[i];
    }
}
Das Problem hier ist, dass der Konstruktor vorgegeben ist...
 
Kirby_Sike

Kirby_Sike

Ich wollte mir die java.util.HashMap anschauen, aber um ehrlich zu sein habe ich den part nicht gefunden wo das Array initialisiert wird :(
 
Kirby_Sike

Kirby_Sike

Aber ist es nicht sehr Fehleranfällig? Also der Cast?
Java:
public class HashMap<Key, Value> {
    
    private Entry<Key, Value> buckets[];
    final Entry<?,?>[] EMPTY_TABLE = {};
    private int size;
    private int hashmode;
    private final double a = 0.61803398;
    
    public HashMap(int capacity, int mode) {
        buckets = (Entry<Key,Value>[]) EMPTY_TABLE;
        hashmode = mode;
        size = 0;
    }
}

Type safety: Unchecked cast from Entry<?,?>[] to Entry<Key,Value>[]
 
J

JustNobody

Ich wollte mir die java.util.HashMap anschauen, aber um ehrlich zu sein habe ich den part nicht gefunden wo das Array initialisiert wird :(
Die Klasse findest Du z.B. unter:

resize() macht das u.a. - da findet sich dann der Code:
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

Und dieses newTab wird dann table zugewiesen.
 
Kirby_Sike

Kirby_Sike

Das hatte ich auch gesehen :) War mir nicht wirklich sicher ob das richtig war xD Uns wurde in dem Modul Einführung in OOP(im 1. Semester) eingeprüggelt: "Casts sind böse" xD Deswegen hatte ich mich gewundert, dass man es so macht :)
 
T

thecain

Geht halt nicht anders/besser in dem Fall.
Keine Regel ohne Ausnahme
 
Kirby_Sike

Kirby_Sike

Also ich bin leicht verwirrt...Wir sollen für das hashing zwei verschiedene Modis anlegen...Eimal Hash mit Divisionsfunktion (mode = 0) und einmal mit der Multiplikationsfunktion (mode = 1). Bei Verwendung der Multiplikationsmethoden kommen schlichtweg falsche werte raus und komischer weiße ist der Key.hashcode() der korrekte Wert für das einordnen in das Array :( Ich verstehe nicht woran es liegt:

Java:
 private int getHash(Key key) {
        int hash = key.hashCode();
        if(hashmode == 0) {
            return hash % buckets.length;
        }
        
        if(hashmode == 1){
            return (int)(buckets.length * (hash * a - (int)(hash * a)));
        }
        return -1;
    }
Die Test eingaben wären diese:

Java:
        HashMap<Integer, String> s = new HashMap<Integer, String>(5,1);
        s.insert(0, "Datenstrukturen");
        s.insert(1, "und");
        s.insert(2, "effiziente");
        s.insert(3, "Programmierung");
        System.out.println(s.toString());
Der erwartete Output ist:

Code:
[0] [(0,Datenstrukturen)]
[1] [(1,und)]
[2] []
[2] [(2,effiziente)]
[3] [(3,Programmierung), (8,I)]
[4] []
Der Output welcher kommt ist dieser:

Code:
[0] [(0,Datenstrukturen)]
[1] [(2,effiziente)]
[2] []
[3] [(1,und)]
[4] [(3,Programmierung)]
 
Kirby_Sike

Kirby_Sike

Oh sorry xD den "goldenen Schnitt" : private final double a = 0.61803398;
 
F

fhoffmann

Java:
public class Test {
    public static void main(String[] args) {
        double a = 0.61803398;
        for(int hash = 0; hash < 10; ++hash) {
            int index = (int)(5 * (hash * a - (int)(hash * a)));
            System.out.println(hash + ": " + index);
        }
    }
}
 
Kirby_Sike

Kirby_Sike

Also es sind die Werte scheinbar korrekt...Dann verstehe ich nicht warum dann die Werte erwartet werden :( Ich schicke mal meine Insert Methode:

Java:
public boolean insert(Key key, Value value) {
        int hash = getHash(key);
        Entry<Key, Value> entry = new Entry<>(key, value);
        Entry<Key, Value> it = buckets[hash];
        System.out.println("Hash Code: " + hash);
        
        while(it != null && it.getNext() != null) {
            if(it.getKey().hashCode() == hash) return false;
            it = it.getNext();
        }
        if(it == null) {
            buckets[hash] = entry;
        }else {
            it.setNext(entry);
        }
        size++;
        return true;
    }
 
Kirby_Sike

Kirby_Sike

Ich hatte im Internet gelesen, dass keys mit dem gleichen hashcode auch gleich sein müssen und deshalb wollte ich damit dopllungen ausschließen xD Oder habe ich da was falsch verstanden? Mein Dozent hat nämlich, das in die Aufgabenstellung geschrieben:

Code:
insert: Genau dann, wenn ein Element nicht eingefügt werden kann, weil der Schlüssel bereits existiert, soll false zurückgegeben werden.
Oder soll ich die Keys mit .equals() vergleichen xD
 
J

JustNobody

Ich hatte im Internet gelesen, dass keys mit dem gleichen hashcode auch gleich sein müssen und deshalb wollte ich damit dopllungen ausschließen xD Oder habe ich da was falsch verstanden? Mein Dozent hat nämlich, das in die Aufgabenstellung geschrieben:
Nein, das ist zweifach falsch:
a) Elemente, die gleich sind, müssen den gleichen Hashcode haben. Aber das gilt nicht umgekehrt. Ist ja auch logisch, denn es gibt oft viel weniger Hashcode Möglichkeiten als mögliche Kombinationen an Werten in einer Klasse.
b) Dein hash ist ja kein hashcode des Elements sondern die Ermittlung eines Buckets. Wenn Du nur einen Bucket hast (macht kein Sinn, aber extremes Beispiel), dann wäre Dein "hash" immer 0. Dann wären ja alle Elemente gleich, oder wie?
 
Thema: 

Hash Map

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben