std::unordered_set - behind the scenes

Von den Schwierigkeiten und Problemen, std::unordered_set (oder zumindest einen Teil davon) zu implementieren.

Video

Quelltext

#include <iostream>
#include <unordered_set>
#include <vector>
#include <memory>

template <typename T,
	  typename Hash = std::hash<T>,
	  typename Equal = std::equal_to<T>
	 > class HashSet
{
  struct ElemHolder
  {
    std::unique_ptr<T> elem;
    bool deleted;
    
    ElemHolder()
     : deleted { false }
    {
    }
    
    ElemHolder(ElemHolder const &src)
      : elem { new T(*src.elem) }, deleted { src.deleted }
    {
    }
    
    bool empty() const
    {
      return deleted || !elem;
    }
  };
  
  std::vector<ElemHolder> mElements;
  Hash mHash;
  Equal mEqual;
  
  void rehash()
  {
    std::cerr << "Rehash aufgerufen. Vergrößere auf " << mElements.size()*2 << " Elemente.\n";
    std::vector<ElemHolder> tmp;
    tmp.swap(mElements);
    mElements.resize(tmp.size()*2);
    for (auto eh : tmp) {
      insert(*eh.elem);
    }
  }
  
public:
  
  class iterator
  {
    typename std::vector<ElemHolder>::iterator it;
    std::vector<ElemHolder> *elements;
    
    friend class HashSet;
    
    iterator(typename std::vector<ElemHolder>::iterator const &i, std::vector<ElemHolder> &e)
      : it{ i }, elements { &e }
    {
    }
    
    iterator &nextSlot()
    {
      ++it;
      return *this;
    }
    
    ElemHolder &holder()
    {
      return *it;
    }
    
  public:
    
    T const &operator*() const
    {
      return *(it->elem);
    }
    
    iterator &operator++()
    {
      do {
	++it;
      } while (it != elements->end() && (!(it->elem) || it->deleted));
      return *this;
    }
    
    iterator &operator+(std::size_t distance)
    {
      auto i = distance;
      while (i > 0 && it != elements->end()) {
	++it;
	--i;
      }
      return *this;
    }
    
    bool operator==(iterator const &other) const
    {
      return it == other.it;
    }
    
    bool operator!=(iterator const &other) const
    {
      return !operator==(other);
    }
  };
  
  HashSet()
    : mElements(17)
  {
  }

  iterator begin()
  {
    return iterator(mElements.begin(), mElements);
  }
  
  iterator end()
  {
    return iterator(mElements.end(), mElements);
  }
  
  iterator find(T const &key)
  {
    return internalFind(key, false);
  }
  
  void insert(T const &element)
  {
    auto position = internalFind(element, true);
    if (position == end()) {
      rehash();
    }
    position = internalFind(element, true);
    position.holder().elem.reset(new T(element)); 
  }
  
  void erase(T const &key)
  {
    auto position = find(key);
    if (position != end()) {
      position.holder().elem.reset();
      position.holder().deleted = true;
    }
  }
  
private:
  
  iterator internalFind(T const &key, bool withEmpty)
  {
    auto hashCode = mHash(key);
    auto position = begin() + (hashCode % mElements.size());
    auto candidate = position;
    while (true) {
      if (candidate.holder().empty()) {
	if (withEmpty) {
	  return candidate; // freier Platz gesucht und gefunden
	}
	else {
	  if (!candidate.holder().deleted) {
	    return end();  // Element ist nicht vorhanden
	  }
	}
      }
      else {
	if (mEqual(*candidate, key)) {
	  return candidate;
	}
      }
      if (withEmpty) {
	candidate.nextSlot();
      }
      else {
	++candidate;
      }
      if (candidate == position) {
	// eine Runde rum -> nicht gefunden
	return end();
      }
    } 
  }
};

struct StupidHash
{
  std::size_t operator()(int)
  {
    return 0;
  }
};

int main()
{
  HashSet<int> hs;
  for (int i = 0; i < 100; ++i) {
    hs.insert(i*10);
  }
  for (auto e : hs) {
    std::cerr << e << std::endl;
  }
  auto i1 = hs.find(105);
  if (i1 == hs.end()) {
    std::cerr << "Element nicht im HashSet vorhanden\n";
  }
  auto i2 = hs.find(110);
  if (i2 != hs.end()) {
    std::cerr << "Element gefunden: " << *i2 << std::endl;
  }
  hs.erase(110);
  auto i3 = hs.find(110);
  if (i3 != hs.end()) {
    std::cerr << "Element gefunden: " << *i3 << std::endl;
  }
  else {
    std::cerr << "Element ist nicht mehr vorhanden.\n";
  }
  auto i4 = hs.find(120);
  if (i4 != hs.end()) {
    std::cerr << "Element gefunden: " << *i4 << std::endl;
  }
}

