Hash Map

Kirby.exe

Top Contributor
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? :)
 

MoxxiManagarm

Top Contributor
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.exe

Top Contributor
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 :)
 

thecain

Top Contributor
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.exe

Top Contributor
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.exe

Top Contributor
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.exe

Top Contributor
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>[]
 
K

kneitzel

Gast
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.exe

Top Contributor
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 :)
 

Kirby.exe

Top Contributor
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)]
 

fhoffmann

Top Contributor
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.exe

Top Contributor
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.exe

Top Contributor
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
 
K

kneitzel

Gast
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?
 

Kirby.exe

Top Contributor
Aight xD Dann lag ich falsch :) Ich verstehe dennoch nicht why die Buckets falsch belegt werden :( Die richtige Belegung wäre scheinbar einfach der Wiedergabewert der .hashcode() methode oder nicht?
 

Kirby.exe

Top Contributor
Ich habe den Fehler gefunden...Ich schlauberger sollte genauer hinschauen...Ich hatte die Parameter für die zwei Hashing methoden vertauscht xD
 

Kirby.exe

Top Contributor
Eine Frage hätte ich noch :) Alsoo wir sollen bei unserer Hash Map erstmal keine Kollisionsbehandlung durchführen sondern einfach mit Chaining Elemente mit gleichem HashWert aneinander hängen :) Ich würde gerne einen solchen Testcase erstellen, da ich mir ziemlich sicher bin, dass ich bei meiner implementierung dafür eine NPE bekommen werde :) KeyType ist Integer
 

thecain

Top Contributor
Du kannst ja HashCode so implementieren das es Kollisionen gibt. z.B. einen fixen Wert zurückgeben.

Mit Integer als key klappt das mMn nicht, da es keine Kollisionen gibt.
 

Ähnliche Java Themen

Neue Themen


Oben