java集合;java集合和数组的区别 收藏 0

Java基础 —— 集合（一）

• 数组是固定长度的数据结构，而集合是动态的数据结构
• 数组可以包含基本数据类型和对象，集合只能包含对象
• 数组只能存放同一类型的数据，而集合可以蹲房不同类型的
• 数组可以直接访问元素，集合需要通过迭代器或其他方法访问元素

 根据上图，可以看出，Java中集合的核心就是collection、map、Iterator，Collections是对集合进行操作的工具类，在图中，虚框代表接口或者抽象类，实框是类，实箭头表示继承，虚箭头表示实现；

collection：是集合List、Set、Queue的最基本接口

map：映射表的基础接口

Iterator：迭代器，可以通过迭代器遍历集合中的数据

 集合主要可以分为两类（collection和map）

• collection：集合List、Set、Queue的最基本接口（单列集合）
• List：所有元素按照进入先后顺序进行存储，可重复集合，存取顺序一致
• ArrayList：底层是数组，随机访问，增删慢，查询快，线程不安全
• 扩容机制：
• ArrayList容量为0时，添加元素需要扩容
• 无参构造：创建ArrayList后容量为0，添加一个元素后，容量变成10，之后正常扩容（为原来的1.5倍）
• 传容量构造：参数为0时，创建ArrayList后容量为0，添加一个元素后，容量为1，之后正常扩容
• 传列表参数：列表为空时，创建ArrayList后容量为0，添加一个元素后，容量为1，之后正常扩容
• ArrayList容量大于0，且是满的时，添加元素，正常扩容
• LinkedList：底层是双向链表，增删快，查询慢，线程不安全
• Vector：和ArrayList基本一样，但是它线程安全
• Set：不允许包含重复的值（可以为空，但是只能有一个），无序
• HashSet：使用哈希表存储元素，无序，其底层包装了一个HashMap去实现，所以查询插入速度较快
• LinkedHashSet：继承自HashSet类，它增加了一个重要特性，就是元素按照插入顺序进行存储
• TreeSet：底层是基于TreeMap实现，它支持两种排序：自然排序和定制排序
• Queue：队列，先进先出
• Map：映射表的基础接口（双列集合）
• HashTable：用哈希表实现，不可重复key，key不能为空，效率较低，线程安全
• HashMap：用哈希表实现，不可重复key，key可以为空，效率较高，线程不安全
• LinkedHashMap：用哈希表和双向链表实现，按照key的插入顺序存储
• TreeMap：用红黑树算法实现，默认按照所有的key进行升序排序，也可自定义排序方式

Java 集合概览

最近一直在写rust 的数据结构，回想Java 的数据结构，和rust 差别不大。其实不同的编程语言的数据结构是相通的，C++的童鞋肯定会想到STL。万变不离其宗，底层的数据结构还是大学的时候学的那点东西。无非是：数组、链表以及树，其他的东西都是在此基础之上演变出来的。

回到主题，我们介绍一个java的数据结构中常用的集合。java 的数据结构collection，有三种类型：list列表、queue队列以及set去重集合。另外一个map 主要存储kv 结构。

list下面有三种实现类：底层是数组的arrylist 以及底层是链表的 linkerlist，由于arrylist 底层是数组，插入的时间复杂度是O(n)，查询的时间复杂度是O(1)。而linkerlist 正好相反，插入的时间复杂度是O(1)，查询的时间复杂度是O(n)。vector 和arraylist 差别有两点：第一是线程安全，这个面试经常问的；第二是vector 扩容是按照100%扩容，而arraylist 是按照 50% 扩容。stack 继承了 vector 提供了先进后出能力

queue 比较简单提供了先进先出的能力，Deque则是提供两端插入和读取的能力，就是可以两端读写。priorityqueue 提供了排序的能力，按照优先级出队列。但它并非线程安全，如果需要线程安全请使用 PriorityBlockingQueue。

set 是去重集合，如果有相同的元素则只会保留一份。HashSet 底层是HashMap，LinkedHashSet 是通过 链表 + hash 表的方式实现，提供更优的插入性能。由于hash散列的特性，元素是无序的，另外一个接口是SortedSet 提供了排序的能力，具体实现类是TreeSet，底层通过树排序。

Map 主要是提供kv 存储，和set 类似，经常使用的是 hashmap，hashmap会通过hash 算法计算数组中的位置，如果发生了hash 冲突，则会通过链表或者树存储。LinkedHashMap底层则是链表方式存储元素，TreeMap 和 TreeSet一样提供排序功能。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com