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