Datentypen Probleme mit eigenem Get() bei eigener HashMap

[btl1000]

Nabend,

ich noch mal 🙂

Jetzt habe ich also mein simples Beispiel der HashMap-Nutzung an's Laufen bekommen. Doch diese konnte mit Kollisionen nicht umgehen. Also habe ich begonnen, eine eigene HashMap (AdressenHashMap) zu bauen. Darin sollten später get und put durch komplexere Funktionen ersetzt werden, so dass put bei einer Kollision eben eine verkettete Liste verlängert (noch nicht drin) und get eben die verkettete Liste zurück gibt.

Doch nun stolpere ich schon auf dem Hinweg. Ich bekomme es gar nicht erst hin eine eigene get-Methode zu schreiben. Wenn ich ein eigenes "get" definiere, compiliert zwar alles, aber offenbar entsteht ein rekursiver Aufruf und das Ding bleibt irgendwann mit einem Overflow liegen.

Wenn ich es get2 nenne, funktioniert es. Das ist zwar OK, aber ich würde schon gerne verstehen, was an meinem ersten Ansatz falsch war (im Sourcecode einfach get2 durch get ersetzen). Zumal es bei put problemlos funktioniert.

Hat da jemand eine Idee?

package hash1;
import java.util.HashMap;
import java.util.Map;


class AdressHashMap extends HashMap<Integer,Adresse> 
{
	AdressHashMap()
	{
		super();
	}
		
	public Adresse put ( Adresse a)
	{
		Integer hv;
		hv = a.hashCode();		
		System.out.println("Put: "+hv+"--"+a);
		return this.put(hv,a);
		}
	
	public Adresse get2 (Integer kv)
	{
		String text = "fail";
		Adresse ad = new Adresse("fail","fail","fail","fail");
		
		ad = this.get(kv);
		text = ad.toString();
		System.out.println("Get: "+kv+" = "+text);
		return ad;
	}
}

hier das drumherum

package hash1;
public class Adresse {
		String vorname;
		String nachname;
		String strasse;
		String ort; 
		
	Adresse (String vn, String nn,  String st, String or)
	{
		vorname = vn;
		nachname = nn;
		strasse = st;
		ort = or;
	}
	

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Adresse other = (Adresse) obj;
		if (nachname == null) {
			if (other.nachname != null)
				return false;
		} else if (!nachname.equals(other.nachname))
			return false;
		return true;
	}

	
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result
				+ ((nachname == null) ? 0 : nachname.hashCode());
		System.out.println("HC für >"+nachname+"< = "+result);
		return result;
	}

		public String toString()
		{
			return vorname+", "+nachname+"; "+strasse+", "+ort;
		}
	
}

package hash1;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

public class Example3 {
	public static void main(String[] args) {
		Adresse a = new Adresse("","","","");
		Adresse b = new Adresse("","","","");

		Collection<Adresse> adressliste =  new LinkedList<Adresse>();
		AdressHashMap adlhash = new AdressHashMap();
		
		
		// Beispieldaten einfüllen
		adressliste.add(new Adresse("Alerich","Amann","3","4"));
		adressliste.add(new Adresse("Berta","Bfrau","3","4"));
		adressliste.add(new Adresse("Charlie","Code","3","4"));
		adressliste.add(new Adresse("Dieter","Amann","3","4"));

		// Jetzt einfach wieder ausgeben und dabei in einer Hash-Tabelle abspeichern
		for ( Iterator<Adresse> i = adressliste.iterator();  i.hasNext(); )
		{
			a = i.next(); 
			adlhash.put(a);
		}	
		System.out.println("-----------------------");

		/* Hash-Map zeigen */
		for ( Map.Entry< Integer , Adresse> elem : adlhash.entrySet())
		{			
			a = elem.getValue();
			System.out.println(a.nachname+" > "+elem.getKey());
		}

		// Suche		
		System.out.println("-----------------------");
		
		Integer hc = 0;
		
		a = new Adresse("","Amann","","");
		hc = a.hashCode();
		System.out.println("Suche "+hc+" = "+a);

		b = adlhash.get2(hc);
		System.out.println("Finde "+hc+" = "+b);
	
	}
}

Danke schonmal.

 

[2000]

Jetzt habe ich also mein simples Beispiel der HashMap-Nutzung an's Laufen bekommen. Doch diese konnte mit Kollisionen nicht umgehen. Also habe ich begonnen, eine eigene HashMap (AdressenHashMap) zu bauen. Darin sollten später get und put durch komplexere Funktionen ersetzt werden, so dass put bei einer Kollision eben eine verkettete Liste verlängert (noch nicht drin) und get eben die verkettete Liste zurück gibt.

Wo ist das Problem, einfach als values der HashMap List zu verwenden? Als key kann dann das in die jeweilige Liste einzufügende Element gewählt werden. So ist es praktisch, einen Wrapper zu schreiben, der die put implementiert.

 

[r.w.]

Hallo btl1000,

ein Blick auf die gleichnamigen Funktionen der Klasse HashMap zeigt, das Deine put-Methode andere Parameter
als die der Basisklasse erwartet. Daher wird in Zeile 18 die Methode put der Basisklasse HashMap aufgerufen.
Deine get-Methode überschreibt aber wegen passender Parameterliste die get-Methode von HashMap.
Daher wird in Zeile 26 die Methode get in AddressHashMap aufgerufen und somit die Rekursion "erzeugt".

Ich hoffe, dass gibt Dir Klarheit. (Ich werde später nochmal lesen was ich um diese Zeit zusammengeschrieben hab. ;-) )

VG ROlf

 

[Andi_CH]

Wer ausdrücklich this.get() hinschreibt will ja nichts anderes als seinen eigene get Funktion aufrufen...

super.get wäre die bessere Variante. Dann kannst du deine eigene auch wieder get nennen.

 

[btl1000]

Wo ist das Problem, einfach als values der HashMap List zu verwenden? Als key kann dann das in die jeweilige Liste einzufügende Element gewählt werden. So ist es praktisch, einen Wrapper zu schreiben, der die put implementiert.

Genau so hatte ich es ja vor. Bloß ich muss dazu ja vermutlich get/put eben an die Liste anpassen. Und bei den Vorbereitungen dazu bin ich schon hängengeblieben.

Gibt's das irgendwo schon halbfertig?

Aber mit den aktuellen Hinweisen bin ich dann schon mal ein Stück weiter. Danke an alle.

 

[Dit_]

Jetzt habe ich also mein simples Beispiel der HashMap-Nutzung an's Laufen bekommen. Doch diese konnte mit Kollisionen nicht umgehen.

Weil du die Methoden

hashCode()

und

equals(..)

nicht richtig implementierst. 😳
Wenn du Eclipse hast, lass die beiden Methoden generieren und schau ob du dann immer noch Kollisionen hast.

 

[fastjack]

@Dit die sind mit Absicht so, um Kollisionen zu erzeugen.

Ich würde eine eigene Klasse schreiben:

class HashMapWithBuckets<K, V> implements Map<K, V> {
    Map<K, List<V>> model = new HashMap<K, List<V>>; // List<V> ist dein Bucket, oder eine Buckets/Bag irgendwas-Klasse nehmen

    // alles was Du überschreiben willst, überschreiben, den Rest geeignet weiterleiten
    @Override
    public void put(K key, V value) {
        List<V> list = this.model.get(key);
        if (list == null) {
            list = new ArrayList<V>();
            this.model.put(key, list);
        }
        list.add(value);
    }

    public void put(V value) {
        this.put(t.hashCode(), value);
    }

    @Override
    public V get(K key) {
        List<V> list = this.model.get(key);
        if (list == null || list.size())  {
            return null;
        }
        return list.get(0); // ist nicht gut alle Elemente zurückzugeben, du mußt dir hier was geeignetes überlegen, oder halte den ersten zurückgeben
    }

}

so ähnlich halt
Von außen sieht das ganze jetzt aus schonmal aus wie eine Map.

Ein kleiner Tip noch: In die Buckets kommen Elemente mit gleichem Hashcode, das bedeutet aber nicht, das sie auch equals sind! Deine Equals-Methode muß richtig funktionieren (über alle relevanten Attribute eben). Der Hash-Code Kontrakt sagt nur, das zwei Objekte, die equals sind, den gleichen Hashcode haen sollen und der Hashcode bei mehrmaligem Aufrufen den gleichen Wert liefern soll. Wie vorhin gesagt, können zwei ungleiche Objekte den selben Hashcode haben.

edit: Dein Beispiel schildert den schlimmsten Fall, nämlich das viele Elemente denselben Hashcode haben, und die Elemente in den Buckets dann alle denselben Hashcode haben.