𝑬𝒏𝒅𝒘𝒂𝒔 -- Java中集合类set、list、map特性总结

Java中的集合类总共有三种：set、list（列表包含Queue）、map

在这里插入图片描述

集合框架

List集合	实现方式	排列顺序	增删改查	线程安全	特点
ArrayList	底层使用数组	排列有序，可重复	速度快、增删慢	线程不安全	容量不够时，扩容至当前*1.5+1
Vector	底层使用数组	排列有序，可重复	速度快、增删满	线程安全，加了synchronized	容量不够，默认扩容一倍
LinkedList	底层使用双向循环链表数据结构	排列有序，可重复	查询慢、增删快	线程不安全

Set集合	实现方式	排列顺序	增删改查	线程安全	特点
HashSet	底层使用HashMap	排列无序，不可重复、独一无二	存取速度快	线程不安全	key可以为null，value为Object对象
TreeSet	底层使用二叉树	排列无序，不可重复	排序存储	线程不安全	内部是TreeMap的SortedSet
LinkedHashSet	采用Hash表存储，并用双向链表记录插入顺序	排列有序，不可重复	存取速度快	线程不安全	内部是LinkedHashMap

在这里插入图片描述

为什么HashSet的value不用null而是一个Object对象？

这就是需要从HashMap源码说起，HashMap的remove方法是去取key对应的node结点如果为null则返回null，如果有则返回node.value。这就可能会有问题了，当我如果node.value的值存储为null，则无法判断是否删除成功。所以则需要存储一个非null的值。

在这里插入图片描述

TreeSet：底层直接使用TreeMap，以存入的值为key，创建的一个static final Object对象为value，和HashSet极为类似 TreeMap底层用红黑树来存储数据结构，最直接的特点就是内部维系了个Comparator，比较和排序TreeMap中的元素。

Map集合	实现方式	排列顺序	增删改查	线程安全	特点
HashMap	底层使用Hash表	排列无序，key不可重复，值可以	存取速度快，每个链条在元素小于9的时候使用链表维护，大于等于9则转化为红黑树	线程不安全	key可以null，value也可以为null
HashTable	底层使用Hash表	排列无序，key不可重复，值可重复	存取速度快	线程安全	key、value都不允许为null
TreeMap	底层是红黑树	排列有序，key可重复定制Comparator方法	存取速度快	线程不安全

HashMap：底层是一个内部类Node数组，每一项存放一个Node<k, v>结点，允许存key和value都为null。
LinkedHashMap：是HashMap的一个子类，保证了记录的插入顺序，在用Iterator迭代的时候，先得到的肯定都先插入的。
TreeMap：实现sortedMap接口，可按照规范排序的，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。

HashMap的几个特性：

为了提升计算效率，我们传统计算位置是使用 hashcode % length，但这种计算效率太低，所以改用位运算，在length = 2^n时候 hashcode%length = hashcode & (length-1)。
为了减少hash碰撞，当长度为2^n的时候，做&运算的时候，起关键作用的是hashcode。