I've implemented binary search, linear search and a hash table to compare each time complexity. The problem is that somehow, my hash table is much slower than the binary search when I measure time to find prime numbers. Below is my code:
// Make the hash table 20 times the number of prime numbers
HashTable::HashTable(std::vector<int> primes)
{
int tablesize = primes.size() * 20;
table = new std::list<int>[tablesize];
size = tablesize;
for (auto &prime : primes)
this->insert(prime);
}
// Hash function
int HashTable::hash(int key)
{
return key % size;
}
// Finds element
int HashTable::find(int key)
{
// Get index from hash
int index = hash(key);
// Find element
std::list<int>::iterator foundelement = std::find(table[index].begin(), table[index].end(), key);
// If element has been found return index
// If not, return -1
if (foundelement != table[index].end())
return index;
else
return -1;
}
// Adds element to hashtable
void HashTable::insert(int element)
{
// Get index from hash and insert the element
int index = hash(element);
table[index].push_back(element);
}
HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <list>
#include <iostream>
#include <vector>
class HashTable
{
private:
// Each position in Hashtable has an array of lists to store elements in case of collision
std::list<int>* table;
// Size of hashtable
int size;
// Hashfunction that returns the array location for the given key
int hash(int key);
public:
HashTable(int tablesize);
HashTable(std::vector<int> primes);
// Adds element to hashtable
void insert(int element);
// Deletes an element by key
void remove(int key);
// Returns an element from hashtable for a given key
int find(int key);
// Displays the hashtable
void printTable();
// Display histogram to illustrate elements distribution
void printHistogram();
// Returns the number of lists in hash table
int getSize();
// Returns the total number of elements in hash table
int getNumberOfItems();
// De-allocates all memory used for the Hash Table.
~HashTable();
};
#endif
I've already tried to exceed the size of the table size to eliminate collisions but I didn't notice any difference.
