C++

######################### Question #####################

Write a program to compute hash values of numbers given in file prog3_input.txt using hash function h(k) = k mod 10. If two numbers have the same hash value, then store the second number in the next free location. Write the computed hash values to a file named prog3_output.txt.

######################### Input File #####################

17 29 5 34 87 42 37 51 38 91

######################### Hints #####################

Algorithm:

Create an array A[10] and initialie all of its values to let's say -1

For each number you read from input file:

compute r= number%10

check if A[r] == -1 //this means the slot is available

then A[r] = number

else:

loop through indices of A starting from index r+1 until you find an empty slot. If reached index = 9 start searching from index 0

A[next available slot] = number

Walkthrough:

17 mod 10 = 7 => A[7] = 17

29 mod 10 = 9 => A[9] = 29

5 mod 10 = 5 => A[5] = 5

34 mod 10 = 4 => A[4] = 34

87 mod 10 = 7 => collision. A[7] is not empty. Next available A[8] = 87

42 mod 10 = 2 => A[2] = 42

37 mod 10 = 7 => collision A[7] not empty. A[8] not empty. A[9] not empty. A[0] = 37

51 mod 10 = 1 => A[1] = 51

38 mod 10 = 8 => collision. A[8] not empty. A[9], A[0], A[1], A[2] not empty. A[3] = 38

91 mod 10 = 1 => collision. A[1] not empty. A[2], A[3], A[4], A[5] not empty. A[6] = 91

Output file (resulting A array).

37

51

42

38

34

5

91

17

87

29

You can alternatively print only the hash values:

7

9

5

4

8

2

0

1

3

6