我的书签
添加书签
移除书签5.1 集合类是什么
5.1.2 集合类是一种数据结构
在讲 Kotlin 的集合类之前，为了更加深刻理解为什么要有集合类，以及集合类到底是怎么一回事，让我们先来简单回顾一下编程的本质：
数据结构 + 算法 （信息的逻辑结构及其基本操作）
我们使用计算机编程来解决一个具体问题时，大致需要经过下列几个步骤：
首先要从具体问题中抽象出一个适当的数学模型；
然后设计一个解此数学模型的算法（Algorithm）；
最后编出程序、进行测试、修改直至得到最终解答。
这里面的寻求数学模型的过程，实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系的过程。建立好的模型，我们使用数学语言来表达。
这里的模型对应的就是数据结构。我们用计算机编程来解决问题的关键就是，设计出合适的数据结构（例如，用线性表、树、图等）和性能良好的算法。
算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。通常情况下，设计良好的数据结构可以大大简化算法的实现复杂度，同时可以提升存储效率。数据结构往往同高效的检索算法和索引技术相关。
我们可以把数据结构理解为是ADT的实现。数据结构就是现实问题模型的表达。
数据结构主要解决以下三个问题：
- 数据元素之间的逻辑关系。
这些逻辑关系有：集合、线性结构、树形结构、图形结构等。
- 数据的物理结构。
数据的逻辑结构在计算机存储空间的存放形式。数据的物理结构是数据结构在计算机中的映射。其具体实现的方法有： 顺序（Sequence）、链接（Link）、索引（Index）、散列（Hash）等形式。
其中，顺序存储结构和链式存储结构是我们常用的两种存储结构。
顺序存储是使用元素在存储器中的相对位置来表示数据元素之间的逻辑关系；
链式存储使用指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。
我们现在很少用抽象数据类型ADT（Abstract Data Type）这个概念，其实这个概念是OO范式的前身，也是类的前身。ADT加上继承、重载和多态性就是现代OOP编程范式中的类的概念了。我们简称类为广义ADT的概念。
如果我们更加广义的来理解这里的ADT的思想，其实各种编程语言的SDK API、所有的服务（IaaS，PaaS和SaaS等）都是一种更加广义的ADT。
使用ADT可以让我们更简单地描述现实世界。例如：用线性表描述学生成绩表，用树或图描述遗传关系等。
我们知道类的本质就是，对象及其关系的抽象（abstraction）。一个类通常有属性（数据结构）和行为（算法）。使用OO范式编程的大致过程为：
划分对象 → 抽象类 → 将类组织成为层次化结构(继承和合成) → 用类与实例进行设计和实现
等几个阶段。
数据抽象本质上讲就是我们解决现实问题的过程中，进行建立领域模型（Domain Model）的过程。
比如说，在前一章节中，我们介绍的程序设计语言的类型系统，本质上就是一种数据抽象。由于计算机的结构和存储的限制（无法像人类大脑神经系统一样去认知识别，并解决现实问题），人类大脑在解决实际问题过程中，经常要计算整数、小数, 要处理英文字符、中文字符， 要持有对象（被操作的数据），要对这些对象进行诸如：查找、排序、修改、传递等操作。把这些问题解决中最常用的数据结构以及其操作算法抽象成对应的类（例如：String、Array、List、Set、Map等），这样我们就可以极大的复用这些功能。而不需要我们自己来实现诸如：字符串、数组、列表、集合、映射等这些的数据结构。通常这些最通用的数据结构，都是现在编程语言中内置的了。
5.1.3 连续存储和离散存储
内存中的存储形式可以分为连续存储和离散存储两种。因此，数据的物理存储结构就有连续存储和离散存储两种，它们对应了我们通常所说的数组和链表。
由于数组是连续存储的，在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据，但是如果要在数据组中任意位置上插入一个元素，就需要先把后面的元素集体向后移一位为其空出存储空间。与之相反，链表是离散存储的，所以在插入一个数据时只要申请一片新空间，然后将其中的连接关系做一个修改就可以，但是显然在链表上查找一个数据时就要逐个遍历了。
考虑以上的总结可见，数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组；当对数据集中的数据进行添加或删除比较多时最好选择链表。
