4

我试图弄清楚对 Java 基本集合的操作有哪些复杂性（使用 big-o 符号）。与C++ 语言的这个问题类似。

这是我所拥有的，使用常识：

列表

数组列表

  • 加(E e) O(1)
  • 添加（整数索引，E e） O(n)
  • 设置（int索引，E元素 O(1)
  • 获取（整数索引）O(1)
  • 删除（E e）删除（整数索引） O(n)
  • 包含(E e)O(n)
  • 列表连接（addAll）O(n)

链表

  • 加(E e) O(1)
  • 添加（整数索引，E e） O(n)
  • 设置（int索引，E元素 O(n)
  • 获取（整数索引）O(n)
  • 删除（E e）删除（整数索引） O(n)
  • 包含(E e)O(n)
  • 列表连接（addAll）O(1)

套

HashSet 和 LinkedHashSet

  • 加(E e) O(1)
  • 删除（E e）O(1)
  • 包含(E e)O(1)
  • 使用迭代器查找/获取元素O(n)

树集

  • 加(E e) O(log n)
  • 删除（E e）O(log n)
  • 包含(E e)O(log n)
  • 全部添加O(n log n)
  • O(n)使用迭代器或可能O(log n)在实现二分查找时查找元素

地图

HashMap 和 LinkedHashMap

  • put(K键，V值) O(1)
  • 得到（K键） O(1)
  • 删除（E e）O(1)
  • containsKey(对象键) O(1)
  • 包含值（对象值）O(n)
  • 全部放O(n)
  • 使用迭代器查找/获取元素，O(n)或者可能O(log n)与TreeSet

树状图

  • put(K键，V值) O(log n)
  • 得到（K键） O(log n)
  • 删除（E e）O(log n)
  • containsKey(对象键) O(log n)
  • 包含值（对象值）O(n)
  • 全部放O(n log n)
  • 使用迭代器查找/获取元素O(n)

注意：基于散列的集合假定设计良好的散列函数在，O(1)否则它在O(n)

问题： 这是正确的吗？

4

1 回答 1

3

你最好的知识来源是文档。这是我可以通过一两次快速搜索找到的内容。

列表

数组列表

、size、isEmpty、get、set和操作在恒定时间内运行iterator。listIterator该add操作在摊销常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都以线性时间运行（粗略地说）。

链表

所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。

根据我对双向链表的记忆，我会说您的“常识​​假设”是正确的。

套

哈希集

此类为基本操作（添加、删除、包含和大小）提供恒定的时间性能，假设哈希函数将元素正确地分散在桶中。迭代这个集合需要的时间与 HashSet 实例的大小（元素的数量）加上支持 HashMap 实例的“容量”（桶的数量）的总和成正比。

链接哈希集

与 HashSet 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确地分散元素。由于维护链表的额外费用，性能可能略低于 HashSet，但有一个例外：迭代 LinkedHashSet 所需的时间与集合的大小成正比，而不管其容量如何。HashSet 的迭代可能会更昂贵，需要的时间与其容量成正比。

树集

此实现为基本操作（添加、删除和包含）提供有保证的 log(n) 时间成本。

地图

哈希映射

此实现为基本操作（get 和 put）提供恒定时间性能，假设哈希函数将元素正确地分散在桶中。集合视图的迭代需要的时间与 HashMap 实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。

LinkedHashMap

与 HashMap 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确地分散元素。性能可能略低于 HashMap，...

树状图

此实现为 、 和 操作提供有保证的 log(n containsKey)get时间成本put。remove

如果某些方法未提及，请尝试查找该特定方法。如果文档中的任何地方都没有提到运行时间，则它可能取决于实现。

于 2013-08-20T00:16:32.727 回答