List、Set和Map的区别、一般实现类

区别：
1、List集合中元素有序，可重复；
Set集合中元素无序（内部有序），元素不能重复；
Map内部元素为key-value，其中key-value是一对一关系，key不能重复，不能为关键字为key。

一般实现类：
1、List：ArrayList、LinkedList
2、Set：HashSet、TreeSet. 底层对Map集合的封装。
3、Map：HashMap、TreeMap、HashTable

ArrayList：
1、底层为动态数组，
2、有序集合、
3、支持随机访问（查询快，数组的内存划分是一块，可以通过索引直接访问，时间复杂度为O1）、
4、增删慢（删除时会遍历寻找，操作元素位于数组中间时，会影响前后元素索引，时间复杂度为On）、
5、占用空间 >= 元素个数，
6、初始容量为10，
7、扩容倍数为1.5倍(每次增加0.5)
8、元素可重复
参考：https://www.bilibili.com/video/BV1Gy4y1u7Gr?p=1&vd_source=a754d9ef602dc1c465a7f73cca0146f9
LinkedList：
1、底层为双向链表，
2、有序集合、
3、不支持随机访问（查询慢，需要从头或尾遍历链表，不能直接访问，时间复杂度为On）、
4、增删快（删除时会遍历寻找，操作元素不影响其他元素，时间复杂度为O1）、
5、占用空间 == 元素个数，
6、初始容量为0，
7、随元素增多而增大容量
8、元素可以重复
参考：https://www.bilibili.com/video/BV1Gy4y1u7Gr?p=1&vd_source=a754d9ef602dc1c465a7f73cca0146f9
HashMap：
1、底层为数组+链表 + 红黑树（jdk1.8后），
2、无序集合，
3、支持随机访问（查询快，时间复杂度O1）、
4、增删慢（底层为数组，原因类比ArrayList）、
5、允许key为null、
6、允许value为null、
7、线程不安全、
8、初始容量 1 << 4，
9、扩容倍数为2倍（扩容因子为0.75f，达到阈值时进行扩容）
参考：(51条消息) 深入理解HashMap和TreeMap的区别_treemap和hashmap区别flydean程序那些事的博客-CSDN博客
TreeMap：
1、底层为红黑树，
2、有序集合，
3、支持随机访问（查询快，时间复杂度On）、
4、增删慢（底层为红黑树，操作元素时会进行旋转【左旋、右旋】操作元素影响其他元素，时间复杂度On）、
5、不允许key为null、
6、允许value为null、
7、线程不安全、
8、初始容量为0，
9、随元素增多而增大容量
参考：(51条消息) 红黑树增删查详解红黑树的增删改查_Always_As的博客-CSDN博客
HashTable：
1、底层为数组+链表，
2、无序集合，
3、支持随机访问（查询快，时间复杂度为O1）、
4、增删慢（底层为数组，原因类比ArrayList）、
5、不允许key为null、
6、不允许value为null、
7、线程安全、
8、初始容量为11、
9、扩容倍数为2倍+1（扩容因子为0.75，达到阈值时进行扩容）
参考：(52条消息) HashMap、HashTable、HashSet的实现原理和底层数据结构hashtable底层数据结构皓晨的架构笔记的博客-CSDN博客
HashSet：
1、底层为HashMap，
2、无序集合，
3、元素不重复、
4、线程不安全、
5、不支持随机访问（未提供get方法）、
6、初始容量1 << 4（与HashMap同步）
7、扩容倍数为2倍（与HashMap同步）
8、可以为null
参考：(52条消息) HashSet详解_我为杰伦代言的博客-CSDN博客

LinkedHashMap：
1、底层为HashMap+双向链表（仅为保证顺序），
2、有序集合（分为插入顺序、访问顺序【put、get后的元素会将已存在的entry元素先删除、再插入的方式放到链表末端】）
3、线程不安全、
4、其他和HashMap一致
参考：(52条消息) HashMap与LinkedHashMap有什么区别_linkedhashmap和hashmap区别_aqiangzai的博客-CSDN博客
LinkedHashSet：
1、底层为HashSet，
2、有序集合
3、线程不安全，
4、元素不重复
5、可以存储null
6、效果类比LinkedHashMap
参考：(52条消息) LinkedHashSet详解_C陈三岁的博客-CSDN博客

//有序集合、支持随机访问(内存是一块的，查询快)、增删慢（会在遍历时进行增加或删除），占用空间 >= 元素个数, 底层使用数组实现
ArrayList