如何计算哈希表中的平均键比较？
How to calculate average key comparisons in a hashtable?
假设我有一个散列 table，带有单独的链接。
它有密钥：1547、2333、6982、3356、1544
它的散列函数为 x mod 7.
散列table:
|1547|
| |
|2333|
|6982| -> |3356|
|1544|
假设我搜索的每个键都成功了，我是否可以像下面这样计算平均键比较？:
如果我要找一个没有被碰撞过的key(1547,2333,1544)，只需要比较一次。因此，基于散列 table，我有 3 个比较。
6982->3356需要比较2次
因此，平均而言，我有 (3+2)/5 = 1 次比较。
你的算术有点不对：你在数 3356 但忘记了 6982（这也是一个关键）。
正确的计算是
(4*1 + 1*2) / 5 = 1.2
假设我有一个散列 table，带有单独的链接。 它有密钥：1547、2333、6982、3356、1544 它的散列函数为 x mod 7.
散列table:
|1547|
| |
|2333|
|6982| -> |3356|
|1544|
假设我搜索的每个键都成功了，我是否可以像下面这样计算平均键比较？:
如果我要找一个没有被碰撞过的key(1547,2333,1544)，只需要比较一次。因此，基于散列 table，我有 3 个比较。
6982->3356需要比较2次
因此，平均而言，我有 (3+2)/5 = 1 次比较。
你的算术有点不对：你在数 3356 但忘记了 6982（这也是一个关键）。
正确的计算是
(4*1 + 1*2) / 5 = 1.2