java集合

Set

LinkedHashSet

List

LinkedList

List实现类

底层数据结构采用红黑树来实现，元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排序需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法；

HashTable

LinkedList是java提供的一个集合类，它实现了List、Deque接口，它的底层是一个双向链表。是通过静态内部类Node实现的，Node类中有指向上一个结点的prev和指向下一个结点的next，以及当前结点的值组成的。元素有序可重复。增加删除效率高，随机访问、修改效率低。线程不安全。当我们调用无参构造方法时，会创建First、last两个属性，默认为null。调用add方法去添加元素，第一次添加时会创建一个Node类型的结点，令first、last都指向该节点。之后的每一次添加，first指向不变，last指向后移。LinkedList获取指定位置的元素时，调用的是get方法，方法内会比较指定的下标值和size的大小关系。如果index小于size右移一位，则从前向后查找，否则从后向前查找，使用的是二分查找的思想。LinkedList获取某个元素的下标（位置）时，调用的是indexOf方法，会从前向后顺序遍历链表，调用equals方法去比较元素的值，查找到就返回下标。 

不能重复、无序、不是线程安全的、集合元素可以为NULLE

Vector是java提供的一个集合类，实现了List接口。它的底层是个Object数组，初始化Vector时会创建一个默认容量为10数组。线程安全，效率较低。

Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。所以通过指定的key就可以取出对应的value。Map接口有四个比较重要的实现类，分别是HashMap、LinkedHashMap、TreeMap和HashTable。TreeMap是有序的，HashMap和HashTable是无序的。Hashtable的方法是同步的，HashMap的方法不是同步的。这是两者最主要的区别。Map 没有继承 Collection 接口， Map 提供 key 到 value 的映射，你可以通过“键”查找“值”。一个 Map 中不能包含相同的 key ，每个 key 只能映射一个 value 。 Map 接口提供 3 种集合的视图， Map 的内容可以被当作一组 key 集合，一组 value 集合，或者一组 key-value 映射。

HashSet

LinkedHashMap

TreeSet

1.实现唯一性的比较过程：存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值，然后和所存储的元素的hashCode值比较，如果hashCode不相等，则所存储的两个对象一定不相等，此时存储当前的新的hashCode值处的元素对象；如果hashCode相等，存储元素的对象还是不一定相等，此时会调用equals()方法判断两个对象的内容是否相等，如果内容相等，那么就是同一个对象，无需存储；如果比较的内容不相等，那么就是不同的对象，就该存储了，此时就要采用哈希的解决地址冲突算法，在当前hashCode值处类似一个新的链表， 在同一个hashCode值的后面存储存储不同的对象，这样就保证了元素的唯一性。2.Set的实现类的集合对象中不能够有重复元素，HashSet也一样他是使用了一种标识来确定元素的不重复，HashSet用一种算法来保证HashSet中的元素是不重复的， HashSet采用哈希算法，底层用数组存储数据。默认初始化容量16，加载因子0.75。3.Object类中的hashCode()的方法是所有子类都会继承这个方法，这个方法会用Hash算法算出一个Hash（哈希）码值返回，HashSet会用Hash码值去和数组长度取模， 模（这个模就是对象要存放在数组中的位置）相同时才会判断数组中的元素和要加入的对象的内容是否相同，如果不同才会添加进去。Hash算法是一种散列算法。

java提供的集合类。是Map接口的实现类，底层是哈希表。Hashtable的默认大小是11，扩容因子为0.75，每次扩容后的容量是之前的2n+1倍。它是线程安全的集合类，Hashtable效率低下。Hashtable的初始容量使用了素数，并且扩容不是2的次幂，这也导致它的效率比HashMap低。Hashtable对Key的分散不如HashMap充分，发生哈希冲突的概率较高。 

底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。

