【习题解答】 哈希表与查找

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 16.1 这是一个概率论的问题 + 总的样本空间是 + 符合要求的子样本空间是 + 故概率是两者的商

16.4

(1)

采用封闭寻址时，哈希表的存储消耗考虑： + 个表头，每个表头1个单位空间 + 个节点，每个节点2个单位空间 + 空间消耗为，即

同样的空间，即，用于开放寻址哈希表，节点还是个，每个节点需要1个单位空间，则位置个数为。故负载因子是，即

(2)

采用封闭寻址时，哈希表的存储消耗考虑： + 个表头，每个表头1个单位空间 + 个节点，每个节点5个单位空间 + 空间消耗为，即

同样的空间，即，用于开放寻址哈希表，节点还是个，每个节点需要4个单位空间，则位置个数为。故负载因子是，即