list set map 各自实现类的区别以及它们的底层原理和实现(部分)

小灰灰 2023-07-11 12:42 25阅读 0赞

## List ##

List是一个不唯一有序的集合。

##### 实现类： #####

**ArrayList：**  
底层结果是数组，所以查询快，增删慢，线程不安全。  
**Vector：**  
底层结果是数组，查询快，增删慢，线程安全。  
**Linkedlist**  
底层结果是双向链表，查询慢，增删快，线程不安全。

## Set ##

Set是一个唯一无序的集合。

##### 实现类： #####

**HashSet：**  
hashset其实是hashmap的一个实例，都是一个存放链表的数组，允许有null元素，hashset中的元素都存放在hashmap中的key上面，value是一个固定对象，hashset中的add()方法其实调用的是底层的hashmap中的put()方法，而如果是在HashMap中调用put，首先会判断key是否存在，如果key存在则修改value值，如果key不存在就插入这个key-value。而在set中，因为value值没有用，也就不存在修改value值的说法，因此往HashSet中添加元素，首先判断元素（也就是key）是否存在，如果不存在这插入，如果存在就不插入，这样HashSet中就不存在重复值。总结：无序，唯一，线程不安全，允许null值。  
**TreeSet：**  
是一个有序集合，是基于treemap实现的支持两种排序方式，自然排序和定制排序，treeset是非同步的，线程不安全。  
**LinkedHashSet：**  
有序，在迭代访问set中的元素时，性能比hashset好，但是插入时性能比hashset差。

## Map ##

map是以键值对方式存储数据的。

##### 实现类： #####

**HashMap：**  
底层结构是哈希表，不过在jdk1.8以前，哈希表是由数组+链表合体实现的，在jdk1.8中，哈希表是由数组+链表+红黑树合体实现的，当链表长度超过阈值(8)时，会自动转为红黑树，这样就大大的提高了效率，减少了查询时间。总结：线程不安全，不允许键值重复，允许null值和null键。  
\*\*存储元素时的流程和原理：\*\*当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部。也就是数组+链表的存储元素流程。  
**HashTable：**  
底层结果与hashmap相同，唯一不同的就是线程安全，键和值都不允许为null，提供了对键的列举，  
**TreeMap：**  
是一个有序集合，底层是红黑树，每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序。这点会在接下来的代码中做说明，如果指定了比较器则按照比较器来进行排序。