(JAVA) Part #1: Design a simple hash table

Design a simple hash table that uses linear probing to store strings. The hash function will just be the length of the string, so hello would hash to index position five.

Make the hash table an array of size ten and populate it with words from short quotes or sentences.

Test your function against the following quotes:

-fourscore and seven years ago

-jack and jill went up the hill

-happiness depends upon ourselves (this one will force the search back to the start of the table)

Print out the hash table each time to verify it works correctly.

Sample output shown here:

original line: [fourscore, and, seven, years, ago]

Hash table with Linear Probing:

table[0]: null

table[1]: null

table[2]: null

table[3]: and

table[4]: ago

table[5]: seven

table[6]: years

table[7]: null

table[8]: null

table[9]: fourscore

Part #2: Data Collisions

Your goal in this lab is to count the number of data collisions that occur in a small hash table (size 100) populated with random strings. To generate the strings, use Math.random() or java.util.Random to create 100 words all of the same length (five) consisting of random characters.

You will use a modified version of the hashCode() function for strings. Since hashCode() returns values that are quite large (over a million) you will need to scale it to a smaller size for this lab. Use the following formula for the hash function:

String.hashCode() % iSize (where iSize=100)

This will scale the large hash values down so they will fit in an array of size 100.

As you populate the array you will need to check if an index is already populated. If it is, you have found a data collision. At that point, you should increase a counter to track how many collisions are generated.

The program should print out all 100 strings followed by their hash codes. It should also print 100 boolean values (true/false) indicating if an index position is populated or not. Finally it should print the total number of collisions that occurred.

Sample ouput for a smaller array size of ten is below:

0: [bkwud] h1: 1

1: [gqvgf] h1: 9

2: [eeocu] h1: 9

---collision---

3: [tongl] h1: 8

4: [mgdim] h1: 6

5: [edzyu] h1: 1

---collision---

6: [swick] h1: 5

7: [vqeuj] h1: 5

---collision---

8: [xerte] h1: 2

9: [vccvx] h1: 4

----------

hash table[0]: false

hash table[1]: true

hash table[2]: true

hash table[3]: false

hash table[4]: true

hash table[5]: true

hash table[6]: true

hash table[7]: false

hash table[8]: true

hash table[9]: true

----------

collisons found: 3