Hashtable

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.