Erklärung

Wie bei der Implementierung eines neuen Containers zu erwarten berühren die Besonderheiten von Hash-Verfahren einige Teile des Codes.

Kern einer Hash-Struktur ist ein Array, welches die Elemente (oder in unserem Fall Verweise darauf) enthält. Dieses Array kann in O(1) indiziert werden und ist daher gut als Grundlage für das (ja auch O(1) unterstützende) HashSet geeignet. Arrays unterstützen allerdings nur Integer-Indizes, so dass unsere einzufügenden Objekte erstmal entsprechend abgebildet werden müssen. Das geschieht in den Zeilen 151 und 152. Zuerst wird aus dem Objekt mittels des festgelegten Hashverfahrens der Hashcode berechnet und anschließend wird dieser in den Bereich der möglichen Indizes des zugrundeliegenden Arrays gebracht (durch eine Modulo-Operation). Damit steht dann die eigentlich gewünschte Position des Elementes fest und es kann mit dem Sondieren begonnen werden. Zeilen 154 bis 180 befassen sich nur damit. Die Sondierung läuft so lange, bis wir wieder an der ursprünglich berechneten Stelle angekommen sind (also einmal um das komplette Array gelaufen (Abbruchbedingung in Zeile 176). Wenn wir bis dahin nichts gefunden haben, dann ist das gesuchte Element nicht enthalten.

Für jeden Sondierungsschritt wird eine andere Zelle geprüft. Dabei gibt es zwei Varianten: entweder es steht etwas darin, dann muss mittels des festgelegten Vergleichs auf Gleichheit mit dem Schlüssel geprüft werden (Zeile 166) oder die Zelle ist leer. Ist die Zelle leer, dann stellt sich die Frage, ob wir eine leere Zelle suchen (bspw. zum Einfügen). Ist das der Fall, dann haben wir die passende Stelle gefunden und können diese zurückliefern.

Suchen wir hingegen ein Objekt, dann wird es etwas komplizierter. Wir nutzen beim Lookup den Fakt aus, dass ein bestimmtes Element auch immer eine bestimmte Kette für die Sondierung durchläuft. Finden wir irgendwo in dieser Kette eine leere Stelle, dann wissen wir, dass das gesuchte Element nicht in der Datenstruktur vorhanden ist und können abbrechen (Zeile 159-163). Soll die Datenstruktur das Löschen von Objekten unterstützen, dann müssen wir allerdings die Suche hinter so einer Leerstelle dann noch fortsetzen, wenn an dieser Stelle mal etwas stand, was später gelöscht wurde. Es könnte ja sein, dass das betreffende Objekt eingefügt wurde, als an der entsprechenden Stelle in der Sondierungskette noch etwas stand, was aber später dann gelöscht wurde. Damit wäre standardmäßig die Kette zerrissen und wir würden nicht mehr weitersuchen. Daher speichert unsere Datenstruktur nicht die Elemente direkt, sondern eine Klasse ElemHolder, die sich zusätzlich noch merken kann, ob genau dieser Fall zutrifft. Ist das so, dann wird weitergesucht.

Für den Nutzer des Containers müssen wir natürlich die gewohnten Dinge wie bspw. Iteratoren bereitstellen. Auch hier ist es wieder ein wenig komplizierter: der zugrundeliegende std::vector bietet ja eigentlich schon einen Iterator an. Allerdings würde ein naives Iterieren über diesen auch die Leerstellen in der Datenstruktur mit liefern. Daher müssen wir doch einen eigenen Iteratortyp implementieren (Klasse iterator von Zeile 49 bis 106), der diese Leerstellen überspringt.

Interessant ist zuletzt noch die Funktion rehash() in Zeile 36. Diese wird immer dann aufgerufen, wenn das Array voll ist. Sie vergrößert es und fügt dann alle bestehenden Elemente neu ein. Das ist notwendig, da die Größe des Arrays Einfluss auf die Indexberechnung hat (über das Modulo in Zeile 152). Ändert sich diese Größe, dann müssen auch alle Indizes neu berechnet werden.