$($a$)[5$ pts$]$ How do we go about picking a good hash function and hash structure? Provide some general guidelines about what a hash designer needs to think about.

$($b$)15$ pts$]$ What is the worst case runtime of insertion into a hash table using chaining $($linked list$)?$ Please explain.

$($c$)(5$ pts$]$ What is the worst case runtime of $($successful$)$ insertion into a hash table using linear probing $($a form of open addressing$)?$ Please explain

$($d$)(5$ pts$]$ There are two hash functions that take in strings as input shown below. Each returns an integer in between $0$ and $1,000,002.($Note: $1,000,003$ is a prime number.$)$ Which of these two is a better hash function?

Explain the weakness in the other function.

int f$1($char$*$ str$)\{$

int i $=0,$ res $=0$;

while $($str $[$i$]!=$

$\backslash$O $)$ s

res $=(256*$ res $+($int$)($str $[$i$]))\%1000003$;

i$+$;

$\}$

return res:

$\}$

int f$2($char$*$ str$)\{$

int i $=0,$ res $=0$;

while $($str $[$i$]!=$

$)$ S

res $=($res $+($int$)($str $($i$]))\%1000003$;

$4+$:

$\}$

return res; $\}$