java集合框架
2021-03-18 21:27:48 36 举报AI智能生成
java集合框架
作者其他创作
大纲/内容
底层接口: Collection, Map, Iterator
Collection
集合类的根接口，Java中没有提供这个接口的直接的实现类
List和Set 都是Collection的子接口
Iterator
所有的集合类都实现了Iterator接口，用于遍历集合中元素
hasNext()是否还有下一个元素
next()返回下一个元素
remove()删除当前元素
Map
Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的
LIST
ArrayList
结构
数组
默认初始数量为 10 (初始化时, 为空数组. 当第一次add时, 才扩容为10)
扩容
每次扩容1.5倍
每次扩容会生成新的数组
add -> 数组长度是否大于容量 -> 扩容
源码解读
add
remove
set
get
LinkedList
结构
双向链表
没有初始化大小，也没有扩容的机制
Vector
结构
数组
默认初始数量为 10
扩容
每次扩容1.5倍
每次扩容会生成新的数组
synchronized 可重入锁 (增删查改)
查加锁, 避免A线程读一半时, CPU被B线程add操作占用, 导致A线程数据不可重复读
CopyOnWriteArrayList
结构
数组
ReentrantLock 可重入锁 (增删改)
SET
HashSet
基于HashMap实现
add时, HashMap为(key, null对象常量)
LinkedHashSet
基于LinkedHashMap实现
TreeSet
基于TreeMap实现
MAP
HashMap
结构
数组+链表/红黑树
初始数量默认为16
装载因子默认为0.75
源码解读
```
table变量
HashMap的底层数据结构，是Node类的实体数组，用于保存key-value对
size变量
Map中的K-V对的数量
capacity
并不是一个成员变量，但却是一个必须要知道的概念，表示容量
threshold变量
临界值，当超出该值时，表示table表示该扩容了
threshod = capacity * loadFactor
threshod = capacity * loadFactor
loadFactor变量
装载因子, 默认为0.75
put
1. key的hash值 -> 数组table的位置i
2. 判断table是否初始化
否 -> resize扩容
3. 判断table[i]是否已有元素
否 -> 直接插入
4. 判断table[i]是否为TreeNode
是 -> 红黑树插入
否 -> 链表遍历插入
链表深度>8 -> 转换为红黑树
5. size是否大于临界值threshold -> resize扩容
resize扩容
1. newsize = oldsize*2, 容量为2的幂次方
2. 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置( index = hash & (tab.length – 1) )
优化: 若知道HashMap的K-V个数size, 初始化时可以 new HashMap(size/loadFactor >> 1)
Hashtable
结构
数组+链表
初始数量默认为11
装载因子默认为0.75
put
类似HashMap
rehash扩容
1. newsize = oldsize*2+1
2. 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置( index = (hash & 0x7FFFFFFF) % tab.length )
锁
synchronized
LinkedHashMap
基于HashMap实现
双向链表
维护链表节点--重写newNode
ConcurrentHashMap
结构
分段的数组+链表
扩容
段内扩容, 不会对整个Map进行扩容
锁
分段锁
1. Hashtable的synchronized是针对整张Hash表的，ConcurrentHashMap允许多个修改操作并发进行
2. 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
TreeMap
结构
红黑树
容量方面没有限制
0 条评论
下一页
