时间戳

首页 > 解决方案 > 一个关于HashMap的时间复杂度的问题

hash - 一个关于HashMap的时间复杂度的问题

问题描述

这不是代码问题，我只是想了解哈希图和时间复杂度的概念。

好吧，我想我知道 hashMaps/sets 等是如何工作的，我想我理解为什么 HashMaps.get 有一个恒定的时间，但是当我们有一个非常大的 hashMap 时，存储值的索引应该重叠。当 2 个哈希码解析为相同的索引时，它们会存储在该索引处的 LinkList 中，对吗？

难道不是所有元素都作为链接列表存储在一个索引中。现在不应该在 O(n) 的最坏情况下运行 HashMap.get。

标签： hashlinked-listhashmaptime-complexity

解决方案

是的，最坏情况的时间复杂度HashMap是 O(n)，其中n是存储在一个桶中的元素数量。最坏的情况是nHashMap 的所有元素都存储在一个桶中。

但是，如果对每个存储桶实施二进制搜索，则可以改进这一点。在这种情况下，最坏情况下的时间复杂度将O(log(n))是binary search tree用于存储元素而不是doubly linked list.

推荐阅读