Collections Performance einer HashMap

[rewireable]

Hallo,

ich lese Daten aus einer Datenbank in eine Hashmap. Der Key der Map ist dabei vom Typ Long der Value irgendein Objekt.

nun kommen mir folgende Fragen:

Die LongWerte sind alle relativ nahe beinander, ich befürchte deshlab dass es zu kollisionen kommt. Kann ich bei HashMap irgendwie festestellen wie gut sie ausbalanciert ist? Falls sie es nicht ist, was wären meine möglichkeiten eine besserer balance herzustellen? Die hashCode() Methode von Long kann ich ja kaum überschreiten. Und mit der Kapazität der HashMap ins unendliche ausweichen ist ja auch nicht optimal. - Aber jetzt muss ich erst mal wissen, ob ich überhaupt ein problem hab, wie analysiert man eine hashmap also?

vielen Dank für hilfe

stefan

 

[Marco13]

Man könnte mal schauen, ob man zum Testen(!) irgendwelche Methoden überschreiben kann, damit man mitkriegt, wann es einen rehash gibt. Aber eigentlich sollten "dicht beienander liegende" Longs kein Problem sein: Was "besseres" als aufeinanderfolgende Werte von 0...100 als Schlüssel zu verwenden gibt es ja nicht ("besser" wäre da nur - ein Array ). Es gibt auch Bibliotheken, die HashMaps anbieten, die Explizit einen "long" als Key verlangen. Das könnte einen Tick schneller sein, weil man sich das Boxing evtl. spart (websuche, "trove" ist recht bekannt aber gerade down, es gibt sicher noch andere).

Wichtiger wäre aber erstmal die Frage: Ist DAS wirklich der Bottleneck?

EDIT: Ah - http://www.java-forum.org/ides-tools/124660-suche-java-profiler.html , dann kannst du das herausfinden

 

[Dit_]

ich glaube die HashMap sorgt dafür, dass es nicht zu viele Kollisionen gibt, sprich, wenn es zu viele Kollisionen gibt, wird die Map vergrößert und reorganisiert. Außerdem hashcode ist ja nicht alles, Index wird ja noch (stark vereinfacht(!)) durch Modulo erzeugt.

 

[Wildcard]

Wie Marco13 sagt, wenn du wirklich denkst die Map ist der Bottleneck, dann solltest du eine Primitive Map verwenden.
Colt soll eine der schnellsten sein:
Colt - Welcome

 

[bERt0r]

Selbst wenn deine HashMap voll mit Kollisionen ist, hast du "nur" eine Zugriffszeit von o(n). Solltest du diesen extrem unwahrscheinlichen Fall mit deinem Programm regelmäßig erzeugen können, kannst du ja auch einfach eine TreeMap nehmen.
Wie bereits gesagt wurde, ist die Hashmap aber sicher nicht der Grund warum du anscheinend auf Performanceschwierigkeiten stößt, weil Hashmaps so ziemlich die schnellsten Maps sind.
edit: ach ja, Hash-Funktionen sind hash-funktionen, weil sie eben genau bei Input mit minimalen Unterschieden auch unterschiedlichen Output generieren.

 

[Wildcard]

Wie bereits gesagt wurde, ist die Hashmap aber sicher nicht der Grund warum du anscheinend auf Performanceschwierigkeiten stößt, weil Hashmaps so ziemlich die schnellsten Maps sind.

Nein, pauschal kann man das so nicht sagen. Ich habe auch Fälle mit vielen Millionen Map Zugriffen für primitivwerte und das Autoboxing macht da durchaus einen Unterschied.
Wichtig ist aber bei Optimierungen zuerst den Bottleneck zu bestimmen und dann zu optimieren, sonst bringt das nichts.
Wenn das identifizieren schwierig ist, hilft es auch Benchmarks mit zB Japex zu erstellen und dann nach und nach Einzelteile der Implementierung auszutauschen und mit den Referenzwerten zu vergleichen.

 

[musiKk]

Selbst wenn deine HashMap voll mit Kollisionen ist, hast du "nur" eine Zugriffszeit von o(n).

Auch wenn das "nur" in Anführungsstrichen steht: Das wäre ein ziemlicher GAU.

Wenn man sich die Definition der Long#hashCode() anschaut, dann sieht man auch, dass es für nahe liegende Werte bis 2^32 - 1 garantiert keine Kollision geben kann. Danach fangen die Werte an, sich zu wiederholen; Kollisionen sind aber immer noch unwahrscheinlich (meine Vermutung ist, dass es bei Long maximal 32 Kollisionen geben kann; der Beweis ist eine Aufgabe an den Leser).

