# It is a hashmap, using linear probing on an array

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();
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;
}
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.remove(14);
h1.remove(33);
cout << h1.get(44) << endl;
// cout << h1.(43) << endl;
h1.display();
}
• Your code has multiple instances of undefined behavior. key % size could become negative, and you must not read array[size]. – Roland Illig Dec 30 '17 at 13:59

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.