Java核心知识点List, Set, Map
2022-03-16 06:58:40 0 举报AI智能生成
Java集合类汇总
作者其他创作
大纲/内容
List
ArrayList
数据结构
动态数组
线程安全
不安全
插入和删除
插入和删除受元素位置影响，如果是add(e),就是添加到尾部，
时间复杂度为o(1)如果是指定位置插入的时间复杂度为O(n-i)
时间复杂度为o(1)如果是指定位置插入的时间复杂度为O(n-i)
快速随机访问
支持，通过下标get(index)来迅速获取元素对象
内存空间占用
尾部需要预留一段空间，防止数组越界
LinkedList
数据结构
双向链表
线程安全
不安全
插入和删除
链表存储，所以插入和删除不受元素位置影响，都是近似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
获模获取当前数组存放的下标。若是链表上有值，那么追加到尾部，
然后取值的时候判断key==和equals
并发闭环问题
扩容方法会新建一个数组，复制原数组到新的数组，由于下标挂着链表，
扩容之后会导致环线链表的出现，JDK1.8已经解决了这个问题了。
扩容之后会导致环线链表的出现，JDK1.8已经解决了这个问题了。
HashTable
数据结构
初始化大小是11，每次扩容都是2n+1
线程安全
安全
内部方法基本上都是经过了synchronized修饰
是否支持NULL键和值
不支持
ConcurrentHashMap
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来保证，效率低下，多线程访问同一个同步方法，会导致阻塞或者轮询，竞争会愈发激烈
1.7
数据结构
分段锁segment，锁的粒度更加精细，
分段的数组+链表的形式
分段的数组+链表的形式
原理
put
1.二阶段hash，第一阶段是定位到那个segment，第二阶段是定位到那个entry
entry中，除了value，还有key，hash和next都是final修饰，意味着不能从中心或者尾部添加或者删除节点，一律添加到头部
通过count来统计段内的数据个数，只有新增和删除会修改这个值，每次都是在上述两个步骤的最后一步进行修改
get
get不需要加锁，采取volatile修饰共享变量这样每次get的时候都可以获取最新的结构更新由于
遍历不需要加锁的原因是因为next是final，要么是不为空返回，为空的话就加锁重读
遍历不需要加锁的原因是因为next是final，要么是不为空返回，为空的话就加锁重读
remove
由于是final，所以删除节点的时候会删除某个节点然后那个节点之上都复制，然后最后一个节点指向被删除节点的下一个节点
resize
扩容只会对段扩容而非整个桶，跟HashMap不同的是，段是先判断
是否需要扩容再put，而HashMap是先put再判断是否需要扩容
是否需要扩容再put，而HashMap是先put再判断是否需要扩容
size
先尝试不锁住segment的方式来统计segment的大小，
如果统计过程中，容器的count发生变化则采取加锁的方式
如果统计过程中，容器的count发生变化则采取加锁的方式
LinkedHashMap
数据结构
继承于HashMap,同时内部增加了一个链表，用来保证元素的顺序
是否有序
基于元素进入集合的顺序或者被访问的先后顺序
与TreeMap的有序性的区别
1). LinkedHashMap是根据元素增加或者访问的先后顺序进行排序
2). TreeMap是基于元素的固定顺序(借助Comparator或者Comparable确定)
3). 如果是自然顺序或者自定义顺序的话treemap好，如果需要输出顺序和输入顺序一致的话用LinkedHashMap好
TreeMap
数据结构
红黑树
一种特殊的AVL树
是否有序
有序
字典顺序来排序[升序]
我们可以通过对象中构造一个Comparator对象来定制排序
原理
put
1).构建二分搜索树
2). 构建红黑树
左旋
右旋
着色
deleteEntry
删除比较特殊，它不是直接删除，而是找到要删除节点子节点，然后用子节点来代替删除节点，这样就删除子节点即可，
简单的说就是把要删除的节点和它的左孩子的最右边的右孩子的最左边交换
简单的说就是把要删除的节点和它的左孩子的最右边的右孩子的最左边交换
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 条评论
下一页
