hash quiz



Which of the following is not a property of Java's hashCode() for the String data type?

can return a negative integer
can take time proportional to the length of the string to compute
a string and its reverse will have the same hashCode()
two strings with different hashCode() values are different strings

What is the average running time of a random search miss in a separate chaining hash table? Assume that your hash function satisfies the uniform hashing assumption and that there are M=N/8 chains, where N is the number of items.

constant
logarithmic
linear
linearithmic

What is the average running time of delete in a linear-probing hash table? Assume that your hash function satisfies the uniform hashing assumption and that the hash table is at most 50% full.

constant
logarithmic
linear
linearithmic

What is the main reason to use a hash table instead of a red-black BST?

supports more operations efficiently
better worst-case performance guarantee
better performance in practice on typical inputs
implementation included in Java libraries