You will implement an efficient hopscotch hash table using C++ that improves on the classic linear probing algorithm. Specifically, you will use a TABLE_SIZE = 17 and use the single hash function (X) = X mod TABLE_SIZE. You shall resolve collisions using linear probing where the maximal length of the probe sequence (i.e., distance away from the original hash location) is bound by the hopscotch hashing algorithm where MAX_DIST = 4.

You shall support the following five operations that are menu driven:

1. Insert Value

2. Delete Value

3. Search Value

4. Output Table

5. Exit Program

All data shall be entered through the console and consist of integers. You may assume valid data, though data may be out of range (i.e., zero, negative integers or possibly out of range of menu options). Your algorithm to find the next available slot is bound by the end of the table so that the linear probe sequence need not be circular. In other words, you do not need to wrap around beyond the last element of the array to the first for either the linear probe or the bound for the hopscotch algorithm. For example, if the user attempts to insert 33 which hashes to index position 16 (i.e., 33 % TABLE_SIZE) in the array, but an element already exists at that location, the insert will fail as there are no more array locations beyond this to attempt to insert the element. You must keep an item array containing the elements as well as an associated hop array that indicates positions in the item array that are occupied with items that hash to the same value. You should also provide specific feedback to the user on successful operations or when an operation failed. The search should utilize the hash value and then perhaps a linear probe of MAX_DIST 1 index locations, but you should not simply search the entire array to accomplish this operation. Be sure to handle the case that requires multiple hops (i.e., using recursion) to get the value within the correct range.

CSCE3110 Data Structures & Algorithms Fall 2017 rogramming Assignment 2 Due: 119 PM on Wednesday, November 15, 2017 You will implement an efficient hopsootch hash table using Cthat improves on the classic linear probing algorithm. Specifically, you will use a TABLE_SIZE 17 and use the single hash function h(x) = x mod TABLE-SIZE, You shall resolve collisions using linear probing where the maximal length of the probe sequence (ie., distance away from the original hash location) is bound by the hopscotch hashing algorithm wbere Ax DIST4. You shall support the following five operations that are menu driven: . Insert Value 2. Delete Value 3. Search Value 4. Output Table 5. Exit Program All data shall be entered through the console and consist of integers. You may assume valid data, though data may be out of range (i.e., zero, negative integers or possibly out of range of mernu options). Your algorithn to find the next available slot is bound by the end of the table so thai the linear probe sequence need not be circular. In other words, you do not need to wrap around beyond the last clement of the array to the first for either the lincar probe oe the bound for the hopscotch algorithm For cxample, if the user attempts to insert 33 which hasbes to index position 16 (ie., 33 % TABLE SIZE) in the array, but an element already exists at that location, the insert will fail as there are no more array locations beyond this to attempt to insert the element. You must keep an item array containing the elements as well as an associated hop array that indicates positions in the item array that are occupied with items that hash to the same value. You should also provide specific feedback to the user on successful operations or when an operation failed. The search should utilize the hash value and then perhaps a linear probe of NAX DIST -l index locatios, but you should not simply search he entire array to accomplish this operation. Be sure to handle the case that requires multiple hops(ie., using recursion) to get the value within the correct rangc. SAMPLE OUTPUT (input in bold green): $Ja.out HOPSCOTCH HASHING MENU 1-Insert Value 2 Delete Value 3 Search Value 4-Output Table 5 - Exit Program 1 of 6