hashtable linear probing wie fülle ich diese?

markuswenczel

folgende Hashmap habe ich über Wikipedia Link
ich möchte sie befüllen

Muss ich da der Methode
void put(int key, int value)
die Werte übergeben nehme ich mal an.

Wie kann ich die gefüllte HashTable benutzen in Main
Ich sehe keine Methode mit der man die erstellte HashTable verwenden kann wenn man Sie erstellt hat.

danke für Tips..

#include <hashmap>

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;
      }

      void setValue(int value) {
            this->value = value;
      }
};

class DeletedEntry: public HashEntry {
private:
      static DeletedEntry *entry;
      DeletedEntry() :
            HashEntry(-1, -1) {
      }
public:
      static DeletedEntry *getUniqueDeletedEntry() {
            if (entry == NULL)
                  entry = new DeletedEntry();
            return entry;
      }
};

DeletedEntry *DeletedEntry::entry = NULL;

const int TABLE_SIZE = 90;

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);
            int initialHash = -1;
            while (hash != initialHash && (table[hash]
                        == DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
                        && table[hash]->getKey() != key)) {
                  if (initialHash == -1)
                        initialHash = hash;
                  hash = (hash + 1) % TABLE_SIZE;
            }
            if (table[hash] == NULL || hash == initialHash)
                  return -1;
            else
                  return table[hash]->getValue();
      }

      void put(int key, int value) {
            int hash = (key % TABLE_SIZE);
            int initialHash = -1;
            int indexOfDeletedEntry = -1;
            while (hash != initialHash && (table[hash]
                        == DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
                        && table[hash]->getKey() != key)) {
                  if (initialHash == -1)
                        initialHash = hash;
                  if (table[hash] == DeletedEntry::getUniqueDeletedEntry())
                        indexOfDeletedEntry = hash;
                  hash = (hash + 1) % TABLE_SIZE;
            }
            if ((table[hash] == NULL || hash == initialHash) && indexOfDeletedEntry
                        != -1)
                  table[indexOfDeletedEntry] = new HashEntry(key, value);
            else if (initialHash != hash)
                  if (table[hash] != DeletedEntry::getUniqueDeletedEntry()
                             && table[hash] != NULL && table[hash]->getKey() == key)
                        table[hash]->setValue(value);
                  else
                        table[hash] = new HashEntry(key, value);
      }

      void remove(int key) {
            int hash = (key % TABLE_SIZE);
            int initialHash = -1;
            while (hash != initialHash && (table[hash]
                        == DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
                        && table[hash]->getKey() != key)) {
                  if (initialHash == -1)
                        initialHash = hash;
                  hash = (hash + 1) % TABLE_SIZE;
            }
            if (hash != initialHash && table[hash] != NULL) {
                  delete table[hash];
                  table[hash] = DeletedEntry::getUniqueDeletedEntry();
            }
      }

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

Bashar

Was meinst du mit benutzen? put, get und remove sind doch da, was brauchst du noch?

markuswenczel

Bashar schrieb:

Was meinst du mit benutzen? put, get und remove sind doch da, was brauchst du noch?

Mit der Methode get kann ich in Main arbeiten?

314159265358979

markuswenczel schrieb:

Bashar schrieb:

Was meinst du mit benutzen? put, get und remove sind doch da, was brauchst du noch?

Mit der Methode get kann ich in Main arbeiten?

Gegenfrage: Was würde denn dagegen sprechen?

Bashar

Wieso nicht?

markuswenczel

Wollte die HashMap füllen aber der compiler schreibt
No such file or directory, Die Hashmap habe ich unter HashMap.h abgespeichert und in main rufe ich sie auf aber das funktioniert nicht.

#include <iostream>

#include "HashMap.h"

using namespace std;

int main(){

for(int i=0;i!=0;i++)    {
cout<<"Bitte Sozialversicherungsnummer eingeben; Ende = '0'"<<endl;
int svn;
cin>>svn;
int key=i;

HashMap.put(key,svn);

      }   

}

SeppJ

Tja, dann wird sie wohl nicht dort gespeichert sein, wo sie gesucht wird. Wenn man eine IDE benutzt, muss man lernen, wie sie zu bedienen ist. Wenn du direkt compilierst, gib einen Includepfad an (meistens -IPfad).

Der Compiler wird wohl auch den Dateinamen nennen.

theta

Ausserdem nehme ich stark an, dass Du ein HashMap Objekt anlegen und benutzen musst.

markuswenczel

SeppJ schrieb:

Tja, dann wird sie wohl nicht dort gespeichert sein, wo sie gesucht wird. Wenn man eine IDE benutzt, muss man lernen, wie sie zu bedienen ist. Wenn du direkt compilierst, gib einen Includepfad an (meistens -IPfad).

