Wie geht "Hashmap programmieren"?

Trollcrew

Wie geht's? Kennt ihr da gute Tutorials oder Beschreibungen zu? Über google finde ich nur Mist.

Griffin

Frag doch einfach mal MrN! :p

*rofl* der war mal lustig... (insiderwitz)

Trollcrew

MrN: Wie geht's?

Griffin: Den hab ich jetzt auch verstanden. *snif*

[ Dieser Beitrag wurde am 30.12.2002 um 21:02 Uhr von Happy Birthday editiert. ]

Mr. N

Griffin: du bist ja mal gut drauf *fg*. Man könnte fast meinen... ach, ich wollte ja nicht so sarkastisch sein :p

Happy Birthday: Hol dir n gutes Buch *g*. Generell sieht es so aus, dass du versuchst, eine große Menge Schlüssel auf eine kleine Zahlenmenge abzubilden, für deren Entitäten du jeweils eine Linked-List hast *fg*. Schau dir das an:

int hash(const char *s) {
  int r = 0;
  while (*s) 
    r = 31 * r + *s++;
  return r % 101;
}

Volkard würde wahrscheinlich erstmal protestieren ist jetzt aber egal. hash("bla") liefert dir jetzt eine Zahl zwischen 0 und 101. Nehmen wir an, du hast eine Klasse linked_list in der du alles Nötige speichern kannst. Dann hast du:

linked_list ht[101];

Und wann immer du etwas in die map einfügen willst, fügst du es hinten an ht[hash(x)] an - und findest es durch Durchsuchen von ht[hash(x)]. Entweder hast dus jetzt geblickt oder nicht :D.

Trollcrew

Danke MrN. für die Antwort!

Hol dir n gutes Buch *g*.

Welches (Algorithmen-) Buch empfiehlst du für sowas? Das würde mir eigentlich schon reichen.

Also ein bisschen klar war mir das schon, ich hätte am besten schreiben sollen was ich schon weiß.

Zum Abspeichern wollte ich einen std::vector nehmen. Ist das ok? Oder std::list, oder sollte ich die Datenstruktur am besten selbst schreiben?

Was ich noch nicht so ganz verstehe: Bleibt diese linked_list ht[101]; immer gleich groß, also setzt man am Anfang ein feste Größe und die bleibt dann, oder wird die auch vergrößert?

Und mein größtes Problem ist, das ich nicht genau weiss, wie man das handhabt, wenn es mehrfache Einträge für einen Hash-Code gibt. *snif*

Mr. N

Welches Buch ich empfehlen kann? Empfehlen kann ich keins, aber dir sagen, welches ich hab: Algorithmen in C von R. Sedgewick.
Dein Problem, wenn es mehrere Einträge auf einer linked_list gibt? Einfügen. Zum Finden: sequenezielle Suche. Alles in der linked_list durchsuchen.

Trollcrew

Hi! Danke für den Tipp. Werde mir das Buch dann mal kaufen.

Da gibt's ja auch noch Unterschiede zwischen Hashtable und Hashmap. Ich hab mal mit Hilfe der Klasse std::map ne super simple Hashmap-Klasse erstellt, vielleicht ist es auch keine richtige Hashmap *g*.

template<typename Key, typename Value, int BucketSize = 20> class HashMap {
public:
    HashMap() {
        for(int nCurrentBucket = 0; nCurrentBucket < BucketSize; ++nCurrentBucket) {
            m_Buckets[nCurrentBucket] = new std::map<Key, Value>;
        }
    }
    ~HashMap() {
        for(int nCurrentBucket = 0; nCurrentBucket < BucketSize; ++nCurrentBucket) {
            delete m_Buckets[nCurrentBucket];
        }
    }
    inline DWORD GetHashCode(Key& k) {
        return DWORD(DWORD_PTR(k) >> 4) % BucketSize;
    }
    inline void Add(Key k, Value v) {
        m_Buckets[GetHashCode(k)]->operator[](k) = v;
    }
    inline Value& Get(Key k) {
        return m_Buckets[GetHashCode(k)]->operator[](k);
    }
private:
    std::map<Key, Value>* m_Buckets[BucketSize];
};

[ Dieser Beitrag wurde am 31.12.2002 um 15:37 Uhr von Happy Birthday editiert. ]

Wie geht &quot;Hashmap programmieren&quot;?

Wie geht "Hashmap programmieren"?