Java基础 (5) - 集合

Java集合大致分为 List、Set、Queue和Map 四种体系，
List代表有序、重复的集合；（ArrayList、LinkedList、Vector）
Set代表无序、不可重复的集合; （HashSet、LInkedHashSet、TreeSet）
Queue Java5增加，代表一种队列的集合 (priorityqueue)
Map则代表具有映射关系的集合

Collection接口
1.Set、LIst、Queue都继承Collection接口。
2.HashSet不能存重复的值（元素可以为null）,线程不安全，且是无序的,如果想有序使用LinkedHashSet。(由于使用了链表 插入和删除速度变快 但遍历速度降低)
3.ArryaList能存重复的值（元素可以为null），有序的，线程不安全，如果想线程安全可以使用Vector(有序)。还有个常用的LinkedList，插入和删除速度快，但遍历速度慢。
4.queue

Map
1.HashMap 可以存重复的值（元素可以为null） 线程不安全，且是无序的。想要线程安全可以使用HashTable。但HashTable不能使用null作为键或值 ， 想要有序 可以使用LinkedHashMap。
2.HashMap和HashTab的区别https://blog.csdn.net/mynameishuangshuai/article/details/52748731
3.区别点https://blog.csdn.net/xiamiflying/article/details/73050577
4.HashMap原理 https://blog.csdn.net/visant/article/details/80045154
https://www.jianshu.com/p/8b372f3a195d/
参考:
https://www.jianshu.com/p/589d58033841
https://blog.csdn.net/world_snow/article/details/79073234

线程安全
同步集合类: vector 、HashTable、 同步集合包装类 - Collections.synchronizedMap()和Collections.synchronizedList() 
并发集合类: ConcurrentHashMap 、CopyOnWriteArrayList、CopyOnWriteHashSet

同步集合比并发集合会慢得多，主要原因是锁，同步集合会对整个Map或List加锁
ConcurrentHashMap：把整个Map 划分成几个片段，只对相关的几个片段上锁，同时允许多线程访问其他未上锁的片段。
CopyOnWriteArrayList：CopyOnWriteArrayList、CopyOnWriteArraySet类（没有CopyOnWriteMap实现）允许多个线程以非同步的方式读，当有线程写的时候它会将整个List复制一个副本给它(写在副本)，适合读多写少这种场景，这会比使用同步集合更具有可伸缩性。

Collection和Collections的区别
1.java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。List、Set、Vector都继承了他。
2.Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索、线程安全等各种操作。

排序
void reverse(List list)：反转
void shuffle(List list),随机排序
void sort(List list),按自然排序的升序排序
void sort(List list, Comparator c);定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j),交换两个索引位置的元素
void rotate(List list, int distance),旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面。

查找，替换操作
int binarySearch(List list, Object key), 对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll),根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)，根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj),用元素obj填充list中所有元素
int frequency(Collection c, Object o)，统计元素出现次数
int indexOfSubList(List list, List target), 统计targe在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target).
boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素。

同步控制
Collections.SynchronizedList()
Collections.SynchronizedSet()
Collections.synchronizedMap()

备注:
2个数组求全集可以转成hashSet 交集可以用Collections的retainAll 差集可以用Collection的removeAll方法
参考:https://www.cnblogs.com/a2b1/p/7520099.html

TreeSet和TreeMap的关系
　　与HashSet完全类似，TreeSet里面绝大部分方法都是直接调用TreeMap方法来实现的。
相同点：

• TreeMap和TreeSet都是非同步集合，都是线程不安全，可使用方法Collections工具类方法来实现同步
• 查询速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)，而HashMap/HashSet则为O(1)。
• TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是排好序的。
  不同点：
• 最主要的区别就是TreeSet和TreeMap分别实现Set和Map接口
• TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）
• TreeSet中不能有重复对象，而TreeMap中可以存在
• TreeMap的底层采用红黑树的实现，完成数据有序的插入，排序

参考:https://www.cnblogs.com/pony1223/p/7907173.html

PriorityQueu
https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html