哈希表 复杂度问题

Question

为什么在改进后的 哈嘻表平均复杂度是 lower_bound ~ upper_bound

比如我们的hashtable 的大小是 4
然后我们的 chaining size upper_bound = 5
那么当 size = 20 的时候 我们就要 resize
好比 size 4 到 8
那么 这个过程resize 方法 需要遍历旧的数组以及这个index的TreeMap 的所有Key(s)
这个大O 是 n^2 (倘若都hash 到了一个 TreeMap并且遍历所有的key)
… 那么…???
所以整个过程平均复杂度怎么就变成了 lower_bound ~ upper_bound?
这个平均下来是怎样转换的呢?

谢谢

Answer 1

liuyubobobo 2019-01-06 04:28:09

resize不是O(n^2)的，是O(n)的。其中n是所有的元素个数。因为resize的过程遍历了所有的元素。即使你举的特殊情况，所有的元素都在一个hash上，那么遍历这一个hash上的所有元素用O(n)，便利其他hash位置，由于没有元素，所以只是扫了一遍其他hash，也是O(n)，整体还是O(n)的。

之后的计算和我们的动态数组的均摊复杂度分析是一样的。平均再次resize，要再来n个元素。这次resize的n次操作，均摊到后续的每一次操作中，相当于每一操作添加了O(1)的复杂度：）

• 提问者 我爱吃板面 #1

  从宏观上看确实 遍历了n个元素
  但是 outer loop 无论是否是空hash index 都要遍历所index
  [TreeMap] size 0
  [TreeMap] size 0
  [TreeMap] size 0
  [TreeMap] size 10
  
  确实我们遍历了10个元素但是同时我们的外层循环也有一个 M 个的遍历
  所有 我觉得是 O(M*size) 就成了 n^2 但是退一步看确实遍历了所有的元素应该就是n.....
  
  这个 resize的简单推论没有懂
  不知道 每次resize 都要遍历所有元素 并且放入到新的 hashtable里
  这时 复杂度就是n 然后这个resize 会被调用会在n个 add operations 之后 所有这个 n 除 这个resize 复杂度的 n 就是 复杂度为1 了?
  
  谢谢

• liuyubobobo 回复 提问者 我爱吃板面 #2

  不是n^2，你可以理解成，我们有n个hash，但无论如何都不可能每个hash都有n个元素，而是n个元素分布在这n个hash里。所以，访问每一个hash需要O(n)，但是每一个hash都乘以n高估了时间，每个hash里有xi个元素，所有的xi加在一起是n，所以遍历每个hash里的元素，总共也用了O(n)的时间。

• liuyubobobo 回复 提问者 我爱吃板面 #3

  至于你说的resize均摊的过程，再理解一下2-9小节，使用resize以后，为什么均摊分析的结果，动态数组的所有操作的复杂度是O(1)的？道理是完全一样的：）