0
\$\begingroup\$

I have been studying hashtable for two days and was musterring up the courage to write a code. Finally I have written code in which I have taken many shortcuts:

  1. The first being I have used compression function as key % hash_size;
  2. I have not used any hashing function.
  3. I have implemented it using array. A better option could be a vector.
  4. For linear probing I have choose to store in the next empty index.
  5. My code is not commented but is pretty straightforward.

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
class data{
  private:
    int key;
    int value;
    bool deleteme;
  friend class hashtable;
};
class hashtable{
  public:
    hashtable(int m);
    hashtable(const hashtable& that);
    hashtable & operator= (hashtable src);
    ~hashtable();
    void add(int key, int value);
    bool exists(int key);
    int get(int key);
    void remove(int key);
    void display();
  private:
    int size;
    data* array;
};
hashtable::hashtable(int m):size(m){
    array = new data[m]();
    // data array[] = {NULL};
}
hashtable::hashtable(const hashtable& that){
  size = that.size;
  array = new data[that.size];
  for(int i = 0; i < that.size ; ++i){
    array[i] = that.array[i];
  }
}
hashtable & hashtable::operator=(hashtable src){
    std::swap(array, src.array);
    std::swap(size, src.size);
    return *this;
}
hashtable::~hashtable(){
    delete [] array;
}
void hashtable::add(int k, int val){
  int index = k % size;
  while(array[index].key != 0 || array[index].deleteme == 1){
    if(array[index].key == k)
      break;
    index += 1;
  }
  array[index].key = k;
  array[index].value = val;
}
bool hashtable::exists(int key){
  int index = key % size;
  while((array[index].key != key && index < size ) || (array[index].deleteme == 1 && index < size)){
    index += 1;
  }
  return index < size;
}
int hashtable::get(int key){
  int index = key % size;
  while((array[index].key != key && index < size) || (array[index].deleteme == 1 && index < size)){
    index += 1;
  }
  if(index < size)
    return array[index].value;
}
void hashtable::remove(int key){
  int index = key % size;
  while((array[index].key != key && index < size)|| (array[index].deleteme == 1 && index < size)){
    index += 1;
  }
  array[index].key = 0;
  array[index].value = 0;
  array[index].deleteme = 1;
}
void hashtable::display(){
    for (int i = 0; i < size; ++i)
    {
        cout << array[i].key << " " << array[i].value  << " " << array[i].deleteme << endl;
    }
}

int main(){
  hashtable h1(11);
  h1.add(3,134);
  h1.add(14,139);
  h1.add(742,963);
  h1.add(11,456);
  h1.add(22,635);
  h1.add(33,852);
  h1.add(44,968);
  h1.add(9,589);
  h1.add(9,7890);
  h1.remove(14);
  h1.remove(33);
  h1.add(55,786);
  h1.add(10,56);
  cout << h1.get(44) << endl;
  // cout << h1.(43) << endl;
  h1.display();
}
\$\endgroup\$
  • \$\begingroup\$ Your code has multiple instances of undefined behavior. key % size could become negative, and you must not read array[size]. \$\endgroup\$ – Roland Illig Dec 30 '17 at 13:59
1
\$\begingroup\$
  1. Use unsigned int for the keys/hashes.
  2. Make functions like get, display or exists const, so you make clear that they are not modifying the map and you can pass the map as const& to a function, which may uses this functions but does not use add or remove or other functions modifying the map.

    void display() const;
    
  3. You can add operator[] which returns a reference to the value, here are the signatures:

    int& operator[](int key); // this can be used for assignment (``map[3] = 5``) and to get a value (``std::cout << map[3] << '\n'``). This needs to insert an element, if there is no element with the key and initialize its value to a default value like ``int()``/``0``
    int operator[](int key) const; // this is used when the map is accessed when it is const. No need for reference, but for other value-types like std::string, use std::string const& to avoid copying
    
  4. You can make the class generic, to allow other value-types.

  5. Make whitespace after each function or class, to seperate.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.