資料結構與演算法

(5 points) Let $S$ be a collection of $n$ objects, each with a unique integer key $a_i \in \{0, 1, 2, \dots, n^2 - 1\}$. Consider hashing all the objects in $S$ into an array $A[0 \dots m-1]$ of size $m = \lceil n^{1.5} \rceil$ buckets. Each bucket stores a (singly) linked list of all objects hashed into the same bucket. The hashing algorithm works as follows. The algorithm first picks a hash function $h$ uniformly at random from a hash family $\mathcal{H}$. Then, for each object $i \in S$, the algorithm computes $h(a_i)$ and inserts the object into the bucket $A[h(a_i)]$. The number of collisions $\tau$ is defined to be the total number of (unordered) object pairs hashed into the same bucket. We focus on the choice of the hash family $\mathcal{H}$ and the worst-case expected number of collisions $\mathbb{E}[\tau]$. Note that the term worst-case refers to the choice of the input set $S$. Select all statement(s) that are correct for every sufficiently large $n$.