Das ganze gemutmaße ist aber sowieso für die Katz, wenn die Performance gar nicht schlecht ist. Ist denn überhaupt schonmal gemessen worden? Sieht bisher nicht danach aus. Es ist nichtmal klar, ob die Map überhaupt so viele Werte enthalten soll, dass sich der Aufwand einer Primitiv-Map lohnt. Wenn die Map Tausend Werte aufnehmen soll und nicht viel manipuliert wird, wird das Autoboxing nicht viel ausmachen.

 

[kirdie]

Die LongWerte sind alle relativ nahe beinander, ich befürchte deshlab dass es zu kollisionen kommt.

Ich glaube du hast nicht ganz verstanden was eine Hashfunktion ist.
Eine gute Hashfunktion zeichnet sich gerade dadurch aus, dass auch naheliegende Werte einen extrem unterschiedlichen Hashwert haben.

 

[ice-breaker]

Auch wenn das "nur" in Anführungsstrichen steht: Das wäre ein ziemlicher GAU.

ich denke mal, dass er mit n die Bucketgröße meint, also die Anzahl an Datensätzen, die alle auf einen Hash gemappt und dann linear verbunden werden.
Und da ist ein O(n) dann wirklich alles andere als schlecht.

meine Vermutung ist, dass es bei Long maximal 32 Kollisionen geben kann; der Beweis ist eine Aufgabe an den Leser

Wenn ich 64 Bit auf 32 Bit abbilde, habe ich aber eine ganze Menge Kollisionen.
Wenn ich mich gerade nicht ganz irre gibt es 2^32 - 1 Kollisionen. Da es für jeden der 32 Bit Werte wiederum die 32 Bit Kollisionen im Bereich gibt, der den Int-Wert überschreitet.
Kann mich auch gerade irren, aber es sind schon eine ganze Menge an Kollisionen. Aber nichts destotrotz ist das ja irrelevant solange man nicht alle Long-Werte in einer HashMap abspeichern will.

 

[Wildcard]

Wenn die Map Tausend Werte aufnehmen soll und nicht viel manipuliert wird, wird das Autoboxing nicht viel ausmachen.

Unter Umständen schon, denn tausende gets, oder contains führen auch zu Autoboxing. Ich hab die Zahlen nicht mehr genau im Kopf, aber für meinen Use Case war meine selbstgeschrieben primitiv Map ca. 30% schneller als eine HashMap. Auf die Gesamtlaufzeit des Vorgangs waren das zwar nur wenige Prozentpunkte, aber Performance war an dieser Stelle sehr wichtig.

 

[musiKk]

Eine gute Hashfunktion zeichnet sich gerade dadurch aus, dass auch naheliegende Werte einen extrem unterschiedlichen Hashwert haben.

Ich habe das Gefühl, viele denken bei "Hashfunktion" and kryptographische Hashfunktionen für die diese Eigenschaft gelten sollte. Das muss nicht unbedingt auf allgemeine Hashfunktionen übertragen werden.

Wenn ich 64 Bit auf 32 Bit abbilde, habe ich aber eine ganze Menge Kollisionen.

Tralli tralla. Guck mal da hinten, ein Zirkus! *weg*

Unter Umständen schon, denn tausende gets, oder contains führen auch zu Autoboxing. Ich hab die Zahlen nicht mehr genau im Kopf, aber für meinen Use Case war meine selbstgeschrieben primitiv Map ca. 30% schneller als eine HashMap. Auf die Gesamtlaufzeit des Vorgangs waren das zwar nur wenige Prozentpunkte, aber Performance war an dieser Stelle sehr wichtig.

Das stimmt natürlich. Ich wollte eigentlich auch mehr darauf hinaus, dass man ohne Messungen und ohne die Umstände zu kennen kaum Aussagen treffen kann. Schon gar nicht mit den limitierten Daten, die aus dem ersten Post hervorgehen. Soviel ich weiß kann die Map sogar nur zwei Einträge enthalten.

 

[rewireable]

erstemal vielen Dank für alle euren Antworten.

wie in meinem OP genannt, weiss ich nicht ob meine Map gut ausbalanciert ist. Mir ist immer noch nicht klar wie ich das herausfinden kann, also jetzt nicht indirekt durch performancetests. Ich dachte eher an sowas ähnliches wie eine (leider nicht vorhandene) Methode int HashMap.getCollisionsCount()

In meinem konkreten Beispiel hat die Maps > 100.000 Einträge.

hier ein auszug von real verwendeten long Werten und deren HashCodes:

