c) (2 points) In Assignment 2, we used an ArrayList to represent a song playlist. Why would it not be a good idea to use a hash table to represent a song playlist?

Because a user might wish to quickly sort a playlist based on different parameters (Artist, album, genre, year, etc...). If the data is stored in a hash table, the linear order of the data in the hash table is inconsistent with any "human" parameters and unsorted. In other words, with hashed storage, in order to find the "next" element, one would have to look at every hash entry, which would take O(n) time.
---------------------------------------------------------


d) (2 points) In the HashTable.HashEntry class, why does it make sense to have a setValue() method, but not a setKey() method?

Because “setting a key” doesn’t make much sense. The key is generated as a function of the data and used as an index for the hash table. There is no point in setting a key because it is computed from the Value.  

---------------------------------------------------------

e) (9 points) Test your hash table for various values of the parameter p in the PolynomialHashCode constructor, and include a selection of these tests in your HashTableTester.main(). For your selected tests, briefly discuss which values of p give a better spread of the songs over the hash table bucket, and which give a worse spread.
Your results sometimes may be ambiguous -- this is ok. Just state what your tests seem to show.

Tests were performed with ‘p’ ranging from 1 to 100. (The value 100 is actually a constant called ‘MAX’ which can be changed easily). For every values of ‘p’, the number of collisions and the % of collisions (normalized to the number of data entries) was counted and displayed. There is also a linear display of the spread of the values under the tab ‘Table Spread’. The values basically represent a linear array of the number of entries in the buckets, where the bucket number would be the array index.
For example, the following results:

p = 3	Collisions:21	%:58
Table spread:
 0 2 0 1 1 3 1 1 4 0 0 0 1 2 4 5 3 2 2 4

Mean that for p = 3, there were 21 collisions, totaling 58% of the entries in the hash table. The line with numbers means that bucket zero has 0 entries, bucket one has 2 entries, bucket two has 0 entries, bucket three has 1 entry, bucket four has 1 entry, etc…

The full results are presented at the end of this document.
 
Discussion of the results: 
Considering the fact that the song collection tested contained 37 entries, the minimum % of collisions on a 20 entry hash table is 17/36 = 47%. It seems that the best spreads are obtained when p is an odd number (Can’t explain why…?). For most odd numbers tested, the collision rate was in the low 50% or high 40%, which is as low as it is observed. For even numbers, the collision rates were in the 80% and up. 
The lowest collision rates observed was at p = 7, with 47% of collisions, meaning a perfect first order spread. The highest collision rate was when p = 64, with a collision rate of 97% meaning that all the entries were in the same bucket (Even though 100% of the entries are in the same bucket, the first one to get there did not generate a collision since the bucket was empty, hence the maximum of 97% collision rate).

---------------------------------------------------------


 f) (2 points) Describe what the getHashCode() method of class PolynomialHashCode doeswhen p = 1. For what kinds of data might this hash function work poorly?

When p = 1, the method returns a sum of the UTF-16 binary representations of every letter present in the string.
This would be a bad thing to use for entries which use the same size of strings and/or a restrained number of UTF characters, For example, if the strings are years, the value pool is restrained to UTF ‘0’ to ‘9’, and since every character has the same weight in the function, the probability to get a hash collision is incremented by a factor of 10C4 = 210. This is the equivalent of the ‘Birthday Paradox’ used to perform differential attacks in cryptanalysis.




---------------------------------------------------------
Raw data collected for 0 < p < 100





p = 1	Collisions:19	%:52
Table spread:
 1 2 0 4 2 4 4 1 2 0 3 1 2 1 0 2 1 3 1 2

p = 2	Collisions:31	%:86
Table spread:
 5 0 0 0 6 0 0 0 5 0 0 0 12 0 0 0 8 0 0 0

p = 3	Collisions:21	%:58
Table spread:
 0 2 0 1 1 3 1 1 4 0 0 0 1 2 4 5 3 2 2 4

p = 4	Collisions:31	%:86
Table spread:
 20 0 0 0 1 0 0 0 8 0 0 0 4 0 0 0 3 0 0 0

p = 5	Collisions:22	%:61
Table spread:
 0 2 2 2 2 1 2 3 5 6 3 0 2 2 0 3 0 1 0 0

p = 6	Collisions:31	%:86
Table spread:
 5 0 0 0 5 0 0 0 12 0 0 0 5 0 0 0 9 0 0 0

p = 7	Collisions:17	%:47
Table spread:
 4 5 2 1 1 1 1 3 3 1 0 3 2 1 1 2 1 2 1 1

