1- We plan to use this hash function to hash ~ half million words into an array

ID: 3768237 • Letter: 1

Question

1- We plan to use this hash function to hash ~ half million words into an array of size ~ a million and

we want to keep collisions of unequal words to a minimum. Words are considered equal if they match

exactly while ignoring the letter case (e.g. AbCd and abcd are equal).

int hash(String str, int arraySize) {

int h=0;

for (int i=0; i<str.length(); i++)

h+=orderInAlphabet(str.charAt(i));

return h % arraySize;

}

orderInAlphabet is an O(1) time method that returns an int equal to the order in the English alphabet of

the given letter. E.g.:

orderInAlphabet('a') 1

orderInAlphabet('A') 1

orderInAlphabet('b') 2

orderInAlphabet('c') 3

a- Is this hash function functionally correct? Yes_____ No ______

Specifically, does it guarantee that equal words have equal hash values? Explain your answer

succinctly below:

b- Is this a good hash function for what we plan to use it for? Yes_____ No ______

Specifically, is it uniformly distributing? If yes, briefly and clearly explain why. If no, briefly and

clearly explain which part(s) of the array it has a preference for (i.e. it will hash more words there).

c- If we use a hash table implemented using separate chaining, give a rough estimate of the typical

chain lengths this hash function would generate if words are 1-10 letters, the average letter has an

alphabet order of 10, and we are hashing 500,000 words. State your assumptions (if you make any) and

perform some simple math; no complicated probabilistic analysis. Briefly show your work:

1- We plan to use this hash function to hash ~ half million words into an array

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.