ArrayList是Java提供的一个集合类，它实现了List接口，它的底层是一个object类型的数组。默认容量为0，元素有序可重复。它的查询修改效率高、增加删除效率低。线程不安全。当我们调用无参构造方法时，会把底层的final类型的空数组赋值给底层数组；当我们第一次add元素的时候，数组的长度会扩容到10。之后当容量满了，再次扩容，将会按照1.5倍去扩容。扩容的时候调用的是grow方法，内部是将数组长度右移一位+数组长度得到的得到的新长度。它底层调用的是arrays.copyOf方法，底层调用了system.arraycopy方法，这是一个本地（native）方法，由操作系统执行，效率高。【ArrayList默认容量为0】当我们调用有参构造方法指定初始容量时，会直接在底层创建一个指定容量的object数组。这一个过程没有扩容，指定容量大于0时，会直接把指定容量的数组付给底层数组，指定容量等于0时，是把空数组赋给底层数组。 

ArrayList 基于动态数组，连续内存储存，适合下标访问

TreeMap

Map

ArrayList

HashMap

HashMap是Java提供的一个集合类，它实现了Map接口，存储的是键值对格式的数据，允许Key-Value为空。在JDK1.8之前HashMap的底层是哈希表，在JDK1.8中HashMap的底层改为哈希表+红黑树，是一种以空间换时间的思想，查询效率高，线程不安全。HashMap的默认容量为16，扩容因子为0.75。一旦HashMap中键值对的数量超过容量与扩容因子的乘积，HashMap将会进行扩容，将数组长度扩大为之前的2倍。扩容时调用resize方法，并将原集合中的元素添加到新的集合中，这一步相当耗费性能。在调用put方法向HashMap中添加元素时，对Key进行了充分的哈希操作。先计算Key的hashCode、再将hashCode右移16位后做异或运算、最后拿着得到的值和【数组长度减一】做与运算（相当于对底层数组的长度取模，但比取模效率高）， 从而得到该Key对应的数组下标值。在创建一个HashMap时，如果指定的初始容量，则该初始容量将被转换为大于等于该数值的最小的2的次幂，并且要求容量最小为16。JDK1.8中做的优化是：当数组中某位置的链表长度大于等于8时，该链表将被转换为红黑树；当树中的键值对数量小于等于6时，红黑树将被重新转换为链表。因此当在6-8左右不断的增删元素时，HashMap的性能反而不高。HashMap添加元素调用的put方法，内部调用的是putVal方法。计算key在数组中的下标时，会计算key的hashCode，再将hashCode右移16位后做异或运算，从而进行二次哈希，降低哈希冲突的概率。HashMap将初始容量设置为16，一方面考虑了它是2的次幂，在扩容时直接进行移位操作效率较高。另一方面之所以不设置为8，是因为容量太小会有频繁的扩容；不设置为32是因为可能会浪费空间。 

java提供的集合类。是Set接口的实现类，底层是TreeMap。TreeSet的元素有序且不可重复（如果使用比较器强制compare方法返回一个非0的数，就可以将重复元素存入），TreeSet内部维护了一个TreeMap，它的元素放在了TreeMap的Key的位置上，所维护的TreeMap的Value位置是一个Object类型的常量。元素是否可以为空取决于它的比较器。 

底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。

java提供的集合类。是Set接口的实现类，底层是HashMap，元素无序且不能重复。HashSet的元素放在了它所维护的HashMap的Key的位置上，该HashMap的Value是一个Object类型的常量。在向HashSet中添加元素时，会调用HashMap的put方法，通过调用Key的hashCode方法计算其哈希码等运算确定该元素对应的数组中的下标，然后会调用该元素的equals方法遍历判断数组某下标处的链表中是否有相同元素，HashSet就是这样实现判重的。 

Vector

无序不可重复，并做内部排序

java提供的集合类，是Map接口的实现类，底层是红黑树。元素有序。TreeMap中的key必须指定比较规则，要么自定义类型实现Comparable接口、重写compareTo方法，要么在创建TreeMap时传入一个比较器。Integer、String等常用类型默认已经实现了Comparable接口、重写了compareTo方法。通过比较器返回正数、负数、零分别可以让元素升序排列、降序排列或去重。TreeMap中Key是否允许为空取决于它的比较规则。TreeMap是线程不安全的集合类。 

元素按进入先后有序保存，可重复