Hashtable

SeppJ

Anfängerfehler: Regel der großen Drei nicht beachtet.
Ungeschickt: Warum Werte nicht direkt beim new selbst mit 0 initialisieren?
Laienhaft: Von Initialisierungslisten haben wir noch nie gehört, oder?
Designfehler: Warum ist das kein Template? Mindestens key, value und Hashfunktion gehören hier frei wählbar und es wäre dazu nicht mehr als eine einzige Zeile template<....> am Anfang nötig.
Designfehler: Warum sind Größenangaben int?
Designfehler: Warum sind da globale Konstanten?
Designfehler: Warum gibt die get-Methode -1 bei Fehler zurück? Was ist, wenn mein value -1 ist?
Designfehler: Und wenn mehr als TABLE_SIZE Einträge gemacht werden?
Designfehler: Warum ist bei dieser Form der Implementierung table überhaupt vom Typ Zeiger auf Zeiger auf Hashelement? Die Zeigereigenschaft wird nur benutzt, um festzustellen, ob ein Element NULL ist oder nicht. Das wäre doch auch einfacher gegangen. Man hat den Eindruck, der Autor hat mal Hastables mit Zeigern auf Zeigern gesehen, aber nicht so richtig verstanden, wie sie funktionieren.
Designfehler: Die Implementierung ist nicht nur auf TABLE_SIZE Einträge beschränkt, sie führt sogar noch nahezu absichtlich Kollisionen herbei, die normalerweise gar nicht da wären!
Anfängerfehler: Was passiert denn, wenn man NULL deletet?
Ungeschickt: Warum überschreibt das put bei einem doppelten key nicht einfach den alten value?
Doppelt ungeschickt: Was passiert, wenn das new im put wirft?
Designfehler: Kann man später auch mal was machen mit dem Hashtable? Ich will ja nicht nur Einfügen und Zugreifen. Bei dem Design wird es zum Beispiel zwischen schwierig bis unmöglich, einen Wert zu entfernen. Das ist nicht die einzige Aktion oder Komfortfunktion, die mit dem Design und/oder der technischen Umsetzung verbaut wurde.

Das ist jetzt nur mal eben schnell quer gelesen, so genau habe ich den Code gar nicht untersuchen müssen, um hier mehrere Seiten im Editorfenster zu füllen.

aber er sagte ja auch, dass er es selbst implementieren wollte, also dass er keine STL in solch einem Falle nutzen kann.

Man kann einen Hashtable doch wunderbar als vector von vector oder als vector von (multi-)set implementieren. Dann lernt man wunderbar viel über Hashtables, aber muss sich nicht mit Details über Speicherverwaltung rumschlagen, die mit Hashtablealgorithmen erst einmal nichts zu tun haben.

Doppelt ungeschickt: Was passiert, wenn das new im put wirft?

Wie soll man das umgehen?

DocShoe

trycatchnix schrieb:

Doppelt ungeschickt: Was passiert, wenn das new im put wirft?

Wie soll man das umgehen?

Erst allozieren, dann die Hash Table anfassen. Damit bleibt die Hash Table intakt.

Edit:
Typos o.O

@SeppJ:
Das sind ja fast mehr Fehler als der Code lang ist Manchmal kann ich die Leute verstehen, die einen Bogen ums C++-Lernen machen

Marthog

Citizen42 schrieb:

@SeppJ:
Das sind ja fast mehr Fehler als der Code lang ist Manchmal kann ich die Leute verstehen, die einen Bogen ums C++-Lernen machen

In anderen Sprachen waeren es 3 bis maximal 5 Problemfaelle weniger, dafuer aber vielleicht auch wieder neue dazu. Das Hauptproblem ist eine vom voellig falsche designte Hashtable.

wo finde ich eine c++ hash table implementierung, die nicht gerade von templates ueberfuellt ist?

SeppJ

coder007 schrieb:

wo finde ich eine c++ hash table implementierung, die nicht gerade von templates ueberfuellt ist?

Eine ernsthafte Implementierung? Wohl nirgendwo, denn warum sollte man das jemals ohne Templates machen?

