algorithm - 计算哈希表中键比较的次数

Question

我有一个哈希表，如下所示:

0
1 -> 1101 -> 1222 -> 1343  \\ 3 key comparison 
2
3 -> 2973 -> 2588          \\ 2 key comparison
4

有多少关键比较？给定的答案是 1 + 2 + 1 = 4 但它不应该是 3 + 2 = 5 吗？

Answer 1

给出的答案是正确的。一种可能的顺序:

• 首先，您有一个空列表 -> 然后添加 1101 -> 不需要比较。

• 添加1222 -> 进入1列表，与1101进行比较 -> 添加到列表末尾 -> 1比较。

• 添加1343 -> 进入1列表，与1101、1222进行比较 -> 添加到列表末尾 -> 2比较。

  <

• 添加 2973 -> 没有比较，

• 添加2588 -> 进入3列表，与2973进行比较 -> 1比较。

所以，总共比较的次数是0 + 1 + 2 + 0 + 1

不知道从哪里得到 3 + 2 = 5？元素总数？