索引数据结构和顺序数据结构之间到底有什么区别?例如,HashSet 是索引数据结构,而 TreeSet 是顺序数据结构。
在 java 中,这些术语没有固定的含义。这些含义将从日常英语用法以及对您列出的类型的检查中获得。
“索引”意味着有一个与数据结构相关的索引,可以用来引用数据结构的元素,最基本的例子是一个数组,它由整数偏移量索引,或者Map
,它由键值索引。请注意,这省略了数据结构具有自然顺序的感觉。我们可以看到数组具有自然顺序,但Map
没有。
“顺序”将意味着数据结构具有可用于对数据结构的元素的操作进行排序的顺序,在某种意义上这应该是自然的顺序,但是该术语也可以意味着存在施加在数据结构上的顺序,其使得能够进行迭代操作。
例如,顺序数据结构可以支持findFirst
操作,而不允许迭代作为外部操作。
对于两个引用的类型,HashSet
和TreeMap
,因为它们是实现类型,所以这些术语可以用来描述数据结构的一般属性,也可以用来描述实现的属性。
请注意,“索引”并不意味着“顺序”,除非索引值本身是顺序的。
使用索引时,您可以将数据直接读取或写入数据结构中的任何位置。如果访问是顺序的,则必须遍历所有元素,直到到达所需的元素(例如迭代next
方法)。
这也意味着访问时间对于索引结构是恒定的,无论其大小如何,同时它随着顺序结构的大小而增加。
这适用于假设访问索引的内部实现(实际上只是可以以多种方式实现的访问操作)基于某种映射,并且顺序结构使用某种链表。
对于一个关于如何根据实现而有所不同的示例,Python 中的列表在内部实现直接访问,出于明显的性能原因,除了由用户使用索引而不是下一个方法访问之外。
让我们在更广泛的数据结构领域中回答这个问题,而不是专注于 Java 或任何其他实现。
索引数据结构
基于更一般的-Random/Direct Access数据结构概念。
使用这些数据结构的主要好处是,它们具有O(1)时间复杂度,用于读取和写入操作。
例如,当您定义数组时,相同大小的的连续链,在物理RAM中分配很少的内存片(块),并且这些片中的每一个都具有唯一但连续链接的内存地址。这意味着,例如,如果将array[0]
存储在0100X001
的插槽中,则array[1]
将在
顺序数据结构
另一方面,are not clearly defined在计算机科学领域,根据实现的不同,它们具有不同的读写操作时间复杂度,但大多数情况下-它永远不会O(1)。
在大多数情况下,顺序数据结构的实现方式如下:
除第一个元素外,每个元素都有对其直接前身的引用;
除最后一个元素外,每个元素都有对其直接后继元素的引用。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处
评论列表(25条)