谈一谈Java容器类

Author Avatar
Ethan Hua 6月 15, 2017

执行程序的过程就是操作数据的过程，即通常所说的 程序 = 数据 + 算法，在看 Java 容器类之前，我们先简单复习下数据结构的知识。

数据结构

数据结构包含数据和结构，就是将数据按照一定的结构组合起来，不同的组合方式会有不同的效率，不同的使用场景。

分类

计算机中的数据结构是对现实场景中数据关系的映射抽象，故按照关系可以划分为三类：

  • 一对一 线性表
  • 一对多 树
  • 多对多 图

按照计算机物理内存中的分配空间位置又可以分为：

  • 顺序
  • 链接
  • 索引
  • 散列

常用数据结构：

数组

数组是一段连续的内存存储空间，由于地址连续，所以查找效率好，但新增、插入、删除等操作涉及到元素挪动效率较低。

链表

链表采用额外的内存空间来保存元素之间的位置地址，所以新增、插入、删除等操作较数组好，但查找效率较低，需遍历集合、内存占用也较数组大。

栈

栈是一种先进后出的数据结构，具体实现可以采用数组也可以采用链表，有一个指向栈顶元素的指针，元素进出栈时，指针重新指向栈顶元素。

队列

队列是一种先进先出的数据结构，具体实现也可以采用数组或者链表，有一个指向队列头和队列尾的指针，进出对列时，对应的指针指向更新。

树

树通俗来说就是一种层级结构，一个根节点对应多个子节点，同时自身可能还有一个父根节点，类似于公司的组织结构，图书的目录、和Android中的View的层级结构。

堆

通常我们讲的堆是二叉堆，是一种二叉树结构。

散列表

根据名称可以得知，内存存储位置是散列不连续的，它有一个映射函数，对于关键值key，有一个位置存储着对应的值。

图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

Java中的集合类

Java 容器类的设计封装是为了我们开发者更高效的开发，其中不同的类对应有不同的使用场景，是否正确的选用容器类对程序的运行性能和稳定性有至关的影响，Java 容器类设计为 Collection 和 Map 两种接口，对应存储集合和键值对。

Collection

Set

无重复数据，无索引方法，内部采用 Map 存储单一实例 Object 对象，数据作为其 Key 值存储所以保证了数据的唯一性

常见实现类有：

  • HashSet
    内部采用 HashMap 来存储，支持快速查找，但不支持有序性操作，例如根据一个范围查找元素的操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
  • TreeSet
    内部采用 HashSet 来存储，基于红黑树实现，支持有序性操作，但是查找效率不如 HashSet，HashSet 查找时间复杂度为 O(1)，TreeSet 则为 O(logn)；
  • LinkedHashSet
    内部采用 LinkedHashMap 来存储，内部使用链表维护元素的插入顺序。

List

有重复数据，有索引方法

常见实现类有：

  • ArrayList
    基于动态数组实现，会在容量不足时进行扩容，扩容因子是 1.5。
  • Vector
    ArrayList 的同步实现，操作增加了 synchronized 所以是线程安全的，它有一个子类 Stack ，是栈在 Java 中的实现类。
  • LinkedList
    基于双向循环链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双端队列。

Queue

队列在 Java 中的接口实现，定义了进队，出队操作

常见实现类有：

  • LinkedList
    双向队列
  • PriorityQueue
    优先队列，每次出列的是优先级最高的元素，而不是先进先出，优先级根据构造时候的比较器来确定，如果没有比较器，则按照自然规则排序，采用二叉堆实现，适用于任务调度场景。
  • BlockingQueue
    阻塞队列接口，采用分段锁实现线程安全，常用于实现生产者-消费者模式。
    • LinkedBlockingQueue 采用链表存储数据
    • ArrayBlockingQueue 采用数组存储数据（构造时确认长度，固定不能扩容）
    • PriorityBlockingQueue 优先级队列的阻塞同步实现
  • ConcurrentLinkedQueue
    采用 CAS 实现线程安全

开发应用相关

迭代器模式应用

Collection 实现了 Iterable 接口，使得访问其所有的实现类可以不依赖于具体实现，iterator() 方法能够产生一个 Iterator 对象，通过这个对象就可以迭代遍历 Collection 中的元素。

从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

Arrays.asList() 的坑

java.util.Arrays#asList() 可以把数组类型转换为 List 类型。

  1. 由于参数是可变长参数，所以不能以基本数据类型数组为参数，它会被处理成一个数组对象的参数。
  2. asList() 内部构建的是一个内部 ArrayList 对象，而这个内部类没有实现增，删、插入方法，是一个不可变数组列表。

Map

键值对的操作

常见实现类有：

  • HashMap
    采用拉链数组结构，内部维护一个 Node 类型的数组，数组中每个位置存储的是一个链表( JDK1.8 开始，如果链表长度大于8时，会将链表转换为红黑树)，查找时会根据 key 的 hash 值定位到数组位置，然后遍历列表找到对应的 Node 值（Node中维护的是键值对和下一个Node的引用）
  • HashTable
    HashMap 的线程安全版，它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
  • LinkedHashMap
    相对于 HashMap 多出一个双向链表维护里面 Node 的顺序，由于可以根据访问时间排序，所以适用于 Lru 缓存实现。
  • TreeMap
    基于红黑树实现，适用于 Key 值按照自然语义排序或者自定义顺序排序的场景

容器选型

选型的依据有数据的类型、数据是否唯一，是否排序，排序规则，增、插、删、改、查何种操作频繁度高、是否并发场景，要结合具体的场景来分析，对症下药，才能药到病除，选型思路大概如下：

典型分析

二叉堆

二叉堆是完全二叉树或者是近似完全二叉树，二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。

与一般的二叉树实现用链表不同二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在 2n 和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点，子节点和根节点通过这种指定的规则来保持联系（不同于链表中的上下指针），如果是最大堆则数组首位为这种序关系中的最大值，如果是最小堆则数组末尾为这种序关系中的最大值，所以取出最大或最最小值的性能表现是O(1)，这种数据结构常用来实现优先级队列，如 Java 中的 PriorityQueue。

具体实现细节可以看这边文章： 二叉堆

红黑树

平衡二叉查找树的一种类型，了解平衡二叉查找树之前需要了解二叉查找树，简单来说二叉查找树是一种按照 左子节点 < 根节点 < 右子节点 的规则排序的二叉树，其查找、插入、删除的算法时间复杂度取决于树的高度，理想情况下为 O(logN),最坏情况(即所有根节点只有左节点或者右节点，退化成了一条链表)下为 O(N)，一个二叉树在插入或者删除的时候如果不做任何平衡处理，很容易慢慢腐化，导致算法时间复杂度增加，为了解决这个问题，所以需要在插入和删除时作相应的平衡处理操作，衍生出了两个新的数据结构： AVL 树 和 红黑树。

  • AVL树
    是一种高度平衡二叉树，其任何节点的两个子树的高度最大差别为1，维护这个严格要求的成本较高，适用于查找频繁，插入删除操作少的场景。
  • 红黑树
    相对于AVL树对平衡做了妥协，实现的是局部的平衡，所以插入、删除等效率较AVL树较高，是一个查找、插入、删除操作性能较平衡的数据结构。具体实现细节可以看这边文章： 红黑树深入分析及 Java 实现

Android 中的数据结构

HashMap 中采用 hash 值作为数组索引来存储数据，由于 hash 值的散列性（取决于Hash算法） 所以数组上的并不是每一个数组都会存储数据，造成了一定程度上的内存空间浪费，为了满足内存使用要求较高的移动设备，Android 平台中提供了内存更友好的容器类：

  • ArrayMap
    采用两个数组来，一个数组来存储所有 key 的 hash 值，另一个数组来存储所有的键值对及其 hash值，第一个数组会按照 hash 值大小排序，第二个数组根据 hash 在第一个数组中的位置来存储对应的键值对，读取一个键值对 A 的逻辑流为：根据 A 的 key 获取其 hash 值，然后根据二分查找法找到在第一个数组中的位置 i，然后用这个 i 作为索引从第二个数组中得到键值对，从而获取到目标 value 值。 可以看出这是一种以时间换取空间的策略，相对于 HashMap 的查找效率（O(1)+ 对应链表的长度）来说较低，如果数据量较大的情况下，其查找、插入、删除的效率都会明显小于 HashMap。

  • SparseArray
    是一种 key 类型为 int 的 ArrayMap，由于 Key 为基本数据类型，减少了 key 值装箱的性能影响，同 ArrayMap 相似有两个数组，不同的是第一个数组维护的直接是 int 类型的 key 值而不是 hash 值，所以较 ArrayMap 减少了hash的操作过程，只能用于 key 值为 int 的 键值对需求.(如果 key 值为 long，可用 LongSparseArray)

最后

数据结构往往伴随着算法，而其中涉及到的算法远远不止一两篇文章能写清楚的，我们可以先了解其特点，时间不足情况下可以先不必深入了解具体实现细节，善于选型就够平常开发需求了，如平时开发中常见的LruCache采用LinkedHashMap，任务队列常采用PriorityQueue，Android 开发中的View的缓存设计常用SparseArray, 数据结构和算法学习时只看代码往往不容易一下理解，这里可以借助动态可视化工具帮助我们：数据结构和算法可视化 。

谢谢阅读！
Thanks:
Java容器

Powered by Hexo
Theme - Material