集合框架
2020-07-28 17:41:27 0 举报AI智能生成
集合框架
作者其他创作
大纲/内容
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
HashSet（无序，唯一）
底层是HashMap
除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自
己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。
己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。
方法
添加
boolean add(e)
删除
boolean remove(o)
遍历
Iterator(E) iterator()
包含
boolean contains(o)
TreeSet（有序，唯一）
底层是红黑树(自平衡的排序二叉树)
方法
获取开头
E first()
获取结尾
E last()
获取子集
NavigableSet<E> subSetE （fromElement, boolean fromInclusive,
E toElement, boolean toInclusive）
E toElement, boolean toInclusive）
LinkedHashSet
继承于HashSet，内部通过LinkedHashMap实现
LinkedHashSet 中的元素顺序是可以保证
的，也就是说遍历序和插入序是一致的
的，也就是说遍历序和插入序是一致的
分支主题
0 条评论
下一页
为你推荐
查看更多
