Complete the functions and create the main method to test the functions, where an index will be computed for each bib number and if there is no collision, the bib number will be stored in the HashTable at index. Otherwise, if a collision happens, use the while loop to call the Hash function and checkCollision until no collision at the index.
This assignment needs to be done in c++ language
Case study:
An event company asks you to design the data structure and program prototype for their
running event system. The participant for the running event is expected to reach more than
1000 in various categories. You decided to use hashing function method to store the
information for each participant’s BIB number in the hash table.
To begin the problem solving, suppose that 10 registered runners need to be stored in a hash
table, HT, with a size of 13. The sample BIB number of the runners are: 101, 102, 103, 104, 107,
111, 121, 217, 157, and 185.
Furthermore, you set the hash function to determine the index of the participant in the HT as:
hash(BIB) = BIB % table size (or 13)
However, if the hash index given by hash(BIB) is already occupied (collision), the linear probing
hash function will be used as:
hash(BIB) = (Hash(BIB)+1) % 17
and, further collision with hash function:
hash(BIB) = (Hash(BIB)+2) % 17
or, hash(BIB) = (Hash(BIB) + n) % 17, where n is probe increment. Refer to the given function
description.
According to the above requirements, create a program to
1. store the participant BIB number in the hash table, and
2. find a bib number
3. print out the content of the hash table.
Given the description of the following function:
/*
Hash function to calculate the index based on the given bib,
linear probe and Hash Table size, tableSize
@param bib - is the number of a participant
@param probe - if probe is 0 then index = bib%tableSize
-else if probe>0 then index = (hash(bib)+probe)%17
@param tableSize - HT size
@return - index
*/
int Hash(int bib, int probe, int tableSize){
}
/*
Function to check if a collision happens for a particular index
computed by Hash function
@param HashTable - the hash table
@param index - index from the hash table
@return - boolean, if HashTable[index] is not 0 then return true
(collision happen), otherwise return false
*/
bool checkCollision(int HashTable[], int index){
}
a. Complete the functions and create the main method to test the functions, where an
index will be computed for each bib number and if there is no collision, the bib number
will be stored in the HashTable at index. Otherwise, if a collision happens, use the while
loop to call the Hash function and checkCollision until no collision at the index.
b. Create a function to find the bib number in the Hash Table.
c. Provide an output that shows the content of the hash table
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
