分享
为什么问答平台  ›  专栏  ›  技术社区  ›  ilkercan Kaya

为什么哈希表插入时间复杂度最坏的情况不是n log n - Why is Hash Table insertion time complexity worst case is not N log N

  •  1
  • ilkercan Kaya  · 技术社区  · 1 周前

    这里是在AVL中添加n个元素的证明。 Running time of adding N elements into an empty AVL tree

    1 回复  |  直到 1 周前
        1
  •  1
  •   Willem Van Onsem    1 周前

    :这取决于桶是如何实现的。使用链接列表,可以在 在某些条件下。对于将AVL树作为bucket的实现,这确实会导致 日志

    通常桶是 使用AVL树实现,或者通常使用树,但使用链接列表。如果有对 last O(1) O(1)

    一些哈希表使用

    Wikipedia article on Hash table s 讨论如何实现存储桶。