Die Dateien liegen beide im gleichen Ordner was meinst du bitte mit Includepfad
ich habe

#include "HashMap.h"

angegeben ist das kein gültiger Include Pfad
in der Hashtable habe ich

#include "Aufgabe4.6.cpp"

für die Main Methode angegeben.
LG
Markus

theta

In cpp File inkludiert man keine cpp Files - nur Header.

ipsec

markuswenczel schrieb:

in der Hashtable habe ich

#include "Aufgabe4.6.cpp"

für die Main Methode angegeben.

Das ist falsch, damit erzeugst du eine zirkuläre Abhängigkeit. Nimm das Include einfach da raus. Woher muss die Hashtabelle auch main kennen?

markuswenczel

manni66 schrieb:

Der Compiler wird wohl auch den Dateinamen nennen.

hashmap: No such file or directory.

markuswenczel schrieb:

manni66 schrieb:

Der Compiler wird wohl auch den Dateinamen nennen.

hashmap: No such file or directory.

Und wo ist die Datei?

markuswenczel

ipsec schrieb:

markuswenczel schrieb:

in der Hashtable habe ich

#include "Aufgabe4.6.cpp"

für die Main Methode angegeben.

Das ist falsch, damit erzeugst du eine zirkuläre Abhängigkeit. Nimm das Include einfach da raus. Woher muss die Hashtabelle auch main kennen?

danke

markuswenczel

manni66 schrieb:

markuswenczel schrieb:

manni66 schrieb:

Der Compiler wird wohl auch den Dateinamen nennen.

hashmap: No such file or directory.

Und wo ist die Datei?

Im gleichen Ordner.
das include war falsch, jetzt kompiliert das ganze aber tut nicht was ich wollte,

aber danke für die Hilfe

markuswenczel

Wollte ein Objekt erzeugen mit der Methode put

HashMap.put(key,svn);

aber das funktioniert so nicht

expected primary-expression before '.' token

ich dachte Klassenname.Methodenname(Parameterübergabe);
ist die Anweisung um die HashTable zu füllen,
hmmm

#include <iostream>

#include "HashMap.h"

using namespace std;

int main(){

for(int i=0;i!=0;i++)    {
cout<<"Bitte Sozialversicherungsnummer eingeben; Ende = '0'"<<endl;
int svn;
cin>>svn;
int key=i;

HashMap.put(key,svn);

      }   

}

markuswenczel

so jetzt habe ich mal begonnen den Code auszubessern war ein peinlicher Fehler
naja,
Mit der Methode get hole ich mir die gespeicherten Werte über den Key,
soweit so gut, der return Wert ist ein array, was ich nicht so ganz verstehe ist
was an der HashTable so anders ist als bei einem gewöhnlichen Array....

#include <iostream>

#include "HashMap.h"

using namespace std;

int main(){

int svn;   

for(int i=1; svn!=0;i++)    {
cout<<"Bitte Sozialversicherungsnummer eingeben; Ende = '0'"<<endl;
cin>>svn;
int key=i;

HashEntry(key,svn);

      }   

HashMap.get(key){

                 }

}

Bashar

markuswenczel schrieb:

so jetzt habe ich mal begonnen den Code auszubessern war ein peinlicher Fehler

Na wenn das der verbesserte Code sein soll, denn du jetzt wieder gepostet hast, dann ist da kein peinlicher Fehler drin, sondern einfach ein grundlegendes Unverständnis von C++. Vielleicht solltest du erstmal ganz kleine Brötchen backen, dich mal ein bisschen einlesen und vielleicht ein paar eigene Miniprojekte bauen, bevor du fremden Code abschreibst, den du nicht verstehst?

naja,
Mit der Methode get hole ich mir die gespeicherten Werte über den Key,
soweit so gut, der return Wert ist ein array

Nö, der return-Wert ist int.

DocShoe

Bashar schrieb:

Na wenn das der verbesserte Code sein soll, denn du jetzt wieder gepostet hast, dann ist da kein peinlicher Fehler drin, sondern einfach ein grundlegendes Unverständnis von C++. Vielleicht solltest du erstmal ganz kleine Brötchen backen, dich mal ein bisschen einlesen und vielleicht ein paar eigene Miniprojekte bauen, bevor du fremden Code abschreibst, den du nicht verstehst?

Ich hätt´s anders (und vor allem finaler. Gibt genügend schöne Berufe, wo man nicht programmieren muss) formuliert

@OP
Wie sieht denn dein Quelltext aus? Das, was du uns hier ständig vorsetzt benutzt zwar das cpp-code-formatting, aber du darfst dir ruhig etwas Mühe beim Ersetzen der Tabs durch Leerzeichen geben. So ist das jedenfalls schwer lesbar...