

首页  思维导图  详情



Java核心知识点List, Set, Map

2022-03-16 06:58:40   0  举报





AI智能生成

Java集合类汇总

Java集合关系图

模版推荐

作者其他创作

大纲/内容

List

ArrayList

数据结构

动态数组

线程安全

不安全

插入和删除

插入和删除受元素位置影响，如果是add(e),就是添加到尾部， 时间复杂度为o(1)如果是指定位置插入的时间复杂度为O(n-i)

快速随机访问

支持，通过下标get(index)来迅速获取元素对象

内存空间占用

尾部需要预留一段空间，防止数组越界

LinkedList

数据结构

双向链表

线程安全

不安全

插入和删除

链表存储，所以插入和删除不受元素位置影响，都是近似O(1)

快速随机访问

链表不支持

内存空间占用

空间消耗比ArrayList更大，因为每个元素需要更多的 空间前指针和后指针及数据

Vector

线程安全

安全

原理

其实就是方法加入synchronized修饰的ArrayList

问题

Java中ArrayList的过程中，删除元素操作会发生修改异常？

循环遍历的时候，删除元素，首先会定位到元素位置删除， 然后复制数组到前移一位，遍历最后就会出现null，报错了

总结

非并发

写多读少

LinkedList

读多写少

ArrayList

并发

Vector

Map

HashMap

数据结构

JDK1.7

散列（数组+链表）

JDK1.8

散列（数组+链表）+红黑树

链表长度大于8就会转为红黑树

初始值大小是16，扩容因子是0.75，扩容是2的幂次方, 如果设置的初始值不是2的n次幂，hashmap会自动扩充2的n次方

线程安全

不安全

是否支持NULL键和值

支持

解决hash冲突

拉链法

我们先根据key获取Hash值，然后通过(数组length-1)和hash 获模获取当前数组存放的下标。若是链表上有值，那么追加到尾部， 然后取值的时候判断key==和equals

并发闭环问题

扩容方法会新建一个数组，复制原数组到新的数组，由于下标挂着链表， 扩容之后会导致环线链表的出现，JDK1.8已经解决了这个问题了。

HashTable

数据结构

初始化大小是11，每次扩容都是2n+1

线程安全

安全

内部方法基本上都是经过了synchronized修饰

是否支持NULL键和值

不支持

ConcurrentHashMap

1.8

取消了分段锁，而是采取了cas和synchronized来保证并发安全， synchronized只锁住当前链表或者红黑二叉树的首节点，只要hash 不冲突，就不会产生并发，效率很高

线程安全

安全

ConcurrentHashMap与HashTable的区别

底层数据结构：1.7分段数组+链表，1.8散列表红黑树，而hashtable一直是散列

实现线程安全的方式【重要】

ConcurrentHashMap

1.7

分段锁对整个桶进行切割，增加锁的粒度 如果不是访问一个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，要么是不为空返回，为空的话就加锁重读

remove

由于是final，所以删除节点的时候会删除某个节点然后那个节点之上都复制，然后最后一个节点指向被删除节点的下一个节点

resize

扩容只会对段扩容而非整个桶，跟HashMap不同的是，段是先判断 是否需要扩容再put，而HashMap是先put再判断是否需要扩容

size

先尝试不锁住segment的方式来统计segment的大小， 如果统计过程中，容器的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的对象是否真的相同。

LinkedHashSet

链表和hash表组成，由链表保证元素的顺序。由hash表保证元素的唯一。

TreeSet

有序、唯一、红黑树

 Collect

Get Started

python知识点

 Collect

Get Started

MyBatis 核心知识点梳理

 Collect

Get Started

Java面试核心知识点

 Collect

Get Started

Spring核心知识点详解





0 条评论

下一页