p = 8	Collisions:32	%:88
Table spread:
 29 0 0 0 3 0 0 0 1 0 0 0 3 0 0 0 0 0 0 0

p = 9	Collisions:20	%:55
Table spread:
 1 2 3 3 1 2 2 2 0 2 0 2 1 2 3 2 5 0 0 3

p = 10	Collisions:31	%:86
Table spread:
 9 0 0 0 4 0 0 0 12 0 0 0 8 0 0 0 3 0 0 0

p = 11	Collisions:18	%:50
Table spread:
 0 0 2 2 2 2 2 1 2 2 2 3 2 2 2 2 1 1 1 5

p = 12	Collisions:31	%:86
Table spread:
 26 0 0 0 1 0 0 0 4 0 0 0 2 0 0 0 3 0 0 0

p = 13	Collisions:18	%:50
Table spread:
 0 1 1 2 1 3 0 2 1 3 6 1 1 3 2 2 3 1 1 2

p = 14	Collisions:31	%:86
Table spread:
 9 0 0 0 6 0 0 0 11 0 0 0 6 0 0 0 4 0 0 0

p = 15	Collisions:18	%:50
Table spread:
 1 1 2 2 1 2 2 4 3 3 2 2 1 3 0 2 1 0 3 1

p = 16	Collisions:32	%:88
Table spread:
 33 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0

p = 17	Collisions:19	%:52
Table spread:
 2 3 3 0 1 4 2 4 1 1 0 2 1 4 1 1 3 1 2 0

p = 18	Collisions:31	%:86
Table spread:
 6 0 0 0 5 0 0 0 11 0 0 0 5 0 0 0 9 0 0 0

p = 19	Collisions:18	%:50
Table spread:
 0 1 2 1 0 3 3 2 1 2 3 3 2 3 3 1 1 2 1 2

p = 20	Collisions:31	%:86
Table spread:
 25 0 0 0 1 0 0 0 5 0 0 0 2 0 0 0 3 0 0 0

p = 21	Collisions:18	%:50
Table spread:
 0 3 1 1 0 2 2 1 1 3 1 3 3 2 1 1 4 3 3 1

p = 22	Collisions:31	%:86
Table spread:
 9 0 0 0 8 0 0 0 5 0 0 0 8 0 0 0 6 0 0 0

p = 23	Collisions:19	%:52
Table spread:
 3 2 1 0 3 4 3 2 2 2 0 2 1 2 1 1 2 4 0 1

p = 24	Collisions:32	%:88
Table spread:
 30 0 0 0 4 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0

p = 25	Collisions:20	%:55
Table spread:
 1 1 4 6 0 1 3 2 1 1 1 4 2 1 4 2 0 2 0 0

p = 26	Collisions:31	%:86
Table spread:
 7 0 0 0 2 0 0 0 13 0 0 0 7 0 0 0 7 0 0 0

p = 27	Collisions:19	%:52
Table spread:
 0 2 2 1 0 2 2 2 1 2 2 3 3 1 0 3 2 1 4 3

p = 28	Collisions:31	%:86
Table spread:
 20 0 0 0 4 0 0 0 5 0 0 0 3 0 0 0 4 0 0 0

p = 29	Collisions:19	%:52
Table spread:
 2 4 0 2 1 2 3 2 4 2 0 1 0 1 3 2 1 3 2 1

p = 30	Collisions:31	%:86
Table spread:
 9 0 0 0 8 0 0 0 4 0 0 0 6 0 0 0 9 0 0 0

p = 31	Collisions:17	%:47
Table spread:
 1 0 2 1 2 2 1 1 1 1 1 2 2 5 3 3 2 4 1 1

p = 32	Collisions:34	%:94
Table spread:
 35 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p = 33	Collisions:19	%:52
Table spread:
 1 0 3 2 2 3 4 2 1 2 0 1 1 3 0 4 3 2 1 1

p = 34	Collisions:31	%:86
Table spread:
 9 0 0 0 7 0 0 0 7 0 0 0 6 0 0 0 7 0 0 0

p = 35	Collisions:19	%:52
Table spread:
 1 0 1 3 3 2 3 1 0 3 1 1 3 5 1 2 3 2 0 1

p = 36	Collisions:31	%:86
Table spread:
 19 0 0 0 4 0 0 0 8 0 0 0 4 0 0 0 1 0 0 0

p = 37	Collisions:19	%:52
Table spread:
 2 1 0 2 3 3 3 1 1 3 0 2 2 3 2 1 0 2 3 2

p = 38	Collisions:31	%:86
Table spread:
 10 0 0 0 9 0 0 0 6 0 0 0 5 0 0 0 6 0 0 0

