Hashtable

Hallo,

kann mir bitte jemand feedback zu meiner implementierten hashtable geben? ich weiss c++11 hat unordered_map, aber ich wollte die hashtable zum ueben selbst implementieren...

#include <iostream>
using namespace std;

class HashEntry {
private:
      int key;
      int value;
public:
      HashEntry(int key, int value) {
            this->key = key;
            this->value = value;
      }

      int getKey() {
            return key;
      }

      int getValue() {
            return value;
      }
};

const int TABLE_SIZE = 128;

class HashMap {
private:
      HashEntry **table;
public:
      HashMap() {
            table = new HashEntry*[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = NULL;
      }

      int get(int key) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != NULL && table[hash]->getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == NULL)
                  return -1;
            else
                  return table[hash]->getValue();
      }

      void put(int key, int value) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != NULL && table[hash]->getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] != NULL)
                  delete table[hash];
            table[hash] = new HashEntry(key, value);
      }     

      ~HashMap() {
            for (int i = 0; i < TABLE_SIZE; i++)
                  if (table[i] != NULL)
                        delete table[i];
            delete[] table;
      }
};

int main() {
	// your code goes here

	HashMap m;
	m.put(1, 12);
	m.put(2, 32);
	m.put(2, 10);
	m.put(8, 100);

	cout << m.get(1) << endl;
	cout << m.get(2) << endl;
	cout << m.get(8) << endl;

	return 0;
}

SeppJ

Das ist ja schon bei den Grundlagen falsch (und zwar auf ganzer Linie: Der Autor kann weder C++, noch weiß er, wie ein Hash Table funktioniert). Das kommt davon, wenn man von irgendwelchen dubiosen Quellen abschreibt. Wo ist denn da die Übung für dich und wieso sollten wir Code, den du nicht geschrieben hast, im Details kritisieren? Zusammenklicken aus dem Internet ist nicht Programmieren!

@SeppJ:
Kennst du denn eine Seite, die man mit ruhigem Gewissen empfehlen kann, um sich mit Datenstrukturen und Algorithmen vertraut zu machen? Google kann ja leider nicht sagen wie gut die gezeigten Treffer vom Inhalt sind. Also geht so eine Suche nur über Empfehlung von Profis.

SeppJ

Citizen42 schrieb:

@SeppJ:
Kennst du denn eine Seite, die man mit ruhigem Gewissen empfehlen kann, um sich mit Datenstrukturen und Algorithmen vertraut zu machen?

Ich bin eigentlich oft recht zufrieden mit Wikipedia.

Nathan

SeppJ schrieb:

Citizen42 schrieb:

@SeppJ:
Kennst du denn eine Seite, die man mit ruhigem Gewissen empfehlen kann, um sich mit Datenstrukturen und Algorithmen vertraut zu machen?

Ich bin eigentlich oft recht zufrieden mit Wikipedia.

Aber die englische Version, versteht sich.

SeppJ

Nathan schrieb:

SeppJ schrieb:

Citizen42 schrieb:

@SeppJ:
Kennst du denn eine Seite, die man mit ruhigem Gewissen empfehlen kann, um sich mit Datenstrukturen und Algorithmen vertraut zu machen?

Ich bin eigentlich oft recht zufrieden mit Wikipedia.

Aber die englische Version, versteht sich.

Meistens. In den letzten Jahren hat die deutsche Wikipedia meiner Meinung nach bei Informatikthemen ganz gut aufgeholt. (Und bei Autothemen ist sie sowieso die beste )

Citizen42 schrieb:

Google kann ja leider nicht sagen wie gut die gezeigten Treffer vom Inhalt sind.

Aber zumindest bei dem hier gezeigten Code sollten alle Alarmglocken schrillen, weil allein schon die technische Umsetzung fehlerhaft ist. Wer nicht weiß, wie in C++ eine Containerklasse aufgebaut ist, dem traut man besser auch nicht bei der Programmlogik.

Ok, also kann man wirklich Wikipedia in der Hinsicht trauen. Das ist doch schon mal eine Hausnummer.

Vielleicht könnte Jemand hier erläutern, wieso der oben gezeigte Code schlecht ist. Mir fällt jetzt nur das Hantieren mit rohen Zeigern auf, aber er sagte ja auch, dass er es selbst implementieren wollte, also dass er keine STL in solch einem Falle nutzen kann.

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...