JAVA的集合类型总结（List，Vector，Set，Map）_java中的有哪些集合数据类型

1.Collection（存放单值类型数据）

 （1）List （有序、可重复）

   注意：有序指的是集合中的元素有下标，放进去和取出来的顺序一致

   1）ArrayList

       底层是数组。优点：查询效率高，因为数组中的元素在内存中是连续的，可以快速的根据下标获取集合中的元素；缺点：增删效率低，因为在对数组中元素进行增删操作的时候，涉及移位。

   2）LinkedList

       底层是链表。优点：增删效率高       因为对链表上的元素进行增删操作的时候，不需要移位，只需要改变链表中节点的指向即可。缺点：查询效率低，查询集合中的元素的时候，需要进行全链表的扫描。

   3）Vector

和ArrayList类似，底层也是Object[ ]数组，只不过是线程安全的。

ArrayList 和 LinkedList 的区别：

1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
2. 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
5. 内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

（2）Set 无序、不可重复

   1）HashSet

        底层是HashMap

   2）SortedSet      让集合中的元素具备了排序的能力

   3）TreeSet

        底层是TreeMap 

HashSet、LinkedHashSet 和 TreeSet 三者的区别

• HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
• HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
• 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

2.Map （存放的是键值对类型 ）

   1）HashMap

         数组 + 链表 + 红黑树

   2）SortedMap

        元素排序

   3）TreeMap

         底层是可排序的二叉树，在向集合中放元素的时候，遵循左小右大的原则，在取元素的时候按照中序遍历的方式取原则。

Hashmap的底层原理

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。

         HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

ConcurrentHashmap的底层原理

      Java 7 中 ConcurrentHashMap 的存储结构如上图，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。