首页  思维导图  详情



 



JAVA集合

2020-11-10 18:37:17   0  举报





Java集合

模板推荐

作者其他创作

大纲/内容

Set

HashSet

基于HashMap实现，除了clone，writeObject和readObject必须自己实现，无序唯一

HashSet和hashMap区别

前者实现了set接口，后者是Map接口

前者存储对象，后者是键值对

前者用add新增，后者是put

前者是用hashcode和equals来判断对象是否相等，后面只用hashcode

前者效率慢，后者快

hashSet怎么检查重复

首先计算对象的hashcode然后匹配是否有其他的已经存入的hashcode与之匹配，若没有 那么假如，如果有，要么要通过equals来检查hashcode的对象是否真的相同。

LinkedHashSet

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

TreeSet

有序，唯一，红黑树

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.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的区别

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

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

ConcurrentHashMap

1.7

分段锁对整个桶进行切割，增加锁的粒度 如果不是访问同一个segment，就不存在竞争

1.8

Node数组+链表+红黑树，并发控制使用CAS与Synchronized

HashTable

使用synchronized来保证，效率低下，多线程访问同一个同步方法 会导致阻塞或者轮询，竞争会愈发激烈

线程安全

安全

TreeMap

数据结构

红黑树

一种特殊的AVL树

是否有序

有序

字典顺序来排序【升序】

我们可以通过往对象中构造 一个Comparator对象来定制排序

原理

put

1）构建二分搜索树

2）构建红黑树

左旋

右旋

着色

deleteEntry

删除比较特殊，他不是直接刪除，而是找到要刪除节点子节点， 然后用子节点来代替删除节点这样就删除子节点即可，简单的 说就是把要删除节点和他的左孩子的最右和右孩子的最左交换

LinkedHashMap

数据结构

继承于HashMap,同时内部增加了 一个链表，用来保证元素的顺序

是否有序

基于元素进入集合的顺序 或者被访问的先后顺序

与TreeMap的有序性的区别

1）LinkedHashMap是根据元素增加或者访问的先后顺序进行排序

2）TreeMap是基于元素的固有顺序（借助Comparator或者Comparable确定）

3）如果是自然顺序或者自定义顺序的话treemap好， 如果需要输出顺序和输入顺序一致的话用LinkedHashMap好

 Collect

Get Started

Java 容器（集合）

 Collect

Get Started

Java集合类

 Collect

Get Started

java集合思维导图

 Collect

Get Started

品牌集合页





0 条评论

下一页