1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include<iostream>
#include"table.hpp"
/* hash.cpp by Adam Carpenter - acarpent - acarpenter@email.wm.edu
This program is a driver that utilizes the table.cpp hash table. It
reads in input from the command line (or fed in from file) and creates
an array containing the given items. It then creates hash table objects
and hashes the items into each of these objects using the four different
methods described in class: linear probing, quadratic probing, double
hashing, and separate chaining. It then calls for printing out all of
the hash tables.
*/
void readInput(int inputArray[]) {
/* Reads input from command line or from a given file of keys
into an array of size 10 (the maximum number of input items.
*/
std::cout << "\nHash Tables!\n\n";
std::cout << "Enter up to 10 positive integers to be hashed one at a time.\nWhen you are done, enter -1\n";
int tmp = 0;
int count = 0;
while (tmp != EMPTY && count < 10) {
std::cin >> tmp;
inputArray[count] = tmp;
count++;
}
// Print entered list
std::cout << "\nEntered integers: ";
for (int i = 0; i < 10; i++) {
if (inputArray[i] != EMPTY) {
std::cout << inputArray[i] << " ";
}
}
std::cout << "\n";
}
int main() {
/* main is the primary driver of the hash table demonstration.
It is the caller of all of the subsequent functions and hash
table methods.
*/
int integerList[10] = {EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY};
readInput(integerList);
// Linear Probing
Table linearTable(false);
linearTable.hashLinear(integerList);
std::cout << "\nLinear Probing Hash Table: \n";
linearTable.printTable(false);
// Quadratic Probing
Table quadraticTable(false);
quadraticTable.hashQuad(integerList);
std::cout << "\nQuadratic Probing Hash Table: \n";
quadraticTable.printTable(false);
// Double Hashing
Table doubleTable(false);
doubleTable.hashDouble(integerList);
std::cout << "\nExtra Credit: Double Hashing Hash Table: \n";
doubleTable.printTable(false);
// Separate Chaining
Table chainTable(true);
chainTable.hashChaining(integerList);
std::cout << "\nExtra Credit: Separate Chaining Hash Table: \n";
chainTable.printTable(true);
return 0;
}
|
