HashMap keySuche

[fco]

Hallo Java Freunde,

wieder einmal brauche ich eure Hilfe.

ein Java Programm erzeugt ein Key->Value in Form ein HashMap<String,HtmlAnchor>. Nach jeder durchlauf wird geguckt ob in der Hashmap diese key existiert. Bei etwa 20.000 elementen wird der suche natürlich sehr langsam.

was kann man dagegen machen? gibt andere Mehtoden?


vielen Dank im Voraus

 

[nrg]

also 20.000 elemente sollten da jetzt kein problem darstellen. was meinst du mit "nach jedem durchlauf"?

 

[Der Müde Joe]

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

HashMap (Java Platform SE 6)

 

[tfa]

Wenn man weiß, dass man viele Objekte in der Tabelle abspeichern will, sollte man gleich die Anfangsgröße entsprechend wählen ( z.B. 27000 bei 20000 Einträgen). Das Reshashing.

 

[Dekker]

Wenn man weiß, dass man viele Objekte in der Tabelle abspeichern will, sollte man gleich die Anfangsgröße entsprechend wählen ( z.B. 27000 bei 20000 Einträgen). Das Reshashing.

Hat ja jetzt wenig mit dem suchen zu tun. Beim einfügen und löschen ist das interessant. Ich denke allgemein wäre es interessant zu wissen was du mit einem Durchlauf meinst. Außerdem wäre es interessant zu wissen ob du eine eigene Hashfunktion benutzt etc pp. Wenn diese nicht stark genug kollisionsresistent ist, degeneriert eine Hashtabelle irgendwann zu einer Liste da der Probingalgorithmus dann oft lange suchen muss bis er den richtigen Eintrag hat.

 

[Andi_CH]

Was heisst lange? Bei 2'000'000 Einträgen braucht nicht einmal mein searchDoof spürbar Zeit
und hm.containsKey(key) ist ja sicher schneller
(Hm - ich glaub es ist Zeit für die Mittagspause, sonst komme ich auf noch doofere Ideen)

	private static void searchDoof(String key) {
		// doofere als doofe Variante
		String antwort = "Ist nicht drin";
		for(String s : hm.keySet()) {
			if(s.equals(key)) {
				antwort = "Ist drin";
			}
		}
		System.out.println(antwort);
	}

 

[fco]

vielen Dank für die rasche Antwort. die funktion siehr so aus.

//hier wird alle anchors aus eine HTML Datei ausgelesen//
TreeMap<String,HtmlAnchor> anchorListe=crawler.getAnchorListe();
for(String key:anchorListe.keySet()){
	HtmlAnchor anchor=anchorListe.get(key);
             //hier wird nach vorhandene anchors in der cache gesucht.
             String key=new MD5().md5(anchor.asXml());
	if(_cache.containsKey(key)){
	    this._cache.put(key, anchor);
	}
}

diese Funktion wird rekursive aufgerufen.

 

[Der Müde Joe]

for(String key:anchorListe.keySet()){
    HtmlAnchor anchor=anchorListe.get(key);

Das macht keinen Sinn. Iteriere über das EntrySet.

containsKey und put ist linearer aufwand.

Aber wenn du über 20'000 Einträge iterierst und dann noch rekursiv ein paar mal....

EDIT:
ach ja..TreeMap wäre übrigens

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations

 

[fco]

@Der Müde Joe: wie sieht dein vorschlag aus?

 

[SlaterB]

der Code ist so wie er ist gut, jedenfalls hinsichtlich Map-Durchlauf und Key-Prüfung,
eine MD5-Berechnung dauert vielleicht länger als die 20.000 Keys zu durchlaufen,
na gut, das wohl nicht, aber von dem Code macht MD5 doch sicher 95% der Zeit aus,
wenn Zeile 7-9 auskommentiert werden, dauert das ganze dann nicht noch genauso lange?

Rekursion ist nicht zu erkennen

----

edit:
ein Key einer Map, den man erst jedesmal aufwending mit MD5 berechnen muss, ist vielleicht für sich diskussionswürdig,
die HashMap kann doch gerade den HashCode eines Strings ausrechnen, reicht das nicht?
ist vielleicht schneller als erst MD5 und dann HashCode?
um Platz musst du dir keine Sorgen machen, jeder Key ist nur 4 Byte, eine Referenz auf den Arbeitspeicher,
die langen XML-Strings sind sowieso im gespeicherten Anchor vorhanden, oder erstellt .asXml() diese erst?

edit:
werden die Keys der anchorListe (= eine Map??) überhaupt benötigt? wenn es dieselben wie für _cache sind, dann direkt verwenden statt neu auszurechnen?
wenn nicht benötigt, kann in der Tat diese Schleife geändert werden, nur über die values() iterieren,
über das EntrySet zu iterieren und dort die Keys + Values rauszuholen ist dagegen eher unschön zu schreiben, muss nicht unbedingt sein

 

[fco]

ich kann das leider nicht bestätigen. Da am anfang die durchläufe sehr schnell gehen, aber mit der zeit wird die durchläufe immer langsamer. Ich muß noch viel lernen :rtfm:

 

[SlaterB]

> ich kann das ledier nicht bestätigen.
bezieht sich das auf meine Frage zur Laufzeit mit Auskommentieren?
dann ist die Antwort nicht sehr hilfreich, meinst du dass es schneller wird (was doch auf ein Problem mit der Key-Suche hindeuten würde), dass sich die Zeit nicht ändert, dass du den Code nicht ändern kannst oder einfach nicht weißt was ich meine bzw. die Messung zu schwer umzusetzen ist? na auch nicht wichtig

ich hab in mein letztes Posting noch zwei edits eingebaut, falls interessiert

 

[fco]

@slaterB:

vielen vielen Dank für den Hinweis. Ich dachte keyLänge ist auch Speicherlänge. Dann ändere ich den Code.