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