JAVA集合框架

一、集合框架概况类图

List、Set、Map的区别:

  - List:存储的元素是有序的，可重复的。
  - Set:存储的元素是无序的，不可重复的。
  - Map:使用键值对（key-value）存储。key是无序、不可重复的，value是无序、可重复的。每个键最多映射一个值。

二、List集合

1.ArrayList和Vector的区别:

  - ArrayList是List的主要实现类，底层使用Object[](数组)存储，适用于频繁的查找工作，现成不安全。
  - Vector是List的古老实现类，底层使用Object[](数组)存储，线程安全。

2.ArrayList和LinkedList的区别:

  - (1)是否保证线程安全：两者都是线程不安全的。
  - (2)底层数据结构：ArrayList底层使用的是Object[]数组的数据结构;LinkedList底层使用的双向链表的数据结构（JDK1.6之前为循环链表，JDK1.7采用双向链表）。
  - (3)插入和删除是否受元素位置的影响:
      #ArrayList采用数组存储，所以插入和删除的时间复杂度受元素位置的影响。在执行add(E e)方法的时候，         ArrayList默认会将元素插入到数组的末尾，这种情况的时间复杂度是O(1)。但如果要指定位置i进行插入元素，时间     复杂度则是O(n-i)。
      #LinkedList采用链表存储，所以add(E e)插入和删除的时间复杂度不受元素位置影响,近似O(1)。而制定位置i进行     插入元素，时间复杂度近似为O(n)。
   - (4)是否支持快速随机访问:ArrayList支持，LinkedList不支持，这都是由底层数据结构决定。ArrayList实现了Randomacces的接口，而LinkedList 没有实现该接口，但这并不是真正决定它是否具有随机访问元素的能力，这只是一个标识而已。
   - (5)内存空间占用:ArrayList的空间占用体现在其初始化的时候就会先分配固定的内存空间，大部分情况下都会有剩余的空间没有被使用；LinedList的空间占用体现在每个Node(元素)的大小，因为每个Node既要存储相应的业务数据，还要存储链表的前驱和链表的后继。

3.ArrayList的扩容机制:

三、Set集合

• HashSet:无序，唯一，基于HashMap实现的，底层采用HashMap来保存元素，线程不安全，可以存储null值.底层基于HashMap实现的，使用对象来计算hashcode值，因为hashcode可能相同，所以还需要equals()方法来判断对象的相等性。
• LinkedHashSet:LinkedHashSet是HashSet的子类，其内部是基于LinkedHashMap来实现的，能够按照添加的顺序遍历。
• TreeSet:有序，唯一，底层使用红黑树实现，能够按照添加元素的顺序进行遍历

  #HashSet如何检查重复
  - 当把对象加入到HashSet时，会先计算对象的hashCode值来判断对象加入的位置，同时也会与其他加入的对象的hashCode值进行比较，如果没有相同的，则视为没有重复。如果有相同的，则会调用equals()方法检查两个对象是否相同，如果相同，则视为重复，加入失败。 

四、Map集合

• HashMap:JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（拉链法解决冲突）。JDK1.8之后在解决哈希冲突有了变化，当链表长度大于阈值（默认8）时，将会把链表转为红黑树，以减少搜索时间。将链表转为红黑树前会进行判断，如果当前数组的长度小于64，那么会选择进行数组扩容，而不是转为红黑树。线程不安全。其可以存储null的key和value。HashMap默认的大小为16，每次扩容后，容量会变为原来的2倍。如果创建时给定容量的初始值，其会将其扩充为2的幂次方大小(tableSizeFor()方法进行保证)。
• LinkedHashMap:LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构（数组+链表或红黑树）组成。另外，LinkedHashMap在上面的基础上增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable:数组+链表组成。线程安全的，因为其内部的方法基本都经过synchronized修饰，性能不高。其不允许null为key或者value,否则会抛出NullPointException。Hashtable默认的大小为11，每次扩容后，容量会变为原来的2n+1。如果创建时给定容量的初始值，其会直接使用给定的大小。并且其没有将链表转为红黑树的机制。
• TreeMap:红黑树。实现了NavigableMap和SortedMap接口。这让其具备对集合中的元素根据key进行排序的能力。默认是按key的升序排序，不过我们也可以指定排序的比较器。
• ConcurrentHashMap:底层数据结构jdk1.7以前采用 分段数组+链表，jdk1.8以后使用数组+链表/红黑二叉树。在实现线程安全方面，jdk1.7以前使用分段锁对容器中一部分的数据加锁；jdk1.8以后使用synchronized和CAS来实现，只锁定当前链表或红黑二叉树的首结点，只要hash不冲突，就不会产生并发。

  #HashMap长度为什么是2的幂次方
  - 主要是为了尽可能的减少碰撞，为了减少碰撞，其使用的算法是<（n-1）& hash>,即对hash值用数组长度取模。

五、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个元素整体移到前面。当为负数时，将list前disntance个元素整体移到后面

int binarySearch(List list,Object key) ==>对List进行二分查找，返回索引，注意List必须是有序的

int max(Collection coll) =============> 根据元素的自然顺序，返回最大的元素。类比int min(Collection coll)

int max(Collection coll,Comparator c) ===> 根据定制排序，返回最大元素

void fill(List list,Object obj) =========> 用指定的元素代替指定list中的所有元素。

int frequency(Collection c,Object o) =====> 统计元素出现次数

int indexOfSubList(List list,List target) ===>统计target在list中第一次出现的索引，找不到则返回-1

boolean replaceAll(List list,Object oldVaule,Object newValue) ===>用新元素替换旧元素