索引数据结构和顺序数据结构之间的差异

Question

索引数据结构和顺序数据结构之间的区别到底是什么？例如，HashSet是索引数据结构，而TreeSet是顺序数据结构。

Answer 1

使用索引时，您可以直接在数据结构中的任何位置读取或写入数据。如果访问是按顺序进行的，则必须遍历所有元素，直到到达所需的元素(就像迭代next方法一样)。

这也意味着，无论索引结构的大小如何，访问时间都是恒定的，而对于顺序结构，访问时间会随着大小而增加。

假设索引访问的内部实现(实际上只是一个可以以多种方式实现的访问操作)基于某种映射，并且顺序结构使用某种链表，则这一点也适用。这应该与所制定的问题的精神相一致。

例如，Python中的列表在内部实现了直接访问，原因很明显，除了由用户使用索引而不是next方法访问之外，它还可以根据实现的不同而有所不同。

Answer 2

在java中，这些术语没有固定的含义。这些含义将从日常英语用法中获得，并通过对您列出的类型的检查来获得。

“索引”意味着有一个与数据结构相关联的索引，可以用来引用数据结构的元素，最基本的例子是数组，它由整数偏移量或Map索引，它由键值索引。请注意，这省略了数据结构具有自然顺序的意义。我们可以看到数组有一个自然的顺序，但是Map没有。

“顺序”将意味着数据结构具有可用于对数据结构元素上的操作进行排序的顺序。有一种感觉，这应该是一种自然的顺序，但这个术语也可能意味着在数据结构上强加了一种顺序，这使得迭代操作成为可能。

在这两种情况下，含义都不应包括对特定操作的引用。数据结构可以支持读、写或迭代，但不一定支持任何或所有这些。例如，顺序数据结构可以支持findFirst操作，而不允许将迭代作为外部操作。

对于两个引用的类型HashSet和TreeMap，因为它们是实现类型，所以这两个术语可以用来描述数据结构的一般属性，也可以用来描述实现的属性。我不确定这是不是很有用，因为实现可以改变。

请注意，“索引”并不意味着“顺序”，除非索引值本身是顺序的。

Answer 3

让我们在更广泛的数据结构领域来回答这个问题，而不是专注于Java或任何其他实现。

索引数据结构

基于更一般的Random/Direct Access数据结构概念。

使用这些数据结构的主要好处是，对于读写操作，它们的时间复杂度都是O(1)。

例如，当您定义数组时，在物理RAM中分配大小相同的小内存片(块)的连续链，并且这些片中的每个片都具有唯一但连续链接的内存地址。这意味着，例如，如果array[0]存储在0100X001中，如果该槽占用1位，则array[1]将被分配到0100X010 (如果更多，则相应地，您必须将该位数添加到每个槽中)；

顺序数据结构

另一方面，在计算机科学领域的are not clearly defined，根据实现的不同，读写操作具有不同的时间复杂度，但大多数情况下-它永远不是O(1)。

除了第一个元素之外，每个元素都有一个对其直接predecessor;

• Each元素的引用，除了最后一个元素之外，每个元素都有一个对其直接后继元素的引用。