java - 列表与 map : Which takes less space and more efficient?

Question

我有两个类Foo和 Bar .

class Foo
{
    Set<Integer> bars; // Foo objects have collection of bars.
    Set<Integer> adjacents; // Adjacency list of Foos.
}

class Bar
{
    int foo; // ID of foo of which this object belongs to
    Ipsum ipsum; // This an arbitrary class. But it must be present
    Map<Integer, Float> adjacents; // Adjacency list of Bars
}

Bar的数量s 是预定义的(最多 1000 个)。因此，我可以使用一个数组。
但是Foo的数量s 未定义(最多 #ofBars/4 )。

当您考虑添加、删除和get() ，我需要速度更快且占用空间更少的那个(因为我要使用序列化)。

这是我的选择(据我所知)

选项 1:不要为 Foo 定义类.相反，请使用 List<Set<Integer>> foo;以及 Map> fooAdjacencies 的另一张 map ；
选项 2:使用Map<Integer, Set<Integer> foo如果我想获得 i 的条形图，我简单写foo.get(i) .
选项 3:不要定义类。相反，使用选项 2 和 Bar类(class):

Map<Integer, Ipsum> bar;
Map<Integer, Map<Integer, Floar>> barAdjacencies;

在空间和时间效率方面我应该选择哪个选项？

Answer 1

这听起来对你很有帮助(特别是数据结构部分):http://bigocheatsheet.com/

你说

I need my structure to be efficient while adding, removing and finding elements. No other behavior.

问题是 Lists和 Maps通常用于完全不同的情况。他们的名字很好地描述了他们的用例——你使用 List如果您需要列出某些内容(可能按某些顺序)，而 Map如果您需要将输入映射到输出，将使用它。您可以使用 Map作为 List通过映射 Integers到你的元素，但这有点过于复杂了。然而，即使在 List 内和 Map您可以有不同的实现，它们在渐近性能方面大相径庭。

除了少数异常(exception)，数据结构将采用 O(n)空间，这是有道理的。如果没记错的话，除了 ArrayList 之外的任何内容(或仅由原始数组支持的其他集合)将具有相当数量的空间开销，因为它们使用其他对象(例如 Nodes 的 LinkedLists 和 Entry 的 Maps 对象)来组织底层结构。我不会太担心这种开销，除非空间真的很宝贵。

为了获得最佳性能的添加、删除和搜索，您需要查看数据结构是如何实现的。

LinkedList风格的实现将使您获得O(1)添加和删​​除(也有一个很好的常数因子!)，但是会有一个相当昂贵的 get()与 O(n)时间，因为每次你想得到一些东西时都必须遍历列表。 Java的LinkedList但是，实现在 O(n) 中删除时间;而实际的删除行为是O(1) ，仅当您引用了要删除的实际节点时。因为你不这样做，Java 的 LinkedList 中的删除是 O(n) -- O(n)用于搜索要删除的节点，O(1)用于移除。

由普通数组支持的数据结构将具有 O(1) get()因为它是一个数组，但需要 O(n)添加和删​​除，因为除了最后一个元素之外的任何添加/删除都需要打乱所有其他元素(至少在 Java 的实现中)。在 O(n) 中使用对象而不是索引来搜索内容。时间，因为您必须遍历数组才能找到对象。

以下两个结构通常是Maps ，因此通常需要您实现 equals() (和 hashCode() 为 HashMaps ):

由树支持的数据结构(例如 TreeMap )将摊销(我认为)O(lg n)添加/删除，作为一个好的实现应该是自平衡的，使最坏情况下的添加/删除最多只需要经过树的高度。 get()操作是O(lg n) .使用树要求您的元素以某种方式可排序/可比较，这可能是一种奖励或阻碍，具体取决于您的使用情况。

基于哈希的数据结构已摊销(平均)O(1)一切，尽管由于散列的开销(如果散列传播很差，则遵循任何链)，常数因子略高。 HashMaps如果你写得不好 hashCode()函数，所以你要小心，尽管 Java 的 HashMap 的实现者确实在幕后做了一些魔术，试图至少部分抵消不良 hashCode() 的影响实现。

希望破败有所帮助。如果你弄清楚你的程序是如何结构的，我可能会给出一个建议。在那之前，我能做的最好的就是向您展示选项并让您选择。