LongWert: 200000141186 -> HashWert -1863321684
LongWert: 200000142026 -> HashWert -1863320860
LongWert: 200000141800 -> HashWert -1863321146
LongWert: 200000143871 -> HashWert -1863319087
LongWert: 200002128140 -> HashWert -1861334750
LongWert: 200002128239 -> HashWert -1861334719
LongWert: 200002128505 -> HashWert -1861334441
LongWert: 200000138530 -> HashWert -1863324404
LongWert: 200000142107 -> HashWert -1863320779
LongWert: 200000143028 -> HashWert -1863319910
LongWert: 200002128267 -> HashWert -1861334619
LongWert: 200000143844 -> HashWert -1863319094
LongWert: 200000140898 -> HashWert -1863322036
LongWert: 200002128654 -> HashWert -1861334240
LongWert: 200002128751 -> HashWert -1861334207
LongWert: 200000139084 -> HashWert -1863323806

Die Long Werte befinden sich alle in der gleichen größenordnung und die Hashwerte dazu auch. Das ist ja auch kein wunder, die hash Funktion von Long sieht ja wie folgt aus

(int)(this.longValue()^(this.longValue()>>>32))

direkte kollision, d.h. dass der gleiche hsh wert berechnet wird sind also erstmal nicht zu befürchten. Jetzt ist mir aber unklar wie die Hashmap das intern macht.
Es gibt ja 2^32 mögliche hashWerte. Eine Hashmap mit sagen wir mal 2^10 Buckets muss also 2^22 Hashwerte in den gleichen Buckets zusammenwerfen. Hier ist jetzt die große Frage: Welche sind das? Wenn es immer die direkt aufeinanderfolgenden sind, hab ich ein Problem. Wenn der darauffolgen Wert immer in den nächsten Bucket kommt, und falls es keinen solchen gibt erst wieder in den ersten, dann hab ich kein Problem. Aber das weiss ich nicht, genau das will ich ja herausfinden!

 

[Marco13]

AFAIR verwendet HashMap intern nochmal einen Trick, um die hashCodes zu "verbessern", aber das ist nur ein Detail. Wenn man von der einfachsten Hashfunktion ausgeht (also eine Table mit der Größe einer Primzahl, und der HashCode wird einfach mit Modulo da reingemappt), dann kann man sich an einem kleinen Beispiel überlegen, was passiert:

Tablegröße 13
hashCode 0 -> Index 0
hashCode 1 -> Index 1
...
hashCode 12 -> Index 12
hashCode 13 -> Index 0

D.h. erst beim 13. aufeinanderfolgenden Wert KÖNNTE theoretisch eine Kollision auftreten - AAAABER in der Praxis passiert nicht mal das, weil vorher die HashTable vergrößert wird!

Geh' einfach davon aus, dass Kollisionen kein Problem sind, und wenn du das nicht glaubst, kopier' dir den Code von HashTable, nenne es "MyHashTable", und mach' Debug-Ausgaben, an denen du erkennst, ob es wirklich Kollisionen gibt....

 

[bygones]

Geh' einfach davon aus, dass Kollisionen kein Problem sind, und wenn du das nicht glaubst, kopier' dir den Code von HashTable, nenne es "MyHashTable", und mach' Debug-Ausgaben, an denen du erkennst, ob es wirklich Kollisionen gibt....

um debug maessig in SDK code rumzufurchen braucht man nicht den code kopieren.. du kannst auch in den SDK code von deinem code "huepfen".

ok - wenn du natuerlich debug ausgaben machen willst... *cola suchen*

 

[fastjack]

Bau doch erstmal Zeitmessungen an bestimmte Stellen in Dein Programm ein, dann weist Du schinmal direkt wo es länger dauert und wo nicht.

 

[rewireable]

hier ein paar ergebnisse von hprof:

-> ich sehe also, dass mein problem weniger an der hashmap liegt die als key ein Long hat, sondern vielmehr die die als key einen String hat.

die Strings sind alle zwischen 3 und 4 buchstaben lang


Platz 1 und 2 Stammen aus einem anderen Thread, hier die folgenden

3 5.01% 71.65% 1441890 302400 java.lang.String.equals
4 2.71% 74.37% 781319 302424 java.util.HashMap.get
5 2.58% 76.95% 742957 302402 java.util.HashMap$HashIterator.<init>

und hier die traces dazu:

TRACE 302400: (thread=200001)
java.lang.String.equals(String.java:1018)
java.util.HashMap.get(HashMap.java:305)

TRACE 302424: (thread=200001)
java.util.HashMap.get(HashMap.java:305)

TRACE 302402: (thread=200001)
java.util.HashMap$HashIterator.<init>(HashMap.java:783)
java.util.HashMap$KeyIterator.<init>(HashMap.java:826)
java.util.HashMap$KeyIterator.<init>(HashMap.java:826)
java.util.HashMap.newKeyIterator(HashMap.java:840)
java.util.HashMap$KeySet.iterator(HashMap.java:874)
java.util.HashSet.iterator(HashSet.java:153)

 

[rewireable]

Hm, die Ergebnisse meiens letztn Posts wundern mich schon sehr.

Ich hab vorhin überprüft dass die verwendeten Strings in den keys eindeutig bezüglich des Hashcodes sind, d.h. keine 2 von mir verwendeten keys ergeben den gleichen hashcode.

wie ist es dann möglich dass sooft equals aufgerufen wird?

für unterschiedliche Strings müsste doch der hashcode bereits unterscheiden, und bei gleichen sollte doch im normalfall der == vergleich schon erfolgreich sein.

Ich würd mir die Stelle gern mal im Quellcode anschauen, kann mir jemand sagen wo ich den Quellcode zur Hashmap Klasse finden kann?

 

[rewireable]

ok, ich hab den relevanten code gefunden, und zwar hier:
http://download.java.net/jdk6/6u23/promoted/b05/jdk-6u23-fcs-src-b05-jrl-12_nov_2010.jar


[JAVA=297]
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

[/code]

es wird also tatsächlich in zeile 305 ein equals aufgerufen, aber nur wenn haswerte gleich sein und == vergleich fehlschlägt. Wieso hab ich soviel verschiedenene String Objekte mit gleichem text?

 

[schalentier]

die Strings sind alle zwischen 3 und 4 buchstaben lang

Wenn die Strings niemals laenger als 4 Buchstaben (Welche? Auch Buchstaben die aus mehreren Bytes bestehen koennen?) werden, koennte man das in einen long umwandeln und diesen als Key nehmen. Evtl. kann man so noch was rausholen (auch in Verbindung mit Colt, siehe Wildcard oben).

 

[faetzminator]

Natürlich könntest du mit [c]intern()[/c] arbeiten, dass du immer die gleichen String-Objekte hast. Siehe String (Java Platform SE 6). Aber da werden beim Aufruf von [c]intern()[/c] auch nur die gepoolten Strings per [c]equals()[/c] mit dem aktuellen String verglichen. Das lohnt sich also nur, wenn du den String x-fach weiterverwendest.

 

[Wildcard]

Equals kannst du umgehen wenn du eine IdentityHashMap verwendest, dann müssen die Strings aber auch immer die gleiche Instanz sein.
String#equals wird vor allem dann teuer, wenn du viele Strings gleicher Länge mit ähnlichem Inhalt hast.

 

[Marco13]

Equals kannst du umgehen wenn du eine IdentityHashMap verwendest, dann müssen die Strings aber auch immer die gleiche Instanz sein.

Da dachte ich zuerst auch dran - bin aber nicht sicher, ob man diese Anforderung einhalten kann...

String#equals wird vor allem dann teuer, wenn du viele Strings gleicher Länge mit ähnlichem Inhalt hast.

Hab' gerade mal geschaut: Es ist ja tatsächlich so, dass der hashCode jedes mal neu ausgerechnet wird, obwohl Strings immutable sind, und er eigentlich direkt im Konsruktor ausgerechnet werden könnte - dann könnte man den equals-Vergleich nämlich durch ein
if (this.finalHashCode != other.finalHashCode) return false;
ggf. drastisch (!) beschleunigen...!?

 

[musiKk]

Da dachte ich zuerst auch dran - bin aber nicht sicher, ob man diese Anforderung einhalten kann...

Wenn man strikt nur internierte Strings benutzt, dann schon.

Hab' gerade mal geschaut: Es ist ja tatsächlich so, dass der Hashcode jedes mal neu ausgerechnet wird, obwohl Strings immutable sind

Verrückt. Welche Bibliothek benutzt Du? Bei der Standardbibliothek im Oracle JDK wird der hashCode lazy berechnet und dann gecached.

Den [c]equals()[/c]-Vergleich nach Deinem Vorschlag abzukürzen wäre sicher denkbar. Das sind halt die typischen Probleme, mit denen man sich herumschlägt, wenn man General-Purpose-Bibliotheken schreibt. Passiert es häufiger, dass die Strings schon ab dem ersten Zeichen unterschiedlich sind? Dann verliert man durch den vorherigen Hashcode-Vergleich evtl. Zeit usw.

 

[Wildcard]

Wenn man strikt nur internierte Strings benutzt, dann schon.

Für die meisten Fälle würde ich lieber einen eigenen String Pool verwenden. Die internierten Strings liegen sonst bis in alle Ewigkeiten im Heap. Mit eigenem Pool hat man zumindest Kontrolle über den Scope. Andererseits verwendet man dafür normal eine Hashmap womit wir beim alten Problem wären

 

[Marco13]

Bei der Standardbibliothek im Oracle JDK wird der hashCode lazy berechnet und dann gecached.

Hu, nochmal schauen, vielleicht hab' ich da was verpeilt...

Der Vergleich... Naja... ist höchstens EIN Vergleich (zwar bei jedem Aufruf, aber) die Anzahl der möglicherweise gesparten Vergleiche ist nicht nach oben beschränkt...

 

[Ark]

(Eigentlich hatte ich vor, eine etwas anschaulichere Erklärung zu geben, aber irgendwie ist es doch bei einer eher wissenschaftlich angehauchten geblieben. )

Es gibt einen interessanten Zusammenhang zwischen der Größe einer Hashtabelle, der Verteilung der Hashcodes und der Performance: Wenn alle Hashcodes der Elemente modulo k in die gleiche Restklasse fallen, dann verteilen sich diese in einer Hashtabelle der Größe m derart, dass sie nur m / ggT(k, m) Plätze zur Auswahl haben.

Beispiel: Alle Elemente haben nur gerade Hashcodes, d.h. k = 2, und für alle Hashcodes h gilt: h ≡ 0 (mod 2). Sei m = 12. Dann müssen sich alle diese Hashcodes 12 / ggT(2, 12) = 12 / 2 = 6 Plätze teilen, obwohl die Hashtabelle 12 Einträge aufnehmen könnte. Die anderen 6 Plätze (und auch nur diese!) könnten dann die ungeraden Hashcodes bekommen.

Kleinere Hashtabellen müssen diesbezüglich aber nicht schlechter als größere sein. So sieht die Rechnung für k = 2 und m = 11 interessanter aus: 11 / ggT(2, 11) = 11 / 1 = 11. Das heißt, selbst wenn nur gerade Hashcodes reinkommen (weil vielleicht die Hashfunktion dumm ist oder man gerade Pech mit der Eingabe hat), besteht bei einer Hashtabelle mit 11 Plätzen tatsächlich die Möglichkeit, dass auch alle diese 11 Plätze überhaupt belegt werden können.

Dass das bei m = 11 in solchen Fällen so gut klappt, liegt daran, dass diese Zahl teilerfremd zu k = 2 ist. Will man also eine Hashtabelle bezüglich ihrer Größe möglichst gut ausnutzen, muss man dafür sorgen, dass m generell möglichst wenige Primfaktoren und im Speziellen gar keine mit k gemeinsam hat. Dies erreicht man wohl am ehesten damit, dass man für m nur Primzahlen zulässt, denn diese sind bis auf k≡m≡0 (mod m) garantiert teilerfremd zu k.

Ark

 

[hdi]

Hier mal ein (bewusst übertriebenes) Beispiel damit du den Unterschied siehst. Führe das Programm aus, ändere die hashCode()-Implementierung (Kommentar einfügen und altes return rausnehmen) und führe es erneut aus.

public class HashTestElement {

	private int x;
	private int y;
	private int z;

	public HashTestElement(int x, int y, int z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}

	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof HashTestElement)) {
			return false;
		}
		HashTestElement e = (HashTestElement) obj;
		return e.x == this.x && e.y == this.y && e.z == this.z;
	}

	@Override
	public int hashCode() {
		return x+y+z;
		//return 31*x +60* y + (z*x) -99;
	}
}

public class HashPerformanceDemo {

	public static void main(String[] args) {

		HashTestElement[] elements = new HashTestElement[100000];
		Random r = new Random();
		for (int i = 0; i < elements.length; i++) {
			int x = r.nextInt();
			int y = r.nextInt();
			int z = -(x + y);
			if (x + y + z != 0) {
				throw new IllegalStateException();
			}
			elements[i] = new HashTestElement(x, y, z);
		}

		Set<HashTestElement> set = new HashSet<HashTestElement>();

		long start = System.currentTimeMillis();
		for (HashTestElement e : elements) {
			set.add(e);
		}
		for (HashTestElement e : elements) {
			set.contains(e);
		}
		for (HashTestElement e : elements) {
			set.remove(e);
		}
		long end = System.currentTimeMillis();
		System.out.println("Benötigte Zeit: " + (end - start) / 1000.0
				+ " Sekunden");
	}

}