Hash-Maps in C++

[snoopysalive]

Hallo!

Mich hätt's interessiert, ob es für C++ auch Hash-Maps gibt. In Java sind sie ja schon per Standard enthalten und in Perl, Ruby usw. sowieso. Wie sieht's denn nun mit C++ aus?

Aus den Ergebnissen der Suchfunktion hier wurde ich nicht sonderlich schlau, denn dort wird immer nur auf die sortierte <map> hingewiesen, um jemandem die Hashes auszureden. Ich finde die <map> ja okay, aber ich will Hashes benutzen können und wäre für Links, Tipps, Hinweise usw. sehr dankbar.

Gruß,
Matthias

 

[Matthias Reitinger]

Hallo,

die STL stellt hier soweit ich weiß keinen entsprechenden Datentyp bereit. Es gibt aber herstellerabhängige Erweiterungen zur STL, die einen Typ hash_map anbieten.

Im Falle der GCC-STL sähe das ungefähr so aus:

#include <ext/hash_map>
#include <iostream>
#include <string>

using namespace __gnu_cxx;

struct eqstring {
    bool operator()(std::string a, std::string b) const {
        return a == b;
    }
};

namespace __gnu_cxx {
    /* Simple Hashfunktion für Strings */
    template<> struct hash<std::string> {
        size_t operator()(std::string s) const {
            size_t hsh = 0;
            for (std::string::iterator it = s.begin(); it != s.end(); it++)
                hsh = 31*hsh + (size_t)(*it);
            return hsh;
        }
    };
}

typedef hash_map<std::string, int, hash<std::string>, eqstring> string_int_hash_map;

int main() {
    string_int_hash_map mymap;

    mymap["foo"] = 12;
    mymap["bar"] = 34;

    std::cout << mymap["foo"] << std::endl; // => 12
    std::cout << mymap["bar"] << std::endl; // => 34

    return 0;
}

Grüße,
Matthias

 

[higret]

Hi

aber der Datentyp map aus der STL ist doch dafür da

#include <map>
#include <string>
#include <iostream>

int main() {
   std::map<std::string, int> string_int_hash;

   string_int_hash.insert(std::make_pair("foo", 200) );
   string_int_hash["bar"] = 12;

   std::cout << "foo:" << string_int_hash["foo"] << std::endl;
   std::cout << "bar:" << string_int_hash["bar"] << std::endl;
   
   return 0;
}

ob jetzt sortiert oder nicht ist doch im Endeffekt egal, solange man mit Hashed draufzugreift

mfg

 

[snoopysalive]

Danke schon mal euch beiden. Ich werde mir die Lösungen mal zu Gemüte führen.

@higret:
Mir geht's halt darum, dass es doch immer heißt, Hashes seien zugriffsoptimiert, also schneller als normale Container. Daher mein Interesse an Perl/Ruby-ähnlichen Hashes.

 

[Matthias Reitinger]

ob jetzt sortiert oder nicht ist doch im Endeffekt egal, solange man mit Hashed draufzugreift

Was meinst du mit „Hashed draufzugreift“? Bei einer map kommt kein Hashing zum Einsatz (wie auch, man übergibt ja keine Hashfunktion). In den meisten Implementationen wird stattdessen ein Rot-Schwarz-Baum verwendet.

Grüße,
Matthias

 

[Endurion]

Die HashMap ist bei den meisten aktuellen Compiler schon drin, allerdings noch nicht offiziell im std namespace. Versuch mal:

stdext::hash_map für Visual Studio

 

[snoopysalive]

Ich kann die Bibliothek <ext/hash_map> einbinden. Weil sich die aber ad hoc nicht so verwenden lässt, wie eine normale <map>, stellt sich mir jetzt die Frage, ob man zu jeder Hash-Map, die man anlegt, eine Hashfunktion schreiben muss, wie es higret in seinem Post macht? Gibt's da irgendwelche Lektüre oder Webtutorials, die einem erklären, wie man Hashes programmiert?