Also es wurde ja auch nach Quellen gefragt, ich erinnere mich daran, dass bei den 6.006 MIT open courseware Videos eins zumindest teilweise Hashing bzw. Hashtables behandelt hat.

Achja, hier der Link: https://www.youtube.com/watch?v=oFBEj6wE_Jw

Ich kann die Qualität der hier vorgestellten Dinge nicht beurteilen (sollte ich dann den Link posten? Ich denke schon, denn:) das ist von einer recht bekannten Universität, und ich hab schonmal irgendo eine Empfehlung für diese Videos gelesen, also daneben wird das vermutlich nicht sein.

P.S.: Wenn es um das Interface Design geht, könnte man sich ja einfach an der std::unordered_map orientieren...

LG

ich suche keine ernsthafte implementierung, sondern nur wie man es im umfang eines interviews coden kann...

folgendes ist recht brauchbar:
http://blog.aozturk.me/simple-hash-map-hash-table-implementation-in-c

Wie wärs damit:

#include <memory>
#include <cassert>
#include <unordered_set>
#include <vector>

size_t hash(int x) { return x; }

template <typename T>
class hash_table {
  typedef std::size_t key_t;

  struct slist_node {
    slist_node(key_t key, T value)
      : key(key), next(nullptr), value(std::move(value)) {}
    key_t key;
    slist_node *next;
    T value;
  };

  slist_node *find(slist_node *n, key_t key, T const& x) const {
    for (; n; n=n->next)
      if (n->key == key && n->value == x)
        return n;
    return nullptr;
  }

  std::vector<slist_node*> table;
  size_t size_ = 0;

public:
  hash_table(size_t n = 13)
    : table(n, nullptr) {}
  hash_table(hash_table const& o)
    : hash_table(o.table.size(), o) {}
  hash_table(hash_table&& o)
    : hash_table(o.table.size(), std::move(o)) {}
  hash_table(size_t n, hash_table o)
    : table(n, nullptr) {
    for (auto *n : table) {
      for (; n; n=n->next) {
        insert(n->key, std::move(n->value));
      }
    }
  }
  ~hash_table() {
    for (auto *n : table) {
      while (n) {
        auto *next = n->next;
        delete n;
        n = next;
      }
    }
  }
  friend void swap(hash_table& a, hash_table& b) {
    std::swap(a.table, b.table);
  }
  hash_table& operator=(hash_table o) {
    swap(*this, o);
  }
  void rehash(size_t n) {
    hash_table o(n, *this);
    swap(o, *this);
  }

  bool contains(T const& x) const {
    auto key = static_cast<key_t>(hash(x));
    return find(table[key%table.size()], key, x);
  }

  bool insert(T x) {
    auto key = static_cast<key_t>(hash(x));
    auto& old_nd = table[key%table.size()];
    if (find(old_nd, key, x))
      return false;
    auto new_nd = std::make_unique<slist_node>(key, std::move(x));
    new_nd->next = old_nd;
    old_nd = new_nd.release();
    ++size_;
    return true;
  }        

  size_t size() const { return size_; }
};

int main() {
  hash_table<int> h1;
  std::unordered_set<int> h2;

  srand(0);
  for (int i=0; i<1000; ++i) {
    int x = rand()%100;
    assert(h1.insert(x) == h2.insert(x).second);
    assert(h1.size() == h2.size());
  }
}

SeppJ

coder007 schrieb:

ich suche keine ernsthafte implementierung, sondern nur wie man es im umfang eines interviews coden kann...

Wenn du in einem Interview kein Template hin bekommst, wäre ich schon ziemlich schwer enttäuscht.

@SeppJ: ich meinte template spielereien wie zb. in boost: http://www.boost.org/doc/libs/1_46_0/boost/unordered/unordered_map.hpp

eine map in der standard lib hat ja auch iteratoren, welche man implementieren muss... da ist es schon einfacher eine hash table zu implementieren, welche das core konzept implementiert...

Nathan

coder007 schrieb:

@SeppJ: ich meinte template spielereien wie zb. in boost: http://www.boost.org/doc/libs/1_46_0/boost/unordered/unordered_map.hpp

Wo sind denn da Template Spielereien? Ist doch noch alles straight-forward.