java集合思维导图
2021-08-07 14:27:50 42 举报AI智能生成
java集合思维导图总结
作者其他创作
大纲/内容
概述
存储引用类型的变量容器
每一个对象作为一个元素存在
提供的集合类位于java.util包中
数组和集合区别
长度
数组固定
集合会改变
内容区别
数组存储同一类型
集合不一定
使用方式
集合有提供的各种方法
基础数据结构
数组
内存连续
大小固定，查找迅速，增删复杂
容易产生碎片
链表
内存地址不连续
动态调整
增删迅速，查找较慢
不会造成碎片化
继承关系
Collection
List
ArrayList
Vector
Stack
LinkedList
Set
HashSet
LinkedHashSet
TreeSet
Map
HashMap
LinkedHashMap
Properties
HashTable
TreeMap
Collection
List
ArrayList
底层实现：数组
线程不安全
扩容机制
无参构造
初始化数组为0
第一次添加扩容到10
之后1.5倍扩容
有参构造
初始化为指定容量大小
不够时，1.5倍扩容
应用
适合查询
增删不适合
Vector
底层实现：数组
方法由synchronized的修饰，线程安全
扩容机制
无参构造
初始化为10
之后2倍扩容
有参构造，之后2倍扩容
应用
多线程
适合查询
增删不适合
LinkedList
底层实现：双向链表
线程不安全
Stack
vector的子类，底层实现和vector一样
pop方法会直接移除最后一个元素
Set
HashSet
底层实现：hashMap，key为set的元素，value为空的object对象
可以存放null值，只能有一个
LinkedHashSet
底层实现LinkedHashMap
HashSet的子类
数组+双向链表
TreeSet
底层实现TreeMap
Map
HashMap
特点
线程不安全
插入慢，查询效率高
底层实现
JDK1.7
数组+链表
JDK1.8
数组+链表+红黑树
扩容机制
第一次添加：
哈希桶初始化为16
负载因子默认值为0.75
哈希桶初始化为16
负载因子默认值为0.75
之后添加：
哈希桶每次2倍扩容
哈希桶每次2倍扩容
什么时候链表会变成红黑树
当一个桶中的元素>8
并且哈希桶桶的个数>=64
并且哈希桶桶的个数>=64
什么时候红黑树会变成链表
当红黑树中的节点<=6时
会转换成链表
会转换成链表
调用位置
移除节点时会判断是否需要转换成链表
扩容时，移动到新的桶时会判断是否需要转换成链表
hashMap的死循环问题
JDK8-在多线程的情况下，红黑树的节点r=r.parent.parent
所以查找根节点死循环
所以查找根节点死循环
JDK7-多线程情况下，两个HashMap扩容
最后会导致链成循环的，造成死循环
最后会导致链成循环的，造成死循环
HashTable
底层结构
数组+链表
线程安全
通过方法上添加synchronized实现
扩容机制
初始化容量为11
之后每次table扩容为原来的2n+1
LinkedHashMap
底层结构
HashMap+LinkedList
哈希+双向链表
集合有序
非线程安全
Properties
hashTable的子类，线程安全
经常读取配置文件等
TreeMap
有序集合，通过红黑树实现
key必须实现comparable接口，否则会抛出异常
ConCurrentHashMap
jdk1.7
通过分段锁+可重入所实现线程安全
结构为：数组+链表
结构
- 一个segments里面是一个小的hashMap，内置自己的计数器
- 每一个线程对hashmap操作，会锁住segments，所以叫做分段锁
并发度一定后，会对segments内置的小HashMap进行扩容
内部机制
有多少并发量，创建多少个segments
使用可重入锁对segments上锁
jdk1.8
通过volatile+synchronized锁节点+CAS操作实现线程安全
底层结构：数组+链表+红黑树
内部结构
- 添加元素通过对每一个桶的头结点加锁
- 桶的个数，说明了他的并发量
- 计数，通过baseCount+counterCells数组实现——为了提供并发量
0 条评论
下一页
为你推荐
查看更多
