zip

CSCE 3110 Project 3 – Hopscotch Hash Table Solved

30.00 $

Category:

Description

5/5 - (2 votes)

PROGRAM DESCRIPTION

In this C++ program, you will implement an efficient hopscotch hash table that improves on the classic linear probing algorithm. Specifically, you will use a TABLE_SIZE = 17 and use the single hash function ℎ(𝑥) = 𝑥 mod 𝑇𝐴𝐵𝐿𝐸_𝑆𝐼𝑍𝐸. 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 hash 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.

REQUIREMENTS

  • Your code should be well documented in terms of comments. For example, good comments in general consist of a header (with your name, course section, date, and brief description), comments for each variable, and commented blocks of code.
  • Your program will be graded based largely on whether it works correctly on the CSE machines (e.g., cse01, cse02, …, cse06), so you should make sure that your program compiles and runs on a CSE machine.
  • You should contact your instructor if there is any question about what is being asked for.
  • This is an individual programming assignment that must be the sole work of the individual student. Any instance of academic dishonesty will result in a grade of “F” for the course, along with a report filed into the Academic Integrity Database.

SAMPLE OUTPUT (input in bold):

$ ./a.out

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 5

5 inserted at position 5.

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 7

ERROR: Please select operation between 1 and 5, inclusively.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 6

6 inserted at position 6.

HOPSCOTCH HASH MENU: 1 – Insert Value

2  – Delete Value

  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 22

22 inserted at position 7.

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 23

23 inserted at position 8.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE: +——————+

|  # | item |  hop |

+——————+

|  0 |      | 0000 |

|  1 |      | 0000 |

|  2 |      | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |    5 | 1010 |

|  6 |    6 | 1010 |

|  7 |   22 | 0000 |

|  8 |   23 | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |      | 0000 |

| 15 |      | 0000 |

| 16 |      | 0000 |

+——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 39

39 inserted at position 6.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE: +——————+

|  # | item |  hop |

+——————+

|  0 |      | 0000 |

|  1 |      | 0000 |

|  2 |      | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 | |  5 |    5 | 1110 |

|  6 |   39 | 0011 |

|  7 |   22 | 0000 |

|  8 |   23 | 0000 |

|  9 |    6 | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |      | 0000 |

| 15 |      | 0000 | | 16 |      | 0000 |

+——————+ HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 56 ERROR: Unable to insert 56 into Hash Table: Hopscotch Hash Failed

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 3

Enter positive integer value to search for in Hopscotch Hash Table: 39

39 found at position 6.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 2

Enter positive integer value to delete from Hopscotch Hash Table: 6

  • deleted from position 9.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |      | 0000 |

|  1 |      | 0000 |

|  2 |      | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |    5 | 1110 |

|  6 |   39 | 0010 |

|  7 |   22 | 0000 |

|  8 |   23 | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 | | 14 |      | 0000 | | 15 |      | 0000 |

| 16 |      | 0000 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 19

19 inserted at position 2.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 50

50 inserted at position 16.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 56

56 inserted at position 8.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |      | 0000 |

|  1 |      | 0000 |

|  2 |   19 | 1000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |    5 | 1111 |

|  6 |   39 | 0001 |

|  7 |   22 | 0000 |

|  8 |   56 | 0000 |

|  9 |   23 | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 | | 13 |      | 0000 | | 14 |      | 0000 |

| 15 |      | 0000 |

| 16 |   50 | 1000 | +——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: -5

Enter positive integer value to insert into Hopscotch Hash Table: 16 ERROR: Unable to insert 16 into Hash Table: Linear Probe Failed

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 5

Program terminated by user…

BONUS OPPORTUNITY:

  • For those students who have completed all the requirements, you may attempt to add circular functionality to the linear probe (i.e., not just to the end of the table) for up to 15 bonus points.
  • SAMPLE OUTPUT for BONUS showing circular table rolling over (input in bold):

$ ./a.out

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 16

16 inserted at position 16.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 15

15 inserted at position 15.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value

 

Enter positive integer value to insert into Hopscotch Hash Table: 33

33 inserted at position 0.

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |   33 | 0000 |

|  1 |      | 0000 |

|  2 |      | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |      | 0000 |

| 15 |   15 | 1000 |

| 16 |   16 | 1100 |

+——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 50

50 inserted at position 1.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE: +——————+ |  # | item |  hop | +——————+ |  0 |   33 | 0000 |

|  1 |   50 | 0000 |

|  2 |      | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |      | 0000 |

| 15 |   15 | 1000 |

| 16 |   16 | 1110 |

+——————+ HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 32

32 inserted at position 16.

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |   33 | 0000 |

|  1 |   50 | 0000 |

|  2 |   16 | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |      | 0000 |

| 15 |   15 | 1100 |

| 16 |   32 | 0111 | +——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value

Enter positive integer value to insert into Hopscotch Hash Table: 67 ERROR: Unable to insert 67 into Hash Table: Hopscotch Hash Failed

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |   33 | 0000 |

|  1 |   50 | 0000 |

|  2 |   16 | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |      | 0000 |

| 15 |   15 | 1100 |

| 16 |   32 | 0111 |

+——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 14

14 inserted at position 14.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE: +——————+ |  # | item |  hop | +——————+ |  0 |   33 | 0000 |

|  1 |   50 | 0000 |

|  2 |   16 | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 | |  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |   14 | 1000 |

| 15 |   15 | 1100 |

| 16 |   32 | 0111 |

+——————+ HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 1

Enter positive integer value to insert into Hopscotch Hash Table: 31 ERROR: Unable to insert 31 into Hash Table: Hopscotch Hash Failed

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |   33 | 0000 |

|  1 |   50 | 0000 |

|  2 |   16 | 0000 |

|  3 |      | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |   14 | 1000 |

| 15 |   15 | 1100 |

| 16 |   32 | 0111 | +——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value

Enter positive integer value to insert into Hopscotch Hash Table: 17

17 inserted at position 3.

HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE:

+——————+

|  # | item |  hop |

+——————+

|  0 |   33 | 0001 |

|  1 |   50 | 0000 |

|  2 |   16 | 0000 |

|  3 |   17 | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |   14 | 1000 |

| 15 |   15 | 1100 |

| 16 |   32 | 0111 |

+——————+ HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 2

Enter positive integer value to delete from Hopscotch Hash Table: 32

32 deleted from position 16.

HOPSCOTCH HASH MENU:

  • – Insert Value
  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 4

HOPSCOTCH HASH TABLE: +——————+ |  # | item |  hop | +——————+ |  0 |   33 | 0001 |

|  1 |   50 | 0000 |

|  2 |   16 | 0000 |

|  3 |   17 | 0000 |

|  4 |      | 0000 |

|  5 |      | 0000 |

|  6 |      | 0000 |

|  7 |      | 0000 |

|  8 |      | 0000 |

|  9 |      | 0000 |

| 10 |      | 0000 |

| 11 |      | 0000 |

| 12 |      | 0000 |

| 13 |      | 0000 |

| 14 |   14 | 1000 |

| 15 |   15 | 1000 |

| 16 |      | 0111 |

+——————+ HOPSCOTCH HASH MENU: 1 – Insert Value

  • – Delete Value
  • – Search Value
  • – Output Table
  • – Exit Program

Enter operation to perform: 5 Program terminated by user…

 

  • hopscotch-hashing.zip