CSCI 2320 Data Structure Final ProjectHash Tables with Quadratic probing and Double Hashing Executive Summary:A hash table is a data structure that uses a hash function to efficiently map certainidentifiers or keys (e.g., person names) to associated values (e.g., their telephonenumbers). The hash function is used to transform the key into the index (the hash) of anarray element (the slot or bucket) where the corresponding value is to be sought.You are asked to use quadratic probing and double hashing to implement the hashfunction with a given action file. Project Objective: in completing this project, you will- Enhance your ability to hash tables- Familiar with different probing approaches- Enable yourself to perform the analysis of different hash function with the samegiven array sizeDue Dates and Honor:This project will be due by the beginning of the class on Thursday Apr/29/2010.This is an independent programming project, and it is very important that you understandand abide by the policy concerning programming projects. Remember, your personalhonor and integrity is far more important than your grade on the project. Detailed Specification:1. Download the action file and read the file in your program 2. Create an empty array with size 2003. Write a quadratic probing function (h(k, i ) = (h(k) + c1*i + c2*i^2) mod 200)with function parameter m for hash function (h(k) = k mod m) and c1 and c2changeable.4. Write a double hashing function (h(k, i ) = (h1(k) + ih2(k)) mod 200) withfunction parameter m1 for hash function (h1(k) = k mod m1) and m2 for hashfunction (h2(k) = k mod m2) changeable.After you finished all functions, following are the things you need to carry out:1. For the reading action file, if you see the number for the first time, it indicates the action is store the value in the hash table. If the value is already stored in the hash table, it indicates the action is delete the value.2. Use quadratic probing approach to deal with the action file, while m=211, c1=1, c2=0. Record the total probe# and calculate the average probe#.3. Use quadratic probing approach to deal with the action file, while m=211, c1=0, c2=1. Record the total probe# and calculate the average probe#.4. Use quadratic probing approach to deal with the action file, while m=211, c1=1, c2=2. Record the total probe# and calculate the average probe#.5. Use double hashing approach to deal with the action file, while m1=211,m2=113. Record the total probe# and calculate the average probe#.6. Try some other parameters in quadratic probing approach to see if the total probe# is reduced7. Try some other parameters in double hashing approach to see if the total probe# is reducedWhat to Submit:- A print out results of your program (it should contain the probe approach,parameters setup, total probe# and average probe#).- Source code of your
View Full Document
Unlocking...