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