Question: CSC255 Lab 5 Hash Table Linear Probing, Quadratic Probing, Double Hashing Probing. Collisions Write program that insert(put) and retrieve(get) numbers from input file and output
CSC255 Lab 5 Hash Table
Linear Probing, Quadratic Probing, Double Hashing Probing. Collisions
Write program that insert(put) and retrieve(get) numbers from input file and output number of collisions for linear probing, quadratic probing, double hashing probing and collect number of collisions for each probing for 3 types of random files: increased random, decreased random, not ordered random(100 numbers in each file).
Hash Table size is 191, so 100 random numbers are to be inserted to the table to collect number of collisions.
R=181, prime that less than table size( 191), you shall use it for hash2() function in Double Hashing Probing.
Template Class LinearProbingHash is given (LinearProbingHash.hpp and LinearProbingHash-impl.hpp files )
Create classes QuadraticProbingHash and DoubleHashingProbingHash and Driver.cpp file to test your classes and collect data about collisions.
First Test your program with data from the textbook: Input file is inTextbook.txt , tableSize is 10, R is 7 (prime number, less than TableSize and used in in hash2(x) function, where x is key; see textbook p201+).
Calculate number of collisions for random increasing data(101 numbers) increaseRandom.txt file, output is in increaseRandomOut.txt file
Calculate number of collisions for random decreasing data(101 numbers) decreaseRandom.txt file, output is in decreaseRandomOut.txt file
Calculate number of collisions for random data(101 numbers) rin100.txt file, output is in t100out.txt file
Number of collisions is cumulative and counts in put() function and in get() function.
Number of collisions calculates separately for Linear Probing, for Quadratic Probing and for Double Hashing Probing.
Hash function calculates from key only, and gives some size_t value, that actually is integer and it adjusted to fit in the hash table (index) of pointer on record
For simplicity, in input files have only keys (integer), (actually key can be string or something else, it is important that you will be able to calculate some hash function of these keys, so domain of hash function is set of keys and range is integers: hash:{keys}->{Integers} ), values are matter, but I used for them ordered numbers 1,2,3, .. 100 for simplicity. In real world you will use some values of different type and different value.
In my implementation table is vector of pointers size tableSize=191 , and each element is either pointer of record
So using hash function, you try to insert pointer on the record
Probing, you use only linear probing to insert and retrieve all data. Same with other Probings.
It is important, to be able to retrieve you data from the table.
If you want to put pointer on record to the hash table, you need to find place where to place it, as soon as you found the place, you good, you just put it there.
If you need to find record, first, you find hash function, then place, where its supposed to be in the hash table, if on this place is record with different key, do not give up, instead of this place we find next possible location using specific probing for our hash table and so on, so on. As soon ad we find record that has the same key, we retrieve value from this record.
If we exhausted whole table and we did not find the record with key that we are looking for we print that there is no record with this key.
It is not easy assignment, but as soon as you understand how Linear Probing, Quadratic Probing, Double Hash Probing works, and how to save records in the Hash Table and retrieve them, you will be able to use it in your work. And understanding how it works you can get only by thoroughly doing it.
I did separately put() and get() functions, then, I put common parts in different private function. I left code it the comments for you to see steps of creating the program.
Best Luck!
/* * LinearProbingHash.cpp * * Created on: Feb 13, 2018 * Author: kamilla */ #include
template
template
template
}
//template
template
Record *const p = table[index];
return p ? &(p->value) : nullptr; }
template
template
while (true) { Record *const p = table[index]; if (!p) { return index; //table[index] = new Record(key, value); // break; } else if (p->key == key) { return index; // p->value = value; // break; } //linear probing ++collision; ++index; index %= table.size(); if (index == startIndex) { //throw std::runtime_error("Table is full"); return table.size()+1; } } } //template
Record *const p = table[index]; if (!p) { table[index] = new Record(key, value); } else { p->value = value; } }
/* * LinearProbingHash.h * * Created on: Feb 13, 2018 * Author: kamilla */
#ifndef LINEARPROBINGHASH_HPP_ #define LINEARPROBINGHASH_HPP_
#include
template
private:
struct Record { Key key; Value value;
Record(Key key1, Value value1) { key = key1; value = value1; } };
std::vector
public:
LinearProbingHash(std::size_t initialSize); //initialSize = 191 virtual ~LinearProbingHash(); Value* get(const Key &key) const; void put(const Key &key, const Value &value);
static unsigned int collision;
}; #include "LinearProbingHash-impl.hpp" #endif /* LINEARPROBINGHASH_HPP_ */
Example input file:
100
28 61 90 125 168 200 201 240 249 277
301 319 333 377 379 392 440 473 493 528 570 615 659 678 727 748 760 764 808 809 851 900 903 903 927 970 1003 1044 1079 1099 1132 1172 1213 1228 1252 1263 1310 1341 1386 1392 1416 1443 1446 1486 1492 1503 1527 1569 1611 1633 1654 1663 1702 1710 1732 1769 1794 1842 1882 1905 1937 1979 2004 2018 2031 2050 2091 2108 2158 2169 2195 2211 2230 2262 2307 2347 2357 2381 2427 2441 2486 2507 2555 2589 2633 2641 2683 2727 2771 2809
Output file:
Before linear key = 100 got value=1 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 100 got value(*p)=1
Before quadratic key = 100 got value=1 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 100 got value(*pq)=1 Before double hashing key = 100 value=1 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 100 value*pdh=1 Before linear key = 28 got value=2 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 28 got value(*p)=2
Before quadratic key = 28 got value=2 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 28 got value(*pq)=2 Before double hashing key = 28 value=2 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 28 value*pdh=2 Before linear key = 61 got value=3 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 61 got value(*p)=3
Before quadratic key = 61 got value=3 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 61 got value(*pq)=3 Before double hashing key = 61 value=3 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 61 value*pdh=3 Before linear key = 90 got value=4 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 90 got value(*p)=4
Before quadratic key = 90 got value=4 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 90 got value(*pq)=4 Before double hashing key = 90 value=4 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 90 value*pdh=4 Before linear key = 125 got value=5 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 125 got value(*p)=5
Before quadratic key = 125 got value=5 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 125 got value(*pq)=5 Before double hashing key = 125 value=5 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 125 value*pdh=5 Before linear key = 168 got value=6 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 168 got value(*p)=6
Before quadratic key = 168 got value=6 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 168 got value(*pq)=6 Before double hashing key = 168 value=6 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 168 value*pdh=6 Before linear key = 200 got value=7 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 200 got value(*p)=7
Before quadratic key = 200 got value=7 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 200 got value(*pq)=7 Before double hashing key = 200 value=7 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 200 value*pdh=7 Before linear key = 201 got value=8 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 201 got value(*p)=8
Before quadratic key = 201 got value=8 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 201 got value(*pq)=8 Before double hashing key = 201 value=8 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 201 value*pdh=8 Before linear key = 240 got value=9 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 240 got value(*p)=9
Before quadratic key = 240 got value=9 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 240 got value(*pq)=9 Before double hashing key = 240 value=9 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 240 value*pdh=9 Before linear key = 249 got value=10 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 249 got value(*p)=10
Before quadratic key = 249 got value=10 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 249 got value(*pq)=10 Before double hashing key = 249 value=10 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 249 value*pdh=10 Before linear key = 277 got value=11 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 277 got value(*p)=11
Before quadratic key = 277 got value=11 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 277 got value(*pq)=11 Before double hashing key = 277 value=11 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 277 value*pdh=11 Before linear key = 301 got value=12 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 301 got value(*p)=12
Before quadratic key = 301 got value=12 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 301 got value(*pq)=12 Before double hashing key = 301 value=12 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 301 value*pdh=12 Before linear key = 319 got value=13 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 319 got value(*p)=13
Before quadratic key = 319 got value=13 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 319 got value(*pq)=13 Before double hashing key = 319 value=13 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 319 value*pdh=13 Before linear key = 333 got value=14 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 333 got value(*p)=14
Before quadratic key = 333 got value=14 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 333 got value(*pq)=14 Before double hashing key = 333 value=14 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 333 value*pdh=14 Before linear key = 377 got value=15 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 377 got value(*p)=15
Before quadratic key = 377 got value=15 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 377 got value(*pq)=15 Before double hashing key = 377 value=15 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 377 value*pdh=15 Before linear key = 379 got value=16 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 0 3.after get LinearProbingHash.collision = 0 After linear key = 379 got value(*p)=16
Before quadratic key = 379 got value=16 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 0
3.after get QuadraticProbingHash.collision = 0
After quadratic key = 379 got value(*pq)=16 Before double hashing key = 379 value=16 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 0
3.after get DoubleHashingProbingHash.collision = 0
After double hashing key = 379 value*pdh=16 Before linear key = 392 got value=17 1.before put LinearProbingHash.collision = 0 2.after put LinearProbingHash.collision = 1 3.after get LinearProbingHash.collision = 2 After linear key = 392 got value(*p)=17
Before quadratic key = 392 got value=17 1.before put QuadraticProbingHash.collision = 0
2.after put QuadraticProbingHash.collision = 1
3.after get QuadraticProbingHash.collision = 2
After quadratic key = 392 got value(*pq)=17 Before double hashing key = 392 value=17 1.before put DoubleHashingProbingHash.collision = 0
2.after put DoubleHashingProbingHash.collision = 1
3.after get DoubleHashingProbingHash.collision = 2
After double hashing key = 392 value*pdh=17 Before linear key = 440 got value=18 1.before put LinearProbingHash.collision = 2 2.after put LinearProbingHash.collision = 3 3.after get LinearProbingHash.collision = 4 After linear key = 440 got value(*p)=18
Before quadratic key = 440 got value=18 1.before put QuadraticProbingHash.collision = 2
2.after put QuadraticProbingHash.collision = 3
3.after get QuadraticProbingHash.collision = 4
After quadratic key = 440 got value(*pq)=18 Before double hashing key = 440 value=18 1.before put DoubleHashingProbingHash.collision = 2
2.after put DoubleHashingProbingHash.collision = 4
3.after get DoubleHashingProbingHash.collision = 6
After double hashing key = 440 value*pdh=18 Before linear key = 473 got value=19 1.before put LinearProbingHash.collision = 4 2.after put LinearProbingHash.collision = 4 3.after get LinearProbingHash.collision = 4 After linear key = 473 got value(*p)=19
Before quadratic key = 473 got value=19 1.before put QuadraticProbingHash.collision = 4
2.after put QuadraticProbingHash.collision = 4
3.after get QuadraticProbingHash.collision = 4
After quadratic key = 473 got value(*pq)=19 Before double hashing key = 473 value=19 1.before put DoubleHashingProbingHash.collision = 6
2.after put DoubleHashingProbingHash.collision = 6
3.after get DoubleHashingProbingHash.collision = 6
After double hashing key = 473 value*pdh=19 Before linear key = 493 got value=20 1.before put LinearProbingHash.collision = 4 2.after put LinearProbingHash.collision = 4 3.after get LinearProbingHash.collision = 4 After linear key = 493 got value(*p)=20
Before quadratic key = 493 got value=20 1.before put QuadraticProbingHash.collision = 4
2.after put QuadraticProbingHash.collision = 4
3.after get QuadraticProbingHash.collision = 4
After quadratic key = 493 got value(*pq)=20 Before double hashing key = 493 value=20 1.before put DoubleHashingProbingHash.collision = 6
2.after put DoubleHashingProbingHash.collision = 6
3.after get DoubleHashingProbingHash.collision = 6
After double hashing key = 493 value*pdh=20 Before linear key = 528 got value=21 1.before put LinearProbingHash.collision = 4 2.after put LinearProbingHash.collision = 4 3.after get LinearProbingHash.collision = 4 After linear key = 528 got value(*p)=21
Before quadratic key = 528 got value=21 1.before put QuadraticProbingHash.collision = 4
2.after put QuadraticProbingHash.collision = 4
3.after get QuadraticProbingHash.collision = 4
After quadratic key = 528 got value(*pq)=21 Before double hashing key = 528 value=21 1.before put DoubleHashingProbingHash.collision = 6
2.after put DoubleHashingProbingHash.collision = 6
3.after get DoubleHashingProbingHash.collision = 6
After double hashing key = 528 value*pdh=21 Before linear key = 570 got value=22 1.before put LinearProbingHash.collision = 4 2.after put LinearProbingHash.collision = 5 3.after get LinearProbingHash.collision = 6 After linear key = 570 got value(*p)=22
Before quadratic key = 570 got value=22 1.before put QuadraticProbingHash.collision = 4
2.after put QuadraticProbingHash.collision = 5
3.after get QuadraticProbingHash.collision = 6
After quadratic key = 570 got value(*pq)=22 Before double hashing key = 570 value=22 1.before put DoubleHashingProbingHash.collision = 6
2.after put DoubleHashingProbingHash.collision = 7
3.after get DoubleHashingProbingHash.collision = 8
etc.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help