Stroustrups hash_map-Implementierung ist falsch?

Ich schaue auf Straustrup die Implementierung von hash_map. Dies wird eine Intuition geben, wie er es ImplementierungStroustrups hash_map-Implementierung ist falsch?

template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<T> > 
class hash_map 
{ 
private: // representation 
    struct Entry { 
     key_type key; 
     mapped_type val; 
     Entry* next; // hash overflow link 
     bool erased; 
     Entry(key_type k, mapped_type v, Entry* n) 
     : key(k), val(v), next(n), erased(false) { } 
    }; 

    vector<Entry> v; // the actual entries 
    vector<Entry*> b; // the hash table: pointers into v 
    // ... 

private: 
    float max_load; // keep v.size()<=b.size()*max_load 
    float grow; // when necessary, resize(bucket_count()*grow) 
    size_type no_of_erased; // number of entries in v occupied by erased elements 
    Hasher hash; // hash function 
    key_equal eq; // equality 
    const T default_value; // default value used by [] 
};

Und das ist die Umsetzung von operator []

template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<T> > 
mapped_type& hash_map::operator[](const key_type& k) 
{ 
    size_type i = hash(k)%b.size(); // hash 
    for(Entry* p = b[i]; p; p = p->next) // search among entries hashed to i 
     if (eq(k,p->key)) { // found 
      if (p->erased) { // re-insert 
       p->erased = false; 
       no_of_erased--; 
       return p->val = default_value; 
      } 
      return p->val; 
     } 

    // not found: 
    if (b.size()*max_load < v.size()) { // if ‘‘too full’’ 
     resize(b.size()*grow); // grow 
     return operator[](k); // rehash 
    } 

    v.push_back(Entry(k,default_value,b[i])); // add Entry 
    b[i] = &v.back(); // point to new element 
    return b[i]->val; 
}

So lassen Sie uns vorstellen, gibt es drei Elemente i Hash abgebildet, aber keiner von ihnen entspricht der neue Schlüssel k, dann sollten wir einen weiteren Eintrag in der Liste b[i] hinzufügen, oder? Stattdessen erzeugt der Code einen weiteren Entry im v Vektor und ersetzt b[i] durch die Adresse dieses Eintrags (woher die alten 3 Einträge verloren gehen).

Habe ich etwas vermisst, oder gibt es wirklich ein Problem?

P.S. Ich schaue mir die "C++ Programmiersprache" von Bjarne Straustrup an, dritte Ausgabe. Die Funktion befindet sich auf der 500. Seite.

Quelle

2016-09-18 user1289

Warum 3 Elemente? Und wie wären die 3 Elemente in erster Linie dort gewesen, wenn jede Kollision die vorherige übertrifft? –

Ja, vielleicht könnte es nicht 3 Elemente geben, aber es könnte ein Element geben, und es wird verloren gehen, oder? – user1289

und es gibt keinen Grund, die Liste der Einträge zu verwenden, wenn Einträge niemals zur Liste hinzugefügt werden (höchstens ein Eintrag in der Liste). – user1289

Die Hash-Einträge bilden eine verkettete Liste. Wenn der neue Eintrag eingefügt wird, wird es den bisherigen Leiter der Liste der Einträge (möglicherweise null) gegeben:

v.push_back(Entry(k,default_value,b[i])); // add Entry

die b[i] dort sehen?

Es macht dann eine Verbindung zu diesem Eintrag in seinem next Feld. Wir verschieben dann den Kopf der Liste b[i], um auf den neuen Eintrag zu zeigen;

b[i] = &v.back(); // point to new element

Quelle

2016-09-18 17:00:14 Yakk

ah, ich sehe, danke – user1289

Stroustrups hash_map-Implementierung ist falsch?

Antwort

Verwandte Themen