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