java - Guava ListMultimap中put()和get()操作的时间复杂度是多少？

Question

Guava ListMultimap 中put() 和get() 的时间复杂度 是多少？或 Guava ArrayListMultimap ？

我已经阅读了下面的 Guava 文档，但是没有提到这些操作的时间复杂度。

ListMultimap

ArrayListMultimap

时间复杂度和Hashmap一样吗(put()和get()的O(1))？

Answer 1

这在 guava 的通用 documentation for multimap 上有描述，虽然有点间接。 .具体来说，在“实现”部分中，它表示对于 ArrayListMultimap，键的行为类似于 HashMap，而值的行为类似于 ArrayList。

因此，get 和 put 都是 O(1)(关于伴随 HashMap 的声明的 usual caveats)。对于get，获取ArrayList只是一个O(1)的操作；对于 put，它是相同的 O(1) get，然后是另一个 O(1) put(摊销，因为 ArrayList 添加总是如此)。