Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.
We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.
All of the listed hash functions are valid, except for the solution using Math.random().
Although simply returning the length of the string or some constant value is a bad hashing algorithm, it is still valid, as a key will always hash to the same integer value. However, using a random number as part of the hash code would not work, since the same key would hash to a different index each time hashCode() is called.
The first hash function is quick - however, it will still result in collisions for strings whose characters sum to the same value. The second function achieves much better spread since it uses Prime numbers, but it would be much slower since it does much more calculation (Note also that it will result in huge integers).
The tree shown has a height of 3.
The tree shown has a height of 0.
The formula for max # of nodes in a tree of height h can be described as:
$$ ⁍ $$
So, $2^{(5+1)} - 1 = 63$.
For the minimum number of nodes in the tree, the equation is $h+1$. So, for a tree of height 5, there could be 6 nodes in the tree.
The worst-case situation for a BST is a degenerate tree, where the tree is essentially a linked list. The runtime for a containsKey() operation would be $\Theta(n)$ since all nodes would need to be traversed.