p = 39	Collisions:18	%:50
Table spread:
 4 2 0 3 3 2 2 1 2 1 1 4 1 2 1 2 2 2 0 1

p = 40	Collisions:32	%:88
Table spread:
 29 0 0 0 2 0 0 0 4 0 0 0 0 0 0 0 1 0 0 0

p = 41	Collisions:19	%:52
Table spread:
 2 2 1 2 2 2 4 1 0 1 3 2 2 3 0 2 2 3 0 2

p = 42	Collisions:31	%:86
Table spread:
 9 0 0 0 4 0 0 0 7 0 0 0 10 0 0 0 6 0 0 0

p = 43	Collisions:20	%:55
Table spread:
 3 2 1 0 3 3 3 0 0 3 1 1 0 2 1 3 2 3 2 3

p = 44	Collisions:32	%:88
Table spread:
 23 0 0 0 4 0 0 0 4 0 0 0 5 0 0 0 0 0 0 0

p = 45	Collisions:17	%:47
Table spread:
 3 1 1 1 1 3 1 3 1 2 2 1 0 4 2 1 3 3 2 1

p = 46	Collisions:31	%:86
Table spread:
 6 0 0 0 7 0 0 0 10 0 0 0 3 0 0 0 10 0 0 0

p = 47	Collisions:20	%:55
Table spread:
 1 3 4 1 3 3 0 0 1 3 3 2 2 1 2 1 0 3 0 3

p = 48	Collisions:34	%:94
Table spread:
 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0

p = 49	Collisions:18	%:50
Table spread:
 2 4 2 2 2 1 0 1 2 2 2 5 1 1 1 2 2 2 2 0

p = 50	Collisions:31	%:86
Table spread:
 10 0 0 0 8 0 0 0 10 0 0 0 4 0 0 0 4 0 0 0

p = 51	Collisions:20	%:55
Table spread:
 1 0 3 0 2 3 3 2 2 1 0 4 2 1 1 2 2 5 0 2

p = 52	Collisions:31	%:86
Table spread:
 23 0 0 0 3 0 0 0 7 0 0 0 2 0 0 0 1 0 0 0

p = 53	Collisions:20	%:55
Table spread:
 1 4 3 2 2 2 0 2 4 0 0 4 1 2 2 2 1 2 2 0

p = 54	Collisions:31	%:86
Table spread:
 8 0 0 0 9 0 0 0 7 0 0 0 7 0 0 0 5 0 0 0

p = 55	Collisions:19	%:52
Table spread:
 2 4 2 1 1 1 1 2 0 4 3 2 2 5 1 0 1 1 3 0

p = 56	Collisions:32	%:88
Table spread:
 31 0 0 0 3 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0

p = 57	Collisions:19	%:52
Table spread:
 1 2 5 1 2 1 1 3 1 0 1 0 0 3 1 7 1 2 3 1

p = 58	Collisions:31	%:86
Table spread:
 5 0 0 0 11 0 0 0 8 0 0 0 5 0 0 0 7 0 0 0

p = 59	Collisions:19	%:52
Table spread:
 1 2 2 1 2 2 0 3 2 4 4 1 0 0 2 3 2 1 1 3

p = 60	Collisions:31	%:86
Table spread:
 21 0 0 0 4 0 0 0 6 0 0 0 1 0 0 0 4 0 0 0

p = 61	Collisions:17	%:47
Table spread:
 3 3 1 4 3 2 1 1 1 2 1 2 0 1 2 2 2 1 2 2

p = 62	Collisions:31	%:86
Table spread:
 5 0 0 0 3 0 0 0 14 0 0 0 6 0 0 0 8 0 0 0

p = 63	Collisions:19	%:52
Table spread:
 2 2 1 1 0 2 2 3 4 3 1 3 1 2 2 1 0 0 3 3

p = 64	Collisions:35	%:97
Table spread:
 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p = 65	Collisions:18	%:50
Table spread:
 2 3 1 2 1 1 1 1 5 2 1 0 1 0 1 3 1 4 2 4

p = 66	Collisions:31	%:86
Table spread:
 9 0 0 0 8 0 0 0 8 0 0 0 5 0 0 0 6 0 0 0

p = 67	Collisions:18	%:50
Table spread:
 1 2 0 2 1 2 2 2 1 2 1 2 2 0 2 4 2 1 4 3

p = 68	Collisions:31	%:86
Table spread:
 21 0 0 0 3 0 0 0 7 0 0 0 3 0 0 0 2 0 0 0

p = 69	Collisions:20	%:55
Table spread:
 0 1 0 4 1 2 1 1 0 4 3 3 2 1 3 3 2 0 4 1

p = 70	Collisions:31	%:86
Table spread:
 7 0 0 0 6 0 0 0 7 0 0 0 9 0 0 0 7 0 0 0

p = 71	Collisions:19	%:52
Table spread:
 2 1 2 3 1 3 1 2 0 1 1 2 0 2 3 1 3 5 3 0

p = 72	Collisions:32	%:88
Table spread:
 29 0 0 0 3 0 0 0 1 0 0 0 0 0 0 0 3 0 0 0

p = 73	Collisions:18	%:50
Table spread:
 1 4 0 3 1 2 3 2 2 3 2 1 1 1 3 0 1 1 2 3

p = 74	Collisions:31	%:86
Table spread:
 5 0 0 0 8 0 0 0 11 0 0 0 5 0 0 0 7 0 0 0

p = 75	Collisions:21	%:58
Table spread:
 3 0 2 6 0 2 3 2 0 2 3 1 0 2 1 1 4 3 0 1

p = 76	Collisions:31	%:86
Table spread:
 24 0 0 0 2 0 0 0 3 0 0 0 5 0 0 0 2 0 0 0

p = 77	Collisions:21	%:58
Table spread:
 1 0 0 2 1 0 0 3 4 2 2 4 2 1 4 1 0 2 2 5

p = 78	Collisions:31	%:86
Table spread:
 9 0 0 0 9 0 0 0 4 0 0 0 7 0 0 0 7 0 0 0

p = 79	Collisions:22	%:61
Table spread:
 0 2 3 0 1 1 2 1 2 0 0 6 3 1 2 3 3 0 0 6

p = 80	Collisions:33	%:91
Table spread:
 33 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0

p = 81	Collisions:18	%:50
Table spread:
 1 2 3 1 1 3 2 0 3 2 1 4 1 2 0 3 2 1 2 2

p = 82	Collisions:31	%:86
Table spread:
 6 0 0 0 4 0 0 0 8 0 0 0 12 0 0 0 6 0 0 0

p = 83	Collisions:19	%:52
Table spread:
 2 1 1 1 3 1 2 2 2 0 0 2 0 4 1 2 1 3 4 4

p = 84	Collisions:32	%:88
Table spread:
 25 0 0 0 3 0 0 0 3 0 0 0 5 0 0 0 0 0 0 0

p = 85	Collisions:17	%:47
Table spread:
 1 2 3 2 2 1 2 2 1 3 0 3 2 2 2 2 2 2 1 1

p = 86	Collisions:31	%:86
Table spread:
 11 0 0 0 8 0 0 0 4 0 0 0 3 0 0 0 10 0 0 0

p = 87	Collisions:18	%:50
Table spread:
 2 2 1 0 2 1 1 7 1 2 4 3 1 2 1 1 3 1 0 1

p = 88	Collisions:33	%:91
Table spread:
 30 0 0 0 3 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0

p = 89	Collisions:19	%:52
Table spread:
 3 5 3 1 1 1 0 3 2 0 2 5 2 2 1 2 1 0 1 1

p = 90	Collisions:31	%:86
Table spread:
 10 0 0 0 6 0 0 0 8 0 0 0 4 0 0 0 8 0 0 0

p = 91	Collisions:20	%:55
Table spread:
 3 2 2 0 3 1 0 2 1 2 3 1 0 3 1 5 3 1 0 3

p = 92	Collisions:31	%:86
Table spread:
 22 0 0 0 3 0 0 0 5 0 0 0 2 0 0 0 4 0 0 0

p = 93	Collisions:21	%:58
Table spread:
 4 2 3 3 0 2 2 1 2 2 0 2 0 1 1 0 0 6 4 1

p = 94	Collisions:31	%:86
Table spread:
 9 0 0 0 4 0 0 0 8 0 0 0 5 0 0 0 10 0 0 0

p = 95	Collisions:21	%:58
Table spread:
 1 0 0 1 1 1 0 3 3 0 1 2 3 0 2 2 3 5 2 6

p = 96	Collisions:34	%:94
Table spread:
 35 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p = 97	Collisions:20	%:55
Table spread:
 3 3 3 0 4 3 0 5 1 3 1 1 1 1 3 2 0 1 0 1

p = 98	Collisions:31	%:86
Table spread:
 5 0 0 0 5 0 0 0 6 0 0 0 9 0 0 0 11 0 0 0

p = 99	Collisions:20	%:55
Table spread:
 1 1 0 0 1 2 4 2 1 4 5 0 2 3 1 2 0 1 1 5