#include<bits/stdc++.h> using namespace std;
int prime[]={1031,2053,4099,8209,16411,32771,65537,131101,262147,524309,1048583,2097169,4194319,8388617,16777259,33554467,67108879,134217757,268435459,536870923,1073741827};
class Hash { public: Hash(int find_prime_location); // Constructor
// inserts a key into hash table
void insertItem(int x);
// search a key from hash table
void searchItem(int x);
// hash function to map values to key
int hashFunction(int x) {
int array[4];
for(int i=0;i<4;++i){
array[i] = x % 256;
x >>= 8;
}
int sum=0;
sum = (r1*array[0])+(r2*array[1])+(r3*array[2])+(r4*array[3]);
return sum % M;
}
void random_r();
private:
// Pointer to an array containing buckets
list<int> *table;
int r1;
int r2;
int r3;
int r4;
int M;
};
Hash::Hash(int location) { random_r(); M = prime[location]; table = new list[M]; }
void Hash::insertItem(int key) { int index = hashFunction(key); table[index].push_back(key); }
void Hash::searchItem(int key) { int index = hashFunction(key); list::iterator it; it = find(table[index].begin(), table[index].end(),key); }
void Hash::random_r() { r1 = rand()%262144+1; //2^18 r2 = rand()%262144+1; r3 = rand()%262144+1; r4 = rand()%262144+1; }
int main() { time_t t;
srand((unsigned)time(&t));
for(int j=10;j<31;++j){
long long int total = pow(2,j);
int *input = new int[total];
int capacity = sizeof(input) / sizeof(input[0]);
int *array = new int[total];
int n=0;
int find_prime_location = j-10;
for(int i=0;i<total;++i){
input[i] = rand()%1073741824+1;
}
clock_t start,end;
start = clock();
Hash h(find_prime_location);
for(int q=0;q<total;++q){
h.insertItem(input[q]);
}
end = clock();
double result = (double)(end - start) / (CLOCKS_PER_SEC);
cout << "Hash Table insert: 2^" << j << ", " << result << endl;
delete[] input;
/*********************************************************************/
int *search = new int[100000];
capacity = sizeof(search) / sizeof(search[0]);
for(int i=0;i<100000;++i){
search[i] = rand()%1073741824+1;
}
start = clock();
for(int q=0;q<100000;++q){
h.searchItem(search[q]);
}
end = clock();
result = (double)(end - start) / (CLOCKS_PER_SEC);
cout << "Hash Table search: 2^" << j << ", " << result << endl << endl;
delete[] search;
}
return 0;
}