集合
2019-02-20 09:46:26 107 举报AI智能生成
集合框架【Java】
作者其他创作
大纲/内容
List
ArrayList
数据结构
动态数组
线程安全
不安全
插入和删除
插入和删除受元素位置影响，如果是add（e），
就是添加到尾部，时间复杂度为O(1)如果是
|指定位置插入的时间复杂度为O(n-i)
就是添加到尾部，时间复杂度为O(1)如果是
|指定位置插入的时间复杂度为O(n-i)
快速随机访问
支持，通过下标get(index)来迅速获取元素对象
内存空间占用
尾部需要预留一段空间，防止数组越界
LinkedList
数据结构
双向链表
线程安全
不安全
插入和删除
链表存储，所以插入和删除不受
元素位置影响，都是近似O(1)
元素位置影响，都是近似O(1)
快速随机访问
链表不支持
内存空间占用
空间消耗比ArrayList更大，因为每个元素
需要更多的空间前指针和后指针及数据
需要更多的空间前指针和后指针及数据
Vector
线程安全
安全
原理
其实就是方法加了synchronized修饰的ArrayList
问题
Java中遍历ArrayList的过程中
删除元素操作会发生并发修改异常？
删除元素操作会发生并发修改异常？
循环遍历的时候，删除元素，首先会定位到元素位置删除，
然后复制数组往前移动一位，遍历到最后就会出现null，报错了
然后复制数组往前移动一位，遍历到最后就会出现null，报错了
总结
非并发
写多读少
LinkedList
读多写少
ArrayList
并发
Vector
Map
HashMap
数据结构
JDK1.7
散列（数组+链表）
JDK1.8
散列（数组+链表）+红黑树
链表长度大于8就会转为红黑树
初始大小是16，扩容因子是0.75，扩容都是2的幂次方，
如果设置的初始值不是2的n次方，hashmap会自动扩充为2
的n次方
如果设置的初始值不是2的n次方，hashmap会自动扩充为2
的n次方
线程安全
不安全
是否支持NULL键和值
支持
解决hash冲突
拉链法
我们先根据key来获取Hash值,然后通过(数组length-1）
和hash取模获取当前数组存放的下标。若是链表上有值，
那么追加到尾部，然后取值的时候判断key==和equals
和hash取模获取当前数组存放的下标。若是链表上有值，
那么追加到尾部，然后取值的时候判断key==和equals
并发闭环问题
扩容方法会新建一个数组，复制原数组到新的数组，由于下标挂着链表，
扩容之后会导致环形链表的出现，JDK1.8已经解决了这个问题了。
扩容之后会导致环形链表的出现，JDK1.8已经解决了这个问题了。
HashTable
数据结构
初始大小是11，每次扩容都是2n+1
线程安全
安全
内部方法基本上都经过了synchronized修饰
是否支持NULL键和值
不支持
ConcurrentHashMap
1.7
数据结构
分段锁 segment，锁的粒度更加精细
分段的数组+链表的形式
分段的数组+链表的形式
原理
put
1）二阶段hash，第一阶段是定位到哪个segment
第二阶段是定位到哪个entry
第二阶段是定位到哪个entry
2）entry中，除了value，还有key，hash和next都是final修饰
意味着不能从中心或者尾部添加或者删除节点，一律添加到头部
意味着不能从中心或者尾部添加或者删除节点，一律添加到头部
3）通过count来统计段内的数据个数，只有新增和删除
会修改这个值，每次都是在上述俩个步骤的最后一步进行修改
会修改这个值，每次都是在上述俩个步骤的最后一步进行修改
get
get不需要加锁，采取volatile修饰共享变量
这样每次get的时候都可以获取最新的结构更新
由于遍历不需要加锁的原因是因为next是final。要么
是不为空返回，为空的话就加锁重读
这样每次get的时候都可以获取最新的结构更新
由于遍历不需要加锁的原因是因为next是final。要么
是不为空返回，为空的话就加锁重读
remove
由于是final，所以删除节点的时候会删除某个节点
然后那个节点之上都复制，然后最后一个节点指向
被删节点的下一个节点
然后那个节点之上都复制，然后最后一个节点指向
被删节点的下一个节点
resize
扩容只会对段扩容而非整个桶
跟HashMap不同的是，段是先判断
是否需要扩容再put，而hashmap是
先put再判断是否要扩容
跟HashMap不同的是，段是先判断
是否需要扩容再put，而hashmap是
先put再判断是否要扩容
size
先尝试不锁住segment的方式来统计segment的大小
如果统计过程中，容器的count发生变化则采取加锁的方式
如果统计过程中，容器的count发生变化则采取加锁的方式
1.8
取消了分段锁，而是采取了cas和synchronized来保证并发安全，
synchronized只锁住当前链表或者红黑二叉树的首节点，只要hash
不冲突，就不会产生并发，效率很高
synchronized只锁住当前链表或者红黑二叉树的首节点，只要hash
不冲突，就不会产生并发，效率很高
线程安全
安全
ConcurrentHashMap与Hashtable的区别
底层数据结构：1.7分段数组+链表,1.8散列红黑树，而hashtable一直是散列
实现线程安全的方式【重要】
ConcurrentHashMap
1.7
分段锁对整个桶进行切割，增加锁的粒度
如果不是访问同一个segment，就不存在竞争
如果不是访问同一个segment，就不存在竞争
1.8
Node数组+链表+红黑树，并发控制使用CAS与Synchronized
HashTable
使用synchronized来保证，效率低下，多线程访问同一个同步方法
会导致阻塞或者轮询，竞争会愈发激烈
会导致阻塞或者轮询，竞争会愈发激烈
TreeMap
数据结构
红黑树
一种特殊的AVL树
是否有序
有序
字典顺序来排序【升序】
我们可以通过往对象中构造
一个Comparator对象来定制排序
一个Comparator对象来定制排序
原理
put
1）构建二分搜索树
2）构建红黑树
左旋
右旋
着色
deleteEntry
删除比较特殊，他不是直接刪除，而是找到要刪除节点子节点，
然后用子节点来代替删除节点这样就删除子节点即可，简单的
说就是把要删除节点和他的左孩子的最右和右孩子的最左交换
然后用子节点来代替删除节点这样就删除子节点即可，简单的
说就是把要删除节点和他的左孩子的最右和右孩子的最左交换
LinkedHashMap
数据结构
继承于HashMap,同时内部增加了
一个链表，用来保证元素的顺序
一个链表，用来保证元素的顺序
是否有序
基于元素进入集合的顺序
或者被访问的先后顺序
或者被访问的先后顺序
与TreeMap的有序性的区别
1）LinkedHashMap是根据元素增加或者访问的先后顺序进行排序
2）TreeMap是基于元素的固有顺序（借助Comparator或者Comparable确定）
3）如果是自然顺序或者自定义顺序的话treemap好，
如果需要输出顺序和输入顺序一致的话用LinkedHashMap好
如果需要输出顺序和输入顺序一致的话用LinkedHashMap好
Set
HashSet
基于HashMap实现，除了clone，writeObject和readObject必须自己实现，无序唯一
HashSet和hashMap区别
前者实现了set接口，后者是Map接口
前者存储对象，后者是键值对
前者用add新增，后者是put
前者是用hashcode和equals来判断对象是否相等，后面只用hashcode
前者效率慢，后者快
hashSet怎么检查重复
首先计算对象的hashcode然后匹配是否有其他的已经存入的hashcode与之匹配，若没有
那么假如，如果有，要么要通过equals来检查hashcode的对象是否真的相同。
那么假如，如果有，要么要通过equals来检查hashcode的对象是否真的相同。
LinkedHashSet
链表和hash表组成，由链表保证元素的排序。由hash表保证元素的唯一
TreeSet
有序，唯一，红黑树
0 条评论
下一页
