#### 选择题

##### 选择题 1

• hash函数应该“展开”大多数（即“非病理”）数据集（跨散列表的桶/槽）

• hash函数应该易于计算（恒定时间或接近它）

• hash函数应该易于存储（恒定空间或接近它）

• hash函数应该“展开”每个数据集（跨散列表的桶/槽）

##### 选择题 2

• $m/(2n)$
• $1/n$
• $n/m$
• $1/m$
• $n/(2m)$
• $m/n$

##### 选择题 3

• $1/m^2$
• $1/n^2$
• $1/(m-1)$
• $1/n$
• $1/m$

$x$的选择是任意的，$x,y$冲突当且仅当$y$落在$x$的桶中，所以概率为

##### 选择题 4

• $n/m^2$
• $n^2/m$
• $n/m$
• $n(n-1)/m$
• $n(n-1)/2m$

##### 选择题 5

• 小于$1\%$
• 小于$0.1\%$
• 小于$0.01\%$
• 小于$0.001\%$

#### 思考题

Recall that a set $H$ of hash functions (mapping the elements of a universe $U$ to the buckets $\{0,1,2,\ldots,n-1\}$) is universal if for every distinct $x,y∈U$, the probability $Prob[h(x) = h(y)]$ that $x$ and $y$ collide, assuming that the hash function $h$ is chosen uniformly at random from $H$, is at most $1/n$. In this problem you will prove that a collision probability of $1/n$ is essentially the best possible. Precisely, suppose that $H$ is a family of hash functions mapping $U$ to $\{0,1,2,\ldots,n-1\}$, as above. Show that there must be a pair $x,y∈U$ of distinct elements such that, if $h$ is chosen uniformly at random from $H$, then $\operatorname{Prob}[h(x)=h(y)] \geq \frac{1}{n}-\frac{1}{|U|}$.