Java集合框架（1.8）

Java集合框架

Iterableinterface

Collectioninterface

Listinterface

ArrayList

底层是基于数组来实现容量大小动态变化的。get效率高，非尾部的增删会带来元素的整体移动

插入时会判断数组容量是否足够，不够的话会进行扩容 扩容时重新申请新的内存空间，并把就数组拷贝到新数组上去，非线程安全

int size; 

 实际元素个数

Object[] elementData; 

数组存储  默认是空数组

DEFAULT_CAPACITY = 10;

初始容量大小为 10;一开始是空数组，第一次添加元素时容量扩大至 10 的。

Arrays.copyof() 拷贝数组

int newCapacity = oldCapacity + (oldCapacity >> 1);

可看出扩容因子子1.5

遍历用for 循环，效率高，用迭代器iterator 遍历会非常慢，因为做了很多安全检查但支持边遍历边remove

vector

很少用

线程安全，但性能低

增删改查很多方法都是synchronized 锁对象

扩容因子1

LinkedList

链表存储，不需要扩容

CopyOnWriteArrayList

线程安全 读写分离

volatile Object[] array;

通过volatile 确保可见性和可序性

get，遍历等读操作不会占用锁

ReentrantLock lock = new ReentrantLock();

通过锁确保增删改

缺点 

占用内存 1 增删改操作都要复制一个数组出来

只能保证数据的最终一致性，不能保证数据的实时一致性。

MAP(散列表)Interface

HashMap

数据结构

1.7 数组+链表

jdk1.8 数组+链表+红黑树

工作原理

元素数组

hash 对应数组 位置 公式   (table.length - 1) & hashCode

如何解决哈希冲突

如何扩容

size

hashmap元素个数

length

table  数组 长度

默认填充因子

0.75

初始容量

默认16

threshold

threshold=初始容量*默认填充因子

map的元素个数size > threshold  就会触发扩容 扩容的数组为原来length的2倍

非线程安全

KEY value 允许null值 遍历是无序的

LinkedHashMap

保存着元素插入的顺序(插入有序性)，并且可以按照我们插入的顺序进行访问

数组 + 单链表 + 红黑树 + 双链表

在hashmap的基础上用双链表保存元素之家的先后插入关系

IdentityHashMap

基本不用

允许key相同数据插入

HashTable

线程安全

key、value都不可以为null

底层数据结构及扩容原理跟HashTable差不多 扩容不需要2的n次方

ConcurrentHashMap替代HashTable

ConcurrentHashMap

数据结构跟hashmap及扩容基本一样

1.8 采用NODE  + CAS + synchronized

TreeMap

基于红黑树实现

默认按照keys的自然排序排列

区别

HashMap 无序 LinkedHashMap 插入有序性 TreeMap 按Key自然排序

如果只需要存储功能，使用HashMap与LinkedHashMap是一种更好的选择；如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。

    SETinterface

HashSet

哈希表结构(底层HashMap)，主要利用HashMap的key来存储元素

TresSet

TresMap的缩水版

LinkedHashSet

LinkedHashMap的缩水版