Java数据结构的空间复杂度

-1

我一直在寻找很多包含Java数据结构空间复杂度信息的网站。我正在寻找HashMap,ArrayList,Stack和LinkedList的空间复杂性。我发现一个站点接近并且只有Stack和LinkedList的信息是：http://bigocheatsheet.com/，但它只有最坏的情况。任何人都知道任何其他有HashMap或ArrayList空间复杂性信息的来源，最好是平均情况和最坏情况？Java数据结构的空间复杂度

来源

2015-05-03 Arvind Talmask

我不明白你的问题。空间或时间复杂性被附加到像搜索元素这样的操作上。没有Hashmap的空间复杂性。 – Lokesh

http://java-performance.info/memory-consumption-of-java-data-types-1/可能值得一看 – mikyra

正确的错字标题。将网址转换为可点击的链接。使用实际的类名称来引用数据结构。一些小的语法修复。 –

在正常情况下，它们都是空间使用的O(N)。（等等都是标准的收集数据的结构，我想......）

当然，这并不能告诉你这些数据结构将有多少空间在实践中使用一些重要的事实。例如：

的ArrayList或HashMap航天使用率不成正比的列表大小。它们的一些或全部空间利用率的策略都是“满员时的两倍”策略。
在最好的情况下，ArrayList使用每元件更少的空间比一个LinkedList和LinkedList使用每元件比HashMap更少的空间。

依此类推。

也很困难，因为有一定的使用模式，可以导致空ArrayList或HashMap占用大量的空间来量化最坏的情况下...。对于这些数据结构，空间使用率可以正比于最大N值（迄今为止）而不是当前N值。

当删除元素时，ArrayList不会“返回”空间。
随着HashMap链占用的空间可以增长和缩小，但散列数组只增长。

来源

2015-05-03 03:48:30

@greybeard - 它将有总共有N个节点的树。所有树节点都直接指向树的唯一元素......内部和叶节点之间没有区别。注意：我们没有考虑用于存储元素（或键）的空间，因为对于所有基于'Collection'的数据结构来说，这是相同的。 –

Ooops ...没有TreeMap是空间中的O（N）。纠正这一点。谢谢。 –

我觉得在移除点之后关于'HashMap'的警告字。用'ArrayList'，有'trimToSize（）'。 – greybeard

如果您检查这些类的代码，你可以看到，他们在内部表示为数组。因此，操作的复杂性应该与阵列上的相似。

来源

2015-05-03 03:48:12 kaykay

Java数据结构的空间复杂度

回答

相关问题