集合概念

什么是集合

JAVA中的集合是对数据结构的实现。

为什么要有集合

不同的数据结构优缺点不同。有些数据结构搜索快；有些数据结构插入或删除快；有些数据结构支持映射（key-value）。

JAVA集合框架

什么是JAVA集合框架

在JAVA中实现集合的架构。
方法：接口和实现分离，如下图所示：

JAVA集合架构.png

JAVA集合接口

JAVA集合接口图如下：

JAVA集合接口-jHQY.png

  • RandomAccess：标记接口支持高效随机访问

  • NavigableSet、NavigableMap：提供用于搜索和遍历有序集和映射的方法

JAVA具体集合

JAVA具体集合如下图：

JAVA具体集合-CfsP.png

  • List：允许根据意愿指定元素顺序，但如果没有记住位置则需要访问所有元素

    • ArrayList：数组实现，支持随机存取

    • LinkedList：链表实现，可以减少插入和删除元素的开销，只可以采用迭代器访问

  • Set：可以快速的查找对象，通过对元素计算出一个整数（散列码）方便查找

    • HashSet：散列表（数组+链表）实现，不关心元素顺序，散列表如下图：

      image-gcyL.png

    • TreeSet：红黑树实现，支持任意顺序插入，按照排序顺序读取，插入时比散列表更耗时

  • Queue：队列包括简单队列、双端队列，双端队列可以高效的添加或删除头尾的元素

    • ArrayDeque：双端队列实现，和LinkedList都可以提供双端队列

    • PriorityQueue：堆实现，堆是可以自组织的二叉树，添加和删除都会让最小的元素移动到根节点，典型用法是任务调度（每当启动新任务时，优先级最高（优先级为1）的任务从队列中删除）

JAVA映射

集（Set）允许通过散列码快速的查找元素，但这个元素信息量太大了，通过映射将关键唯一信息提取出来，可以更好的查找元素，具体的映射对象如下图：

  • HashMap：键是一个散列表，相当于键是HashSet

    • LinkedHashMap：①按插入的顺序进行访问 ②按访问的顺序来处理映射（可以将常访问的元素放到链表的尾部，不常访问的元素就会在列表前面，这些不常访问的元素可以改成从数据库读取）

  • TreeMap：键是一个红黑树，相当于键是TreeSet

  • WeakHashMap：弱散列映射，一个值对应的键在程序的任何地方都不在使用时，想要垃圾回收机制删除这个键/值对，可以使用WeakHashMap，WeakHashMap使用弱引用（todo什么是弱引用）保存键。

  • EnumMap：键类型为枚举类型的映射

  • IdentityHashMap：键的散列值不是通过hashCode函数计算，而是通过System.identityHashCode计算的，System.identityHashCode是Object.hashCode根据对象的内存地址计算散列码，对象比较时使用==，不使用equals。意味着，不同的键对象即使内容相同，也会被视为不同对象。