

首页  思维导图  详情



集合框架

2020-07-28 17:41:27   0  举报





仅支持查看

AI智能生成

集合框架

java

集合框架

模版推荐

作者其他创作

大纲/内容

List

ArrayList

底层是Object数组

线程不安全

插入和删除

位置为末尾时，时间复杂度约为O（1）

位置为i时，时间复杂度为O（n-i）

支持快速随机访问（通过下标）

内存空间占用

数组需要预留空间，所以会有空间浪费

对循环方法的选择

优先使用for循环，其次是foreach（foreach底层也是iterator）

方法

扩容

void grow

添加

boolean add（e）

void add（index，e）

void rangeCheckForAdd(index)

删除

boolean remove（o）

boolran fastRemove(index)

E remove（index）

获取

E get（index）

void rangeCheck(index)

E elementData(index)

更新

E set（index，e）

遍历

Iterator<E>   iterator()

包含

boolean contains(o)

int indexOf(o)

LinkedList

底层是双向循环链表（jdk1.6之前是循环链表）

线程不安全

插入和删除

时间复杂度约为O（1）

不支持快速随机访问

内存空间占用

链表需要存储直接前驱和直接后记，所以会占用额外的空间

对循环方法的选择

优先使用iterator

方法

添加

boolean add(e)

void add(index,e)

Node<E> node(index)

void linkBefore(e,Node<E> succ)

删除

boolean remove(o)

E unlink(Node<E> x)

E remove(index)

获取

E get(index)

更新

E set(index,e)

遍历

ListIterator <E> listIterator(index)

包含

boolean contains(o)

int indexOf(o)

Vector

底层是Object数组

线程安全

synchronized

Map

HashMap

jdk1.8之前底层是列表散列（数组和链表组合使用），jdk1.8之后是列表散列+红黑树

实现原理

HashMap通过扰动函数得到hash值，经过计算得到要存储的位置，如果当前位置存在元素，判断hash值以及key是否相同，相同则覆盖，不同则通过拉链法解决冲突（为什么要使用扰动函数？扰动函数可以减少碰撞）

线程不安全

可以有一个null键，多个null值

初始容量为6，每次扩容为原来的2倍（当指定初始容量时，初始容量为2的幂次方）

扩容方法resize（）在多线程下操作可能导致死循环。jdk1.8已经解决了这个问题

ConcurrentHashMap

线程安全

在 JDK1.7 的时候，Segment（分段锁）首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。JDK1.8 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。

要想线程安全，使用这个而不是使用HashTable

HashTable

线程安全

(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程 访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态

效率低

不能有null键、null值，当put null键值时会抛出空指针异常

初始容量为11，每次扩容为2n+1（当指定初始容量时，初始容量为所指定的容量）

LinkedHashMap

继承于HashMap，底层拉链式加红黑树实现

TreeMap

红黑树

Set