java集合

java集合

List

ArrayList

底层是数组，排列有序可重复

线程不安全

查询效率高，增删效率低

无参构造器默认容量为0，第一次add时设置默认容量为10

扩容机制：1.5左右

增删都需要复制

内存连续

Vector

底层数组实现，排列有序可重复

线程安全，内部方法大量使用synchronized关键字，效率低下

无参构造器默认容量10

容量不够时，Vector默认扩展一倍容量

LinkedList

底层使用双向循环链表数据结构

排列有序可重复

set

HashSet

无序集合、线程不安全

底层使用Hash表实现

存取速度快

内部是HashMap

TreeSet

底层TreeMap、有序集合、线程不安全

底层使用二叉树实现

内部是TreeMap的SortedSet

LinkHashSet

采用Hash表存储，并使用双向链表记录插入顺序

内部 是LinkedHashMap

Map

HashMap

jdk1.7 结构：数组+链表 头插法（在扩容时可能产生循环链表）

jdk1.8 结构：数组+链表+红黑树，链表长度大于8并且数组长度大于64才转换为红黑树，尾插法-put与get方法未加锁，线程不安全

默认初始容量为16，负载因子默认为 0.75，扩容后数组大小为当前的 2 倍

底层哈希表

允许key值为null，value也可以为null

LinkedHashMap 

HashMap+双向链表，访问有序性

默认初始容量 (16)和默认负载因子(0.75)

ConcurrentHashMap

线程安全

jdk1.7

Segment 数组，Segment 通过继承ReentrantLock 来进行加锁

ConcurrentHashMap 有 16 个 Segments

jdk1.8

CAS乐观锁+synchronized

HashTable

任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap， 因为 ConcurrentHashMap 引入了分段锁。Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用HashMap 替换，需要线程安全的场合可以用ConcurrentHashMap 替换

TreeMap

可排序

底层二叉树