Description
1. Draw the 11-entry hash table that results from using the has function, h(i) = (3i+5) mod 11, to hash
the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by separate chaining
approach (using a linked list in each bucket in a hash table)
Programming Assignment (80 points)
2. Your task in this programming assignment is to create a hash table (its size is 128), read words from an input
file, convert each word to a hash value, and store each word to the hash value index of the hash table. The
collisions are handled by separate chaining approach (again, using a linked list in each bucket in the hash table).
In the end of your program, extract all words from the hash table (from index 0 to 127), and print out each
distinct word with its frequency.
Input File
An input file hw4_input.txt contains a word in each line as follows:
to
be
or
not
to
be
…
…
Hash Table
The hash table itself is essentially an array of linked lists. The array indices are the same as the hash values.
Hash Function
The hash function you will use is extremely simple: it will go through the string a character at a time, convert
each character to an integer (a.k.a. ASCII value), add up the integer values, and return the sum modulo 128.
This will give an integer in the range of [0, 127]. This is a poor hash function. However, it’s simple to
implement. Note that a value of type char in a C++ program can also be treated as if it were an int, because
internally it’s a one-byte integer represented by the ASCII character encoding. If you like, you can convert the
char to an int explicitly using a type cast. However, a string of characters is not an int, and you can’t use
atoi to convert it into one. You also shouldn’t try to type cast the string to an int (it’ll just cast the address into
an integer, which might work but it’s not what you want). A string is an array of chars, which is not the same as
a single char; keep that in mind. So you’ll need a loop to go through the string character-by-character. Your
program will use a hash table to count the number of occurrences of words in a text file. The basic algorithm
goes as follows. For each word in the file:
1. Convert it to a hash value.
2. Insert the word to a linked list in a hash value index of the hash table
Output
At the end of the program, you should output all the words in the file, one per line, with the count next to the
word e.g.
cat 2
hat 4
green 12
eggs 3
ham 5
algorithmic 14
deoxyribonucleic 3
dodecahedron 400
What to turn in:
Include your name and A number at the top of each file (PDF and the programming file).
Compress the files (i) your answer note for questions 1 and 2 in PDF file format; and (ii) your
hashtable.cpp. You may include additional files (e.g., .h file) for the question 2.
Name the compressed file as hw04_FIRSTNAME_LASTNAME.zip. For example, if your name is
John Smith, name the file as hw04_John_Smith.zip. Submit the compressed file to Canvas.
Make sure all your programs are fully commented, and compile and run correctly.
This is an individual assignment, but you may discuss general strategies and approaches with
other members of the class (refer to the syllabus for details of the homework collaboration
policy). If you discussed an assignment with your colleague, explicitly report the colleague’s name and
what you discussed in your submission.
Follow Code of Conduct (refer to the syllabus for details).
