JAVA集合

JAVA集合

collection

List

ArrayList

有序可重复，线程不安全，底层是数组，查询快，增删慢

初始大小10，扩容时公式：newCapacity = oldCapacity + (oldCapaticy >> 1)，就是扩大为原来的1.5倍

底层数据结构：Object数组

LinkedList

有序可重复，线程不安全，底层是双向链表，查询慢，增删快

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

Vector

和ArrayList类似，线程安全的（所有方法都用了synchronized 修饰）

扩容：原来的两倍

Set

HashSet

无序无重复元素，线程不安全

底层由HashMap实现，为哈希表结构，新增元素相当于HashMap的key，value默认为一个固定的Object

TreeSet

有序无重复元素，线程不安全

与HashSet集合类似，TreeSet也是基于Map来实现，具体实现TreeMap

底层结构：为红黑树

Queue

迭代器

Iterator

轻量级对象

单向移动

使用方法interator()返回一个Iterator

ListIterator

Iterator子类型

用于List访问

双向移动

使用方法listIterator()创建

Map

HashMap

Java 8

数据结构

数组+链表+红黑树

插入

尾插，当链表长度超过8时，就会变为红黑树

Java 7

数组+链表

头插

高并发时会导致死锁

加载因子

0.75

初始容量

16

扩容

扩容到原数组长度的2倍

解决哈希冲突

链地址法

无序，线程不安全

TreeMap

有序，线程不安全

底层数据结构：红黑树

HashTable

无序，线程安全

将HashMap的所有方法都加上了synchronized

底层数据结构：数组+链表

ConcurrentHashMap

CAS + synchronized 

数组 + 链表 + 红黑树

Java 7 

分段锁，ReentrantLock

数组 + 链表

允许null值情况

容器继承图