list、set、map区别

一、前言：

list 、set、 map区别：意思不同、用途不同。

1、意思不同

• List：有序、可重复。
• Set：无序、不可重复的集合。重复元素会覆盖掉。
• Map：键值对，键唯一、值不唯一。Map 集合中存储的是键值对，键不能重复，值可以重复。

结构图.png

2、用途不同

• List 集合中对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象。

• Map中的每一个元素包含一个键和一个值，成对出现，键对象不可以重复，值对象可以重复。

• Set 集合中的对象不按照特定的方式排序，并且没有重复对象，但它的实现类能对集合中的对象按照特定的方式排序。

cbc31c84a10446ac073d36cdb916ab7.png

3、ArrayList，LinkedList，HashMap的扩容机制

1、ArrayList底层是数组，初始容量为10，当使用空参构造器创建对象时对象此时的容量并不是10，当使用add给对象赋值操作时
此时的容量为10。当数组要满了就自动扩容为原容量的1.5倍。

2、LinkedList不用扩容，因为它实现了Dqueue和LIst接口，底层是用双向链表实现的，所以它对元素的增加、删除效率要比ArrayList好；
它是一个双向链表，没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好

3、HashMap的初始容量为16，扩容因子为0.75，扩容为原来容量的两倍。

4、在Java中，Map有4个主要的子类：HashMap、TreeMap、LinkedHashMap和ConcurrentHashMap。

• HashMap：它是最常用的Map实现类之一，它使用哈希表来存储键值对。它不保证元素的顺序，因此在迭代时不能保证顺序。它允许null键和值，但不保证线程安全。

• TreeMap：它是基于红黑树实现的，它可以保证元素按照键的自然顺序排序。它不允许null键，但允许null值。它也不是线程安全的。

• LinkedHashMap：它是HashMap的一个子类，它通过维护一个双向链表来保证元素的顺序。它既可以按照插入顺序迭代，也可以按照访问顺序迭代（即最近访问的元素排在最前面）。它允许null键和值，但不保证线程安全。

• ConcurrentHashMap：它是线程安全的HashMap实现类，它使用分段锁来实现并发访问。它的性能比Hashtable好，并且允许null键和值。它也可以按照插入顺序迭代。

• Hash Table：哈希表（Hash Table）是一种数据结构，也被称为散列表（Hashing）。它是基于键（Key）直接访问值（Value）的数据结构。哈希表可以快速的插入、删除、查找数据。

5、set

1、HashSet扩容结论

HashSet底层是Hashmap即数组+链表，添加元素时，table数组扩容为16，加载因子为0.75，所以临界值为16 * 0.75 = 12，意思是添加12个元素后，table数组将继续扩容至原来的2倍即32，临界值也会变为32 * 0.75 = 24，以此类推。
2、HashSet转成红黑树机制结论
当一条链表的元素得到8个之后，并且table数组的大小达到64，链表就转成红黑树，如果table数组未到64，table数组将扩容至原来的2倍，直至大小达到64链表转成红黑树为止。

二、 List 的区别

类型	底层实现	是否线程安全	扩容方式	是否允许添加 null 元素	功能
ArrayList	是数组	线程不安全	初始容量是 10，扩容因子是 0.5，超出现有长度后，自动扩容，扩容的容量最小是1.5倍	允许添加 null 元素	允许重复的元素，查询快，增删慢
LinkedList	链表	线程不安全	它是一个双向链表，没有初始化大小，也没有扩容的机制，就是一直在前面或者后面新增就好	允许添加 null 元素	允许重复的元素，查询慢，增删快
Vector	是数组	线程安全	Vector默认初始容量为10，扩容因子是 1，自动扩容，扩容的容量最小是2倍	允许添加 null 元素	允许重复的元素，查询快，增删慢

三、 Set的区别

注意：一条链表的元素个数达到默认值（8），并且数组的大小大于默认值（64），此链表就会进行树化（红黑树），数组的大小就行hashSet中所有元素的个数。
HashMap 底层维护了Node类型的数组table，默认为null

类型	底层实现	是否线程安全	扩容方式	是否允许添加 null 元素	功能
HashSet	HashSet的底层是基于HashMap实现的，HashSet底层是Hashmap即数组+（链表或者红黑树）	线程不安全	添加元素时，table数组扩容为16，加载因子为0.75，所以临界值为16 * 0.75 = 12，意思是添加12个元素后，table数组将继续扩容至原来的2倍即32，临界值也会变为32 * 0.75 = 24	允许添加 null 元素	不允许重复的元素，查询快，增删快，无序集合
LinkedHashSet	底层数据结构是LinkedHashMap，同时维护一个双向链表来保证元素的顺序(多增加一个双向链表)	线程不安全	初始容量为16，需要扩容table容量为16，临界值为12，以后再次扩容，则需要扩容table容量为原来的2倍	允许添加 null 元素	不允许重复的元素，查询快，增删快，有序集合
TreeSet	有序的集合，基于TreeMap实现（底层的数据结构是红黑树），支持两种排序方式：自然排序和定制排序	线程不安全	当TreeSet中的元素个数达到它的容量时，会自动进行扩容，将容量翻倍	不允许添加 null 元素	不允许重复的元素，查询快，增删快，有序集合

四、 Map的区别

类型	底层实现	是否线程安全	扩容方式	是否允许添加 null 元素	功能
HashMap	jdk1.7采用数组+链表；jdk1.8 采用数组+红黑树	线程不安全	HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍	允许key添加一个null元素	查询快，增删快，无序集合
LinkedHashMap	是继承 HashMap 的，底层是数组（哈希表）+链表/红黑树，并自己维持了一个双向链表，按照插入顺序进行访问，实现了LRU算法	线程不安全	LinkedHashMap 的扩容方式跟 HashMap 相同，当元素个数达到阈值时，会将数组容量扩大2倍	允许key添加一个null元素	查询快，增删快，有序集合
CocurrentHashMap	jdk1.7：Segments数组+ReentrantHashMap(作为互斥锁来控制并发访问)+链表，采用分段锁保证安全性；jdk1.8：Striped locking(算法来实现互斥锁控制，避免了使用synchronized关键字对整个HashMap进行加锁的效率问题，提高了并发度和性能表现) + CAS算法 +红黑树	线程安全	当链表中元素个数超过默认设定（8个），当数组的大小还未超过64的时候，此时进行数组的扩容，如果超过则将链表转化成红黑树	不允许null键和值	查询快，增删快，无序集合（ConcurrentHashMap是线程安全的数组,是HashTable的替代品,同为线程安全,其性能要比HashTable更好）
HashTable	底层通过数组+链表的方式实现	线程安全（通过synchronized关键字实现线程安全）	创建时如果不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩容，容量变为原来的2n+1	允许null值作为key和value	查询快，增删快，无序集合
TreeMap	基于红黑树实现	线程不安全	新底层数组的长度是原长度的2倍	key 不可以存入null	查询快，增删快，有序集合

注意：Android 中常用的 map 集合:

类型	底层实现	是否线程安全	扩容方式	是否允许添加 null 元素	功能
ArrayMap	ArrayMap 的底层实现基于数组和红黑树，适用于小型数据集	线程不安全	每次扩容时的新数组大小是原有数组大小的2倍	可以添加null元素	查询快，增删快，有序集合（相比HashMap内存空间占用更少）
SparseArray	它的底层实现主要依赖于两个数据结构：一个数组和一个 Map	线程不安全	每次扩容时的新数组大小是原有数组大小的2倍	允许存储null元素	查询快，增删快，有序集合（Key 是 int 是代替 HashMap）

五、 其它小细节：

1、hashMap和LinkedHashMap区别

HashMap和LinkedHashMap都是Java集合框架中的Map接口的实现类，其中HashMap基于哈希表实现，而LinkedHashMap则继承自HashMap，底层使用哈希表和双向链表结合的方式实现。它们之间的区别主要体现在以下几个方面：

-插入顺序：HashMap不保证映射的顺序，而LinkedHashMap会根据元素插入的顺序维护一个双向链表，因此保证了映射的顺序，可以通过get操作访问元素的插入顺序。

• 迭代顺序：LinkedHashMap迭代元素的顺序是插入顺序，而HashMap的迭代顺序是随机的。
• 性能：由于LinkedHashMap在底层额外维护了一个双向链表，因此在插入或删除元素时需要更多的操作，因此HashMap的性能通常比LinkedHashMap要高。
• 内存占用：由于LinkedHashMap维护了一个双向链表，因此它的内存占用通常比HashMap要高一些。

综上，如果需要维护元素的插入顺序或者迭代顺序，并且对性能和内存占用要求不是非常高，可以选择使用LinkedHashMap。如果只关心键值对的映射关系，对性能和内存占用有较高要求的话，可以选择使用HashMap。

2、hashMap和TreeMap区别

HashMap和TreeMap都是Java中的集合类，其中HashMap是基于哈希表实现的，而TreeMap则是基于红黑树实现的。它们之间的区别主要体现在以下几个方面：

• 插入顺序：HashMap不保证映射的顺序，而TreeMap会根据元素的键值进行排序，因此保证了映射的顺序。
• 元素访问时间复杂度：HashMap的元素访问时间复杂度是常数级别的，即O(1)，而TreeMap的元素访问时间复杂度是基于红黑树的复杂度，通常是O(log(n))。
• 键的类型：HashMap可以使用任何类型的对象作为键，只要它们能正确的实现hashCode()和equals()方法，而TreeMap的键必须实现Comparable接口或提供自定义的Comparator比较器来进行比较。
• 内存占用：由于TreeMap需要维护红黑树的结构，因此它的内存占用相对较高。而HashMap在元素较少时，占用内存较小。

综上，如果需要按照键值对的键进行排序访问元素，可以选择使用TreeMap。如果只关心键值对的映射关系，对元素访问速度和内存占用要求较高的话，可以选择使用HashMap。

3、hashMap和CocurrentHashMap区别

HashMap和ConcurrentHashMap都是Java中的集合类，但它们之间有以下区别：

• 线程安全性：HashMap是非线程安全的，而ConcurrentHashMap是线程安全的，多个线程可以同时读写ConcurrentHashMap的不同部分。
• 内部实现方式：HashMap是基于哈希表实现的，而ConcurrentHashMap是基于分段锁实现的，它将整个Map拆分成多个“段”，其中每个段都有自己的锁，不同的线程可以同时访问不同的段，从而提高并发性能。
• 迭代器支持：在使用Iterator迭代器遍历HashMap时，如果在遍历过程中对HashMap进行了修改操作，会抛出ConcurrentModificationException异常。而在ConcurrentHashMap中，它支持在并发修改的情况下安全的使用迭代器进行遍历操作，而不会抛出异常。
• 数据一致性：在进行并发读写的情况下，HashMap不能保证数据的一致性，而ConcurrentHashMap能够保证更新操作之后的读操作能够看到更新后的数据。

综上，如果需要在多线程环境下访问Map，建议使用ConcurrentHashMap，它提供了更好的并发性能和线程安全性，而如果是单线程环境下访问Map，可以使用HashMap。