A good hash function h(x) behaves in practice very close to the simple uniform hashing assumption analyzed in class, but is a deterministic function. Designing good hash functions is hard, and a bad hash function can cause a hash table to quickly exit the sparse loading regime by overloading some buckets and under-loading others. Good hash functions often rely on beautiful and complicated insights from number theory, and have deep connections to pseudorandom number generators and cryptographic functions. In practice, most hash functions are moderate to poor approximations of uniform hashing. Consider the following two hash functions. Let U be the universe of strings composed of the characters from the alphabet Σ = [A, . . . ,Z], and let the function f(xi) return the index of a letter xi ∈ Σ, e. g., f(A) = 1 and f(Z) = 26. Let x be a string of length m.

(1) The first hash function we consider is h1(x) = [Pm i=1 f(xi)] mod `, where ` is the number of buckets in the hash table.

(2) For the second hash function, first—globally, external to the hash function— choose uniformly random integers ai (one for each xi ∈ Σ) from {0, . . . ,10,000}, and then define h2(x) = [Pm i=1 ai · f(xi)] mod `. List your values of ai here: (and please use consistent values of ai throughout this question)

(a) There is a txt file on Canvas that contains US Census derived last names. Using these names as input strings, first choose a uniformly random 50% of these name strings. Let ` = 5851 be the number of buckets. For each of the two hash functions (separately), produce a histogram showing the distribution of hash locations for the names you chose. Label the axes of your figures. Give a brief description of what the figure shows about h1(x) and h2(x); justify your results in terms of the behavior of these hash functions. Hint: the raw file includes information other than the name strings, which will need to be removed; and, think about how you can count hash locations without building or using a real hash table.

(b) State at least 4 reasons why h1(x) is a bad hash function relative to the ideal behavior of uniform hashing

(c) Produce two plots—one for each hash function h1, h2—showing the length of the longest chain (were we to use chaining for resolving collisions) as a function of the number n of these strings that we hash into a table with ` = 5851 buckets. That is, you may use the 50% of names from part (a), and as you hash them one by one, show how the length of the longest chain is growing

(d) Produce another pair of plots—one for each of h1, h2—showing the number of collisions as a function of `. Comment on how collisions decrease as ` increases. Aside from size, do you notice any particular kinds of values for ` that seem better than others? (e. g. odd/even, prime, etc.) Discuss briefly.