关于集合的有序性和无序性

Question

在《集合类的复杂度分析》中最后提到了 有序性和无序性，我有如下几个疑问：

问题一：集合有序性和无序性是指Set，还是泛指各类集合如 Set，ArrayList，LinkedList，HashMap等

问题二：什么是有序性无序性？是按照插入的顺序存储(遍历的顺序和插入的顺序一致)叫做有序， 如ArrayList。还是插入后内部排好序(升序降序)了叫做有序， 如TreeSet。

Answer 1

liuyubobobo 2018-06-10 06:16:21

通过这一章的学习，你应该已经了解了：集合是一种抽象数据结构，和底层实现无关。我们使用动态数组，链表，二分搜索树，等等底层实现，都可以实现“集合”这样的一种抽象数据结构。

同理，“有序集合”和“无序集合”，也是抽象的数据结构。所谓的“有序的集合”，是指在集合的基础上，还保持着所存储元素的顺序。在“有序集合”中，可以提供接口，供调用者完成下列操作：找到所存储元素的最大值(maximum)，最小值(minimum)，某个元素的下一个元素(succesor)，上一个元素(predecessor)，第k大元素(select)和某个元素是第几大元素(rank)。

通常，使用二分搜索树，有序数组或者有序链表，都可以作为“有序集合”的底层实现。在这一章，我们基于二分搜索树实现的集合，其实就是有序集合。只不过由于我们在讲二分搜索树的时候，没有为我们的二分搜索树实现上述接口（maximum，minimum，successor，predecessor，select和rank），所以我们使用二分搜索树实现的集合，表现和普通集合没有什么区别。有兴趣可以自己实现一下在二分搜索树中的相关方法，之后实现一个“真正意义上的有序集合”：）

同时，还非常建议尝试自己基于有序链表和有序数组实现一下有序集合这个抽象数据结构，也可以自己比较一下基于不同底层实现，有序集合的各项操作的性能。当然，如果没有时间进行具体实现，自己计算一下时间复杂度也是可以哒：）

对于无序集合，则是我们的数据在存储以后，不提供上述介绍的和元素之间的“顺序”相关的操作。我们在这一章基于链表实现的集合，就是一个典型的无序集合。更高效的无序集合，是使用哈希表。我们在这个课程的第十四章将会进行介绍：）

“有序映射”和“无序映射”完全同理，有兴趣也可以自己试试看：）

• Poplar_hills #1

  谢谢老师的详细讲解！