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一样提供排序功能。