java 集合框架

ArrayList
ArrayList底层是用数组实现的，可以认为ArrayList是一个可改变大小的数组。随着越来越多的元素被添加到ArrayList中，其规模是动态增加的。

数组中查询和赋值比较快，因为可以直接通过数组下标访问指定位置。

链表中删除和增加比较快，因为可以直接通过修改链表的指针（Java中并无指针，这里可以简单理解为指针。其实是通过Node节点中的变量指定）进行元素的增删。

LinkedList
LinkedList底层是通过双向链表实现的。所以，LinkedList和ArrayList之前的区别主要就是数组和链表的区别。

数组中查询和赋值比较快，因为可以直接通过数组下标访问指定位置。

链表中删除和增加比较快，因为可以直接通过修改链表的指针（Java中并无指针，这里可以简单理解为指针。其实是通过Node节点中的变量指定）进行元素的增删。

Vector
Vector和ArrayList一样，都是通过数组实现的，但是Vector是线程安全的。和ArrayList相比，其中的很多方法都通过同步（synchronized[同步]）处理来保证线程安全。

如果不涉及到线程安全问题，那么使用ArrayList是更好的选择（因为Vector使用synchronized，必然会影响效率）

HashSet
HashSet按Hash算法来存储集合中的元素，因此具有很好的存取和查找性能。底层数据结构是哈希表。
哈希表
一个元素为链表的数组，综合了数组与链表的优点。

HashSet具有以下特点：
不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也可能发生变化；
HashSet不是同步的；
集合元素值可以是null；

内部存储机制:
当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode方法来得到该对象的hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals方法比较true，但它们的hashCode方法返回的值不相等，HashSet将会把它们存储在不同位置，依然可以添加成功。
也就是说。HashSet集合判断两个元素的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode方法返回值也相等。

靠元素重写hashCode方法和equals方法来判断两个元素是否相等，如果相等则覆盖原来的元素，依此来确保元素的唯一性

LinkedHashSet
LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的，也就是说当遍历集合LinkedHashSet集合里的元素时，集合将会按元素的添加顺序来访问集合里的元素。

输出集合里的元素时，元素顺序总是与添加顺序一致。但是LinkedHashSet依然是HashSet，因此它不允许集合重复。

并且linkedHashSet是一个非线程安全的集合。如果有多个线程同时访问当前linkedhashset集合容器，并且有一个线程对当前容器中的元素做了修改，那么必须要在外部实现同步保证数据的冥等性。

TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。

迭代器 it 的两个基本操作是 next 、hasNext 和 remove。

调用 it.next() 会返回迭代器的下一个元素，并且更新迭代器的状态。

调用 it.hasNext() 用于检测集合中是否还有元素。

调用 it.remove() 将迭代器返回的元素删除。

大概用法：

// 创建集合
        ArrayList<String> sites = new ArrayList<String>();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");

        // 获取迭代器
        Iterator<String> it = sites.iterator();

        // 输出集合中的第一个元素
        System.out.println(it.next());

HashMap
它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

LinkedHashMap
LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

TreeMap
TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

Hashtable
Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

Collections
Collections提供以下方法对List进行排序操作

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), 用新元素替换旧元素。

Arrays
Arrays类包含用于操作数组的各种方法（例如排序和搜索）。此类还包含一个静态工厂，允许将数组视为列表。

如果指定的数组引用为null，则此类中的方法都抛出NullPointerException，除非另有说明。


List<T>  asList(T... a)：返回由指定数组构成的大小固定的列表，该列表不能使用add和remove方法改变长度

int binarySearch(Object[] a, Object key)：使用二分查找元素的索引

T[] copyOfRange(T[] original, int from, int to)：复制数组，并且指定开始/结束索引

T[] copyOf(T[] original, int newLength)：复制数组，并且指定复制长度

void fill(Object[] a, Object val)：使用指定元素填充数组

void fill(Object[] a, int fromIndex, int toIndex, Object val)：使用指定数组填充数组，并且指定填充的开始/结束索引

void sort(Object[] a)：对数组排序，需要实现数组元素的Comparable接口

void sort(Object[] a, int fromIndex, int toIndex)：对指定开始/结束索引的数组排序，需要实现数组元素的Comparable接口

void sort(T[] a, Comparator<? super T> c)：对数组排序，需要实现数组元素的Comparator接口

void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)：对指定开始/结束索引的数组排序，需要实现数组元素的Comparator接口

String toString(Object[] a)：数组转字符串

static Stream<T> stream(T[] array)：数组转为流

static IntStream stream(int[] array)：int数组转为流，还有DoubleStream和LongStream