Java 静态和动态数据结构之间的差异

Differences between Static & Dynamic data structures

提问by Carlos

What are the main differences, advantages and disadvantages between static and dynamic data structures?

静态和动态数据结构之间的主要区别、优缺点是什么？

Under which categories do the most common data structures fall?

最常见的数据结构属于哪些类别？

How could I know in which situation to use each?

我怎么知道在哪种情况下使用每个？

采纳答案by Jon

To start with an oversimplification:

从过度简化开始：

There are just a few basic kinds of data structures: arrays, lists and trees. Everything else can be composed by using different types of these two structures (e.g. a hash table can be implemented with an array for the hash values and one list for each hash value to handle collisions).

只有几种基本类型的数据结构：数组、列表和树。其他一切都可以通过使用这两种结构的不同类型来组合（例如，可以使用哈希值数组和每个哈希值的列表来实现哈希表以处理冲突）。

Of these structures, arrays are static (i.e., their memory footprint does not vary over time as operations are performed on them) and everything else is dynamic (i.e., in the general case the memory footprint changes).

在这些结构中，数组是静态的（即，它们的内存占用不会随着对其执行操作而随时间变化），而其他一切都是动态的（即，在一般情况下，内存占用会发生变化）。

The differences between the two kinds of structures can be derived from the above:

这两种结构的区别可以从上面推导出来：

• Static needs the maximum size to be known in advance, while dynamic can adapt on the fly
• Static does not reallocate memory no matter what, so you can have guaranteed memory requirements

• 静态需要提前知道最大尺寸，而动态可以动态适应
• 无论如何，静态都不会重新分配内存，因此您可以保证内存需求

There are also other differences, which however only come into play if your data might be sorted. I can't give an extensive list, as there are many dynamic data structures which exhibit different performance characteristics for different operations ("add", "remove", "find") and so they cannot be placed all under the same roof.

还有其他差异，但是只有在您的数据可能被排序时才会发挥作用。我不能给出一个详尽的列表，因为有许多动态数据结构对于不同的操作（“添加”、“删除”、“查找”）表现出不同的性能特征，因此它们不能全部放在同一个屋檐下。

A very visible difference is that sorted arrays require moving (possibly a lot of) stuff around in memory for any operation other than "find", while dynamic structures generally perform less work.

一个非常明显的区别是排序数组需要在内存中移动（可能很多）东西来进行除“查找”之外的任何操作，而动态结构通常执行的工作较少。

So, to recap:

所以，回顾一下：

1. If you need a guarantee on maximum memory usage, you have no option other than an array.
2. If you have a hard upper limit for your data size, consider using an array. Arrays can be a good fit for problems which mainly require add/remove operations (keep the array unsorted) and for those which mainly require find operations (keep the array sorted), but not for both at the same time.
3. If you do not have a hard upper limit, or if you require all of add/remove/find to be fast, use an appropriate kind of dynamic structure.

1. 如果您需要保证最大内存使用量，除了数组之外别无选择。
2. 如果您的数据大小有硬上限，请考虑使用数组。数组非常适合主要需要添加/删除操作（保持数组未排序）和主要需要查找操作（保持数组排序）的问题，但不能同时用于两者。
3. 如果您没有硬上限，或者如果您要求所有添加/删除/查找都很快，请使用适当类型的动态结构。

Edit:I did not mention graphs, another kind of dynamic data structure which arguably cannot be composed from simpler parts (by definition, a tree has exactly one link going "into" any node except the root, while graphs may have more than one). However, graphs cannot really be compared with other structures in a "what would be better to use" scenario, because you either need to use a graph or you do not (other structures may exhibit different performance, but in the end they all support the same set of operations).

编辑：我没有提到图，这是另一种动态数据结构，可以说它不能由更简单的部分组成（根据定义，树只有一个链接“进入”除根之外的任何节点，而图可能有多个） . 但是，在“什么更好用”的情况下，图不能真正与其他结构进行比较，因为您要么需要使用图，要么不需要（其他结构可能表现出不同的性能，但最终它们都支持相同的操作集）。

回答by Phani

Its always vice-versa, if you go with static then you lose memory whereas in case of dynamic, performance will be decreased. A best design would use the data structures efficiently, there is no one perfect answer.

反之亦然，如果使用静态，则会丢失内存，而在动态的情况下，性能会降低。最好的设计将有效地使用数据结构，没有一个完美的答案。

回答by Nidhi

Static data structures(SDS) are fixed sized (eg Arrays), the amount of memory once allocated to them cannot change on run time whereas Dynamic data structures(DDS)(eg Linked Lists) have flexible size , they can grow or shrink as needed to contain the data to be stored.

静态数据结构（SDS）是固定大小的（例如数组），一旦分配给它们的内存量不能在运行时改变，而动态数据结构（DDS）（例如链表）具有灵活的大小，它们可以根据需要增长或缩小包含要存储的数据。

SDS are linear data structures which allow fast access to elements stored in them but the insertion/deletion operations are expensive compared to DDS where the access to the elements is slower but insertion/deletion is faster.

SDS 是线性数据结构，它允许快速访问存储在其中的元素，但与 DDS 相比，插入/删除操作成本高昂，其中访问元素的速度较慢，但​​插入/删除的速度较快。

Most of the DS are Dynamic DS.

大多数DS都是Dynamic DS。

In case of SDS space is allocated before the actual data insertion so space may go wasted or may be insufficient some times so they should be used only in case the exact amount of data to be inserted is known in advance, if that is to be known at run time DDS should be used.

如果在实际数据插入之前分配了 SDS 空间，因此空间可能会浪费或有时可能不足，因此仅应在事先知道要插入的确切数据量的情况下使用它们，如果要知道的话在运行时应该使用 DDS。

回答by Menezes Sousa

Simple tips

简单提示

Dynamic data structures have the following characteristics:

动态数据结构具有以下特点：

• Ability to efficiently add, remove or modify elements
• Flexible size
• Effective use of resources – because resources are allocated at the runtime, as required.
• Slower access to elements (when compared with static data structures)

• 能够有效地添加、删除或修改元素
• 尺寸灵活
• 资源的有效利用——因为资源是在运行时根据需要分配的。
• 访问元素较慢（与静态数据结构相比）

Static data structures have the following characteristics:

静态数据结构具有以下特点：

• Add, remove or modify elements is not directly possible. If done, it is a resource consuming process.
• Fixed size.
• Resources allocated at creation of data structure, even if elements are not contain any value.
• Faster access to elements (when compared with dynamic data structures)

• 不能直接添加、删除或修改元素。如果完成，这是一个资源消耗过程。
• 固定尺寸。
• 在创建数据结构时分配的资源，即使元素不包含任何值。
• 更快地访问元素（与动态数据结构相比）

To sum up, it is not effective to use dynamic structures to store a set of data that is known, not to change. Using static data structure in such case will save system resources and also provide faster access to elements. If the size of the data is known to change on the other hand, then use dynamic structures.

综上所述，使用动态结构来存储一组已知的、不改变的数据是无效的。在这种情况下使用静态数据结构将节省系统资源并提供对元素的更快访问。另一方面，如果已知数据的大小会发生变化，则使用动态结构。