#functions
Recall that a hash function maps a (potentially infinite) domain of inputs to a finite range of outputs. A "perfect" hash function, meanwhile, is one that maps a (finite) set of inputs to a range of distinct outputs without any collisions.
Answer the below in functions.md
.
Questions

(2 points.) Consider the hash function below.
int hash(char *s) { if (s[0] >= 'A' && s[0] <= 'Z') { return s[0]  'A'; } else { return s[0]  'a'; } }
Why might a hash table, if implemented using this hash function, prove to be slow? Assume that
s
is an entirely alphabetical string of nonzero length. 
(4 points) Recall that a string is just a sequence of characters, each of which is a sequence of bits. In ASCII,
A
is thus01000001
,AB
is thus0100000101000010
, andABC
is thus010000010100001001000011
. Suppose that a hash function, given a string in ASCII as input, outputs the (decimal) integer represented by its sequence of bits. GivenA
as input, this hash function would output 65; givenAB
as input, this hash function would output16706
; and givenABC
as input, this hash function would output4276803
. Why is this hash function "perfect" by definition but imperfect in practice if implemented in C? 
(4 points.) The input to a hash function could also be a file. After all, a file is just a sequence of bits, much like a string. As it turns out,
check50
uses hashes to check the correctness ofrecover
for Problem Set 4. Rather than compare the 50 files outputted by your implementation ofrecover
against the original 50 JPEGs fromcard.raw
(as is possible, recall, with programs likediff
),check50
instead hashes each of your 50 files, the output of which is a 64digit hexadecimal string (i.e., 256 bits), comparing each such hash against 64digit hexadecimal strings hardcoded into the source code ofcheck50
's checks. If curious, you (and anyone on the internet!) can see them atop https://github.com/cs50/checks/blob/master/cs50/2017/fall/recover/check50/__init__.py, though no need to understand the Python code therein. Why might we be storing those 50 hashes in that repository instead of the original 50 JPEGs themselves? 
(4 points.) Recall that a trie iteratively hashes each of the letters in words in order to index into arrays. And even a hash table might hash all of the letters in words in order to index into an array. Why, though, is lookup of words said to be in O(1) for a trie but O(n) for a hash table?
Debrief

Which resources, if any, did you find helpful in answering this problem’s questions?

About how long did you spend on this problem’s questions?