Java -> C++ / Hashmaps

[GO]

Hallo,

Ich suche gerade nach der besten Entsprechung für Java hashmaps in C++. Die stl hat ja eine Klasse map die, sowie ich das verstehe, baum basiert sucht. Dies ergibt natürlich eine schlechtere Laufzeit als hashmaps aber das wäre vermutlich nicht allzu tragisch... Ich habe halt als key integers und in eine map sollten dann einige tausend klassen wandern und schnellst möglich zu finden sein. Deshalb meine Idee hashmaps zu nutzen... Nun jedoch hab ich nichts dergleichen in C++ gefunden auch in boost/google hab ich erstmal nichts entdeckt. Deswegen meine Frage ob jemand vielleicht eine hashmap implementierung für c++ kennt oder eine gute Alternative / Würden maps auch reichen? Ansonsten werd ich mir wohl selber eine schreiben muessen :) - Ach ja und Thread safe soll das ganze nach möglichkeit auch schon sein.. wobei das erweitern net zu schwer wäre. Danke schon mal :P

[Sternmull]

Probier doch erst mal die std::map aus. Wenn sie die performance bringt die du für deine anwendung brauchts, dann nimm sie einfach und mach dir über die Dinge gedanken die du eignetlich entwickeln willst. Sollte sich herausstellen das die std::map nicht performant genug ist, dann (und wirklich erst dann) such nach einer Alternative. Ein paar Minuten mit Google dürften z.B. so etwas hervorbringen wie unordered_map und SparseHash.

[Matthias Gubisch]

Soweit ich weiß bietet auch QT sowas an.
Ob die Klasse allerdings Thread safe ist weiß ich ned auswenidig, müsstest selber nachschauen

[kimmi]

Je nach Compiler bietet die jeweils zugehörige STL eine eigene Hashmap mit aus. Und Boost hat ebenfalls eine Hashmap mit dabei. ich würde zu Boost raten:
http://www.boost.org/doc/libs/1_33_1/bo ... sh/map.hpp

Gruß Kimmi

[GO]

Okay danke leute...
Das werd ich mir dann mal anschauen :)

[nil]

Vieleicht eine dumme Frage,
aber warum sollte die std::map eine schlechtere Performance als eine Hashmap liefern wenn die Keys Integers sind? :?:

Ich hatte mir zwar selbst eine hashmap aus std::maps gebaut, aber nur um sie einzusetzen wenn ich strings als Key verwende.
Wo bei einem Integer Key der Performance Vorteil sein soll verschliesst sich mir hier.

[Chromanoid]

Weil eine HashMap zur Schlüssel/Wert-Suche eine Hash-Funktion benutzt und eine Map in STL

baum basiert sucht.

(Binärbaum)

Eine HashMap ist dadurch im Normalfall eher schneller, verbraucht aber auch mehr Speicher.
Eine Map arbeitet sich durch die Äste des Baums, während die HashMap eine Schlüssel-Position in einem Array berechnet und sofort dorthin springt.

[kimmi]

Wer es noch etwas detailierter wissen möchte:
Die std::map benutzt in der Regel bzw. oft einen sogenannten Rot-Schwarz-Baum: http://de.wikipedia.org/wiki/Rot-Schwarz-Baum . Der ist besser ausbalanciert als ein reiner Binärbaum, der im Worst-Case zu einer Linked-List werden kann.

Gruß Kimmi

[yonibear]

Eine HashMap ist dadurch im Normalfall eher schneller, verbraucht aber auch mehr Speicher.
Eine Map arbeitet sich durch die Äste des Baums, während die HashMap eine Schlüssel-Position in einem Array berechnet und sofort dorthin springt.

Du beschreibst eine Hashtable, eine Hashmap auch nur eine Baum-basierte Map die statt der Keys deren Hashes vergleicht.

[Chromanoid]

Eine HashMap ist dadurch im Normalfall eher schneller, verbraucht aber auch mehr Speicher.
Eine Map arbeitet sich durch die Äste des Baums, während die HashMap eine Schlüssel-Position in einem Array berechnet und sofort dorthin springt.

Du beschreibst eine Hashtable, eine Hashmap auch nur eine Baum-basierte Map die statt der Keys deren Hashes vergleicht.

Das ist für Java eine falsche Aussage.
In Java ist der Unterschied zwischen HashMap und HashTable lediglich, dass HashMap nicht threadsafe ist und "null" als Schlüssel zulässt. Hier ist eine SUN-Implementation der HashMap:
http://www.docjar.org/html/api/java/uti ... .java.html
Beide (Hashmap und HashTable) benutzen den hashCode der vom Schlüssel-Objekt zurückgegeben wird. In folgender Implementation wird dieser hashCode mit hash(int h) noch einmal transformiert, um diesen dann in der Schlüssel-Tabelle zu finden...
hash-Funktion

Code: Alles auswählen

  264       static int hash(int h) {
  265           // This function ensures that hashCodes that differ only by
  266           // constant multiples at each bit position have a bounded
  267           // number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }

get-Funktion

Code: Alles auswählen

  314       public V get(Object key) {
  315           if (key == null)
  316               return getForNullKey();
  317           int hash = hash(key.hashCode());
  318           for (Entry<K,V> e = table[indexFor(hash, table.length)];
  319                e != null;
  320                e = e.next) {
  321               Object k;
  322               if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
  323                   return e.value;
  324           }
  325           return null;
  326       }

  272       /**
  273        * Returns index for hash code h.
  274        */
  275       static int indexFor(int h, int length) {
  276           return h & (length-1);
  277       }

Erst wird eine Position in der Schlüssel-Tabelle berechnet, dann werden alle Schlüssel, die in dieser Tabellenzelle abgespeichert wurden, nacheinander geprüft. Man kann sich das ganze wie eine Art Aktenschrank vorstellen: Die Hash-Funktion berechnet eine Schublade in der man schauen muss und dann schaut man alle Akten in der Schublade durch. Im Optimalfall befindet sich immer nur eine Akte in je einer Schublade.

[GO]

Die STL bietet std::tr1::unordered_map als hashmap. Jedenfalls dort wo es bereits implementiert ist :)
http://msdn.microsoft.com/en-us/library/bb982522.aspx

[Sternmull]

Gratuliere. Du hast drei Tage gebraucht um etwas herauszufinden was ich dir in meiner Antwort geschrieben hab die ich keine drei Stunden nach deiner Fragestellung verfasst hab... Manchmal frag ich mich echt warum ich mir hin und wieder doch die Mühe mache und was in solchen Foren schreibe.

[knivil]

std::unordered_set ist fast genauso performant wie std::map. Wenn du wirklich Geschwindigkeitsvorteile gegenueber std::map suchst, dann nutze eine spezielle HashMap z.B. http://code.google.com/p/google-sparsehash/ (wie schon gepostet, findet man auch beim Suchen mit google im gamedev-Forum. Wenn es sich nur ein paar tausend Elemente handelt, dann braucht eine std::map etwa 10 Vergleiche, um das entsprechende Element zu finden (2^10 = 1024). Was normalerweise vertretbar ist. Bei Zweifeln hilft immer Testen und Messen.