Hashmap Capacity und Collision

[tobiw]

Hey,

hallo erstmal. Bin froh, dass ich dieses Forum gefunden habe.
Ich bin Einsteiger in Java und habe mich gerade etwas in collections eingelesen.

Ich muss für meinen Unikurs eine Klasse schreiben, die die Funktionalität eines Sets hat.
Ich darf allerdings die java library Set Klasse nicht verwenden.

Habe mir gedacht, dass ich eine Hashmap als Speicher verwende und die restliche Funktionalität drum rum programmiere.

Was genau würde passieren, wenn ich eine hashmap mit initialCapacity
HashMap<Integer,Object> hm = HashMap<Integer,Object>(100)
erstelle und diese capacity überschritten wird?
Beispielsweise wenn ich das 101. Object einfüge?

Gehen mir Daten verloren oder wird die HashMap automatisch vergrößert?

Außerdem muss mein eigengestricktes Set unterschiedliche Objecte speichern können.
Habe mir gedacht, dass ich immer die .hashCode() Funktion nehme und damit den unique hashkey erstelle.

Was aber, wenn mein Autoobject und mein Integer, welche ich beide in meine hashmap lege will, per .hashCode() den gleichen key produzieren?
Kann hashmap damit umgehen oder wie werden da collisions behandelt?

Viele Grüße

Tobi

 

[SlaterB]

ziemlich genaue Fragen, dafür dass du die Grundlagen etwa in der API oder in einem Lehrbuch nicht nachlesen willst?
Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 12 Datenstrukturen und Algorithmen

 

[Der Müde Joe]

Hash

>Gehen mir Daten verloren oder wird die HashMap automatisch vergrößert?

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

 

[FArt]

Habe mir gedacht, dass ich immer die .hashCode() Funktion nehme und damit den unique hashkey erstelle.

Das ist unnötig. Der Hash wird ja nur genommen, um das Objekt schnell zu finden. Für den Vergleich wird aber immer equals verwendet. Somit sind verschiedene Objekte (gleichen oder verschiedenen Typs) mit gleichem Hash immer ungleich.

 

[tobiw]

Hallo und vielen Dank für die schnellen Antworten.
Das letzte Kommentar hat mich etwas verwirrt.
Ich hatte mir das ganze ungefähr so vorgestellt.
Ist der Ansatz falsch?

public class DataStore extends HashMap<Integer, Object> implements DataStoreInterface{
	public DataStore(Integer length){
		super(length);
	}

	public void add(Object objectForInsertion) {
		//retrieve an object if there is one for the current key
		Object objectInHashMap = get(objectForInsertion.hashCode());
		
		if(objectInHashMap!=null && objectInHashMap.equals(objectForInsertion)){
			//do nothing, the same object is already in the hashmap
			
		}else if(objectInHashMap!=null && !objectInHashMap.equals(objectForInsertion)){
			//there is an object in the current position with the same hashkey,  
			//but it is not the same object that I try to insert (what now?)
			
		}else{
			//there is nothing in there, simply add the new object
			put(objectForInsertion.hashCode(),objectForInsertion);
			
		}
		
	}
}

 

[Marcinek]

Ich glaube nicht, dass es die Intention der Übung ist, wenn man SET nachproggen will dann eine andere Klasse zu nehmen, die ähnliche Eigenschaften hat, wie sein SET, nur dass die Einträge per Definition keinen Vorgänge und keinen Nachfolger haben.

Ich denke du solltest begreifen, was ein SET ist und dies selbst implementieren. Dazu würde ich eine LinkedList implementieren, die ein Objekt nur einmal aufnimmt.

Eine LinkedList würde ich implementieren indem ich ein Objekt habe, was auf einen Nachfolger zeig. Also ganz plain.

Gruß,

Marcinek

 

[Gelöschtes Mitglied 5909]

@Marcinek:
Ein Set bzw. genauer ein HashSet ist aber etwas anderes als eine LinkedList, die ein Objekt nur einmal aufnimmt.
Und eine LinkedList ist um ein vielfaches langsamer als ein HashSet, wenn du Set-typische operationen wie contains aufrust.

ALso am besten nochmal

Bei einer LinkedList muss im schlimmsten fall über die ganze Liste iteriert werden. Bei dem HashSet wird der hash berechnet und dann ist man im normalfall schon da (wenn keine kollision vorhanden ist)


Ich würde eine ArrayList implementieren, die intern in dem Set verwendet wird (wegen den Kollisionen).

Hash modulo capacity = array-index


und da dadurch kollisionen entstehen können, verwendest du dann intern ein array von Listen

dasarray "für das hashen", die liste für die kollisionen

oder eben eine liste von listen

 

[Marcinek]

@raiL

ich habe nochmal :rtfm: und habe das gefunden:

insel:

Die Schnittstelle Set für Mengen

Ein Set ist eine im mathematischen Sinn definierte Menge von Objekten. Wie von mathematischen Mengen bekannt, darf ein Set keine doppelten Elemente enthalten. Für zwei nicht identische Elemente e1 und e2 eines Set-Objekts liefert der Vergleich e1.equals(e2) also immer false. Genauer gesagt: Aus e1.equals(e2) folgt, dass e1 und e2 identische Objekt-referenzen sind, sich also auf dasselbe Mengenelement beziehen.

In der Aufgabenstellung hies es: Implementieren Sie ein SET. Nicht implementieren Sie ein SET mit optimalen Laufzeiten.

Selbst wenn es optimale Laufzeizeiten haben sollte, so würde sich statt eines closed hasing ein open Hashing besser eigenen, wie das Brent-Hashing. Wobei man das bei ~ 100 Elementen ehh imho vernachlässigbar ist.

 

[FArt]

Die Oracle Implementierung eines HashSets ist die HashMap. So hätte ich es auch gemacht. Eine LinkedList ist sicher unpraktisch. Natürlich gibt es für andere Bereiche andere Sets, die von der Datenstruktur anders aufgebaut sind und auch Vorteile (und Nachteile) bieten, je nach Verwendung.

Für den TS:
Das Objekt ist sein eigener Schlüssel. Da musst du nicht künstlich einen erzeugen. Wenn das Objekt schon vorhanden ist (kann man überprüfen mit contains) dann darst du es halt nicht einfügen.
Die Hashes werden von den Objekten selber gebildet und equals wird auch von den Objekten selber geprüft. Fertig, ohne besonderen Aufwand. Objekte mit unterschiedlichen Hashes werden schnell als ungleich angenommen, Objekte mit gleichen Hashes werden halt noch auf equals geprüft. Dass hashCode() und equals() immer konsistent und sinnvoll implementiert ist, davon darf man ausgehen.