Hab ich geändert, trotzdem die gleichen Fehler : (
Ohne jemals eine Implementierung einer HashMap gesehen zu haben, kann dein Ansatz nicht funktionieren, weil du die Einträge in einem eindimensionalen Array speicherst.
Du brauchst deine Buckets, die wiederum aus einfach verketteten Listen bestehen. Der Hash des Eintragschlüssels gibt vor, in welchem Bucket der Eintrag landet, dieser wird dann in die Liste eingefügt, sofern für den Schlüssel noch kein Eintrag existiert (andernfalls wird der Eintrag überschrieben).
Eine Kollision gibt es dann, wenn zwei Schlüssel einen Hash haben, der in das selbe Bucket einsortiert werden soll. Nach spätestens 100 Einträgen muss es in deiner Implementierung zu einer Kollision kommen.
Abgesehen davon ist der Test Müll, weil er nicht das testet, was er testen soll. Ich hätte da eher so etwas gemacht:
Hashing<Object, Integer> objTable = new Hashing<>();
Object firstKey = new Object() {
public int hashCode() {
return 42;
}
};
Object secondKey = new Object() {
public int hashCode() {
return 42;
}
};
objTable.put(firstKey, 1);
objTable.put(secondKey, 2);
assertEquals(Integer.valueOf(1), objTable.get(firstKey));
assertEquals(Integer.valueOf(2), objTable.get(secondKey));
}```
(Code ist im Browser geschrieben, kann also sein, dass kleinere Fehler drin sind)
*** Edit ***
@Bleiglanz : doch, man braucht eine While-Schleife. Und zwar um innerhalb eines Buckets durch die Liste zu iterieren.ohje ok also doch wieder While-Schleife rein…
Also gegen den Test kann ich leider nichts machen der war vorgegeben^^
Dann war also dieser Ansatz richtig? :
h = (h+1)% data.length;
return data[h];
}
private int hash(Object key) {
return key == null ? 0 : (key.hashCode() & 0x7fffffff) % data.length;
}
Ich hab grad keine Zeit mir das so detailliert anzusehen, aber poste bitte einmal die kompletten Klassen, so wie du sie hast. Dann sehe ich es mir nachher an.
ok danke : )
//import util.Hashing.Entry;
/**
* Die Klasse implementiert ein Verzeichnis, in dem nach
* unter einem Schluessel gespeicherten Daten gesucht werden
* kann.
* <p>
* Als Implementierungsmethode wird die Kollisionsbehandlung der
* direkten Verkettung verwendet.
*/
public class Hashing<K,V> implements IMap<K,V> {
/**
* Anzahl der gespeicherten Key-Value-Paare.
*/
private int size = 0;
/**
* Feld mit den Daten.
*/
@SuppressWarnings("unchecked")
private Entry<K,V>[] data = new Entry[100];
@Override
public int size() {
return size;
}
@Override
public V put(K key, V value) {
Entry<K,V> p = referenceOf(key);
if (p == null) {
int index = hash(key);
data[index] = new Entry<K,V>(key, value, data[index]);
size++;
return null;
}
return p.setValue(value);
}
@Override
public V get(K key) {
Entry<K,V> p = referenceOf(key);
return p == null ? null : p.value;
}
@Override
public boolean containsKey(K key) {
// TODO den richtigen Algorithmus einsetzen.
return referenceOf(key) != null;
}
/**
* Findet die Referenz zu dem Entry mit key oder gibt null zurueck.
* @param key Suchschluessel
* @return null oder Referenz auf gefundenen Entry.
*/
private Entry<K,V> referenceOf(K key) {
// TODO den richtigen Suchalgorithmus (direkte Verkettung) einsetzen.
if(key == null)
throw new NullPointerException();
int h = hash(key);
//int h = (key.hashCode() & 0x7FFFFFFF) & data.length;
/*if (data[h]== null)
return null;
if(key.equals(data[h].key))
return data[h];
return null;*/
//////////////////////////////////////////////////////
while(safeEquals(data[h],key))
h = (h+1) %data.length;
return data[h];
}
private int hash(Object key) {
return key == null ? 0 : (key.hashCode() & 0x7fffffff) % data.length;
}
private static boolean safeEquals(Object a, Object b) {
return a == null ? a == b : a.equals(b);
}
/**
* Klasse fuer die einzelnen Eintraege.
*/
static class Entry<K,V> {
private final K key;
private V value;
private Entry<K,V> link;
/**
* Konstruktor.
*
* @param key Schluesselbegriff.
* @param value eigentlicher Inhalt.
*/
Entry(K key, V value, Entry<K,V> link) {
this.key = key;
this.value = value;
this.link = link;
}
/**
* Veraendert den Inhalt des Eintrags und gibt den ueberschriebenen
* Inhalt zurueck.
*
* @param value neuer Inhalt.
* @return vorhergehender Inhalt.
*/
V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
@Override
public String toString() {
return key + ":" + value;
}
}
}```Nein, es handelt sich ja um gar kein echtes Hashing
private Entry<K,V>[] data = new Entry[100];
Wir bräuchten mal den Text der Aufgabe (So wie das jetzt ist, kann es eigentlich nicht richtig sein. Wahrscheinlich ist nicht nur die eine Methode, sondern sogar die ganze Klasse defekt).
Aufgabenblatt gibts nicht.
Die Klasse soll an den angegebenen Stellen korigiert werden.
Dort wo steht TO DO .
Zusätzlich hat man eine Reihe von JUNIT Tests die laufen müssen.
So wie ich jetzt die Klasse zuletzt gepostet habe läuft nur der eine Test nicht den ich auch gepostet habe.
Mache ich es so wie du es mir geschrieben hast Bleiglanz dann kommt der Fehler nullpointerException bei meiner Version kommt expectet 0 but was 914.
Vielleicht wurde es ja überlesen aber es geht um eine verkettete liste mit Hashzahlen also eine direkt verkettete liste
Ok, die Entry-Klasse ist jeweils ein Eintrag in einer verketteten Liste (im Gegensatz zu dem gewohnten Map.Entry<K, V>). Damit sollte es funktionieren (ungetestet):
// TODO den richtigen Suchalgorithmus (direkte Verkettung) einsetzen.
if (key == null)
throw new NullPointerException();
int h = hash(key);
Entry<K, V> current = data[h];
while (current != null && !current.equals(key))
current = current.link;
return current;
}```
Was passiert ist eigentlich ganz einfach. Es wird das erste Element des Buckets, welches zum Hash gehört ausgewählt. In der Schleife wird dann immer geprüft, ob man am Ende angekommen ist. Wenn nicht, dann wird geprüft, ob das aktuelle Element das gesuchte ist. Falls das nicht der Fall ist, wird das nächste Element im Schleifenrumpf ausgewählt.danke dir vielmals für deine Mühe, aber haut immer noch nicht hin : ( ausserdem ist noch eine Methode namens Safequals dort die nicht benutzt wird.
Ich gebe es langsam auf… jetzt blinkt neben dem einen Fehler noch mehrere auf die vorher funktioniert haben…
Hab’ nicht alles im Detail gelesen, aber ein Array wird nicht reichen. Eigentlich besteht so eine Hash Map aus zwei Stufen:
- Berechne den Hashwert und bestimme daraus den Arrayindex
- Für den gegebenen Index: SUCHE nach dem passenden Eintrag (in der verkettenen Liste von Einträgen, die an diesem Index stehen)
Letzteres macht man über den “link” in der Entry-Klasse - den scheinst du überhaupt nicht zu verwenden!?
Die ist ja auch überflüssig. Vom Prinzip her sollte das so schon in die richtige Richtung gehen (eigentlich bin ich mir ziemlich sicher, dass es richtig ist). Aber dazu solltest du vielleicht auch mal die Unittests und das Interface IMap zeigen.
Und aus deinen obigen Versuchen erscheint es mir, als wenn du das Prinzip der Hashmap noch nicht ganz verstanden hast (siehe @Marco13 s Beitrag).
[QUOTE=cmrudolph]Ohne jemals eine Implementierung einer HashMap gesehen zu haben, kann dein Ansatz nicht funktionieren, weil du die Einträge in einem eindimensionalen Array speicherst.
Du brauchst deine Buckets, die wiederum aus einfach verketteten Listen bestehen[/QUOTE]
Nicht unbedingt, siehe folgendes Beispiel:
char c = 'a'; // (Lauf-)Variable, damit nicht immer das Gleiche in oaa steht
for (Object[] objects : oaa) {
Arrays.fill(objects, "" + c++);
}
for (int i = 0; i < oaa.length; i++) {
if (Math.random() < 0.5) {
oaa** = new Object[4]; // <-- das war vorher ja Länge 2
Arrays.fill(oaa**, "" + c++);
}
}
System.out.println("oaa = " + Arrays.deepToString(oaa));
for (int i = 0; i < oaa.length; i++) {
System.out.println("oaa** = " + Arrays.toString(oaa**));
}```
---
@ tealino : Erst muss geklärt werden, was eigentlich die Aufg. ist. Also zB Hash-Funktion, Einfügen, Suchen, Entfernen, Verkleinern/Vergrößern, Ausageben... Wenn der Hash nicht genau mit dem Arrayelementindex übereinstimmt, aber irgendeine Reihenfolge der Elemente besteht, wäre auch eine binäre Suche auf dem "Hash"set/-map (also dem Array) denkbar/möglich.Gut, meine Aussage war etwas überspezifiziert. Es muss keine verkettete Liste sein, sondern kann natürlich auch ein Array oder eine andere Listenstruktur sein.
Eine Verkettete Liste ist aber die beste Datenstruktur dafür, weil Hinzufüge- und Löschoperationen billig sind (sprich in konstanter Zeit und ohne Kopieroperationen) ausgeführt werden können. Die Suche wird in linearer Zeit ausgeführt, was innerhalb eines Buckets optimal ist, weil unabhängig von der Datenstruktur jedes Element einzeln angesehen werden muss.
Mir scheint das Problem schon bei
static class Entry<K,V> {
private final K key;
private V value;
private Entry<K,V> link;
Entry(K key, V value, Entry<K,V> link) {
this.key = key;
this.value = value;
this.link = link;
}
V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
}
und
public V put(K key, V value) {
Entry<K,V> p = referenceOf(key);
if (p == null) {
int index = hash(key);
data[index] = new Entry<K,V>(key, value, data[index]);
size++;
return null;
}
return p.setValue(value);
}
zu liegen. Wenn man was hinzufügt und der key schon da war, dann man p.setValue doch das völlig falsche. Es sollte ein Element hinzugefügt werden zu einer verketteten Liste?
Das sollte so schon passen. Die put-Methode macht doch folgendes:
[ol][li]suche einen Eintrag, der zum Schlüssel gehört (in referenceOf muss berücksichtigt werden, dass die Schlüssel in einem Bucket in einer verketteten Liste abgelegt sind)[/li][li]falls kein Eintrag zu dem Schlüssel existiert, füge dem zugehörigen Bucket einen Eintrag hinzu und inkrementiere size[/li][li]der alte Wert war nicht belegt, also wird null zurückgegeben[/li][li]falls es einen Eintrag zum Schlüssel gab, wird der Wert überschrieben und der alte Wert zurückgegeben (das passiert ja in Entry)[/ol][/li]Ich glaube aber, dass das
so gemeint war.
Wie Bleiglanz sagt, die “link” Variable deiner Entry Klasse wird für nix benutzt. Der Sinn davon ist, dass Werte mit gleichem Hash gespeichert werden können, also musst du in der put nicht einfach den Wert überschreiben sondern ein neues Entry erzeugen und den link des alten Entrys auf das neue zeigen lassen.
Deine while Schleife im referenceOf brauchst du dann, um die Liste des Elements durchzugehen, NICHT um das data Array durchzugehen. Auf das Feld im data Array kommst du durch die Hash-Funktion. Wenn der Entry Key nicht mit dem gesuchten übereinstimmt, dann gehst du eben die Liste durch.