Java集合框架（1.8）
2019-10-30 13:17:33 0 举报AI智能生成
Java基本知识常用集合框架
作者其他创作
大纲/内容
Iterable
interface
interface
Collection
interface
interface
List
interface
interface
ArrayList
底层是基于数组来实现容量大小动态变化的。get效率高，非尾部的增删会带来元素的整体移动
插入时会判断数组容量是否足够，不够的话会进行扩容 扩容时重新申请新的内存空间，
并把就数组拷贝到新数组上去，非线程安全
并把就数组拷贝到新数组上去，非线程安全
int size;
实际元素个数
Object[] elementData;
数组存储 默认是空数组
DEFAULT_CAPACITY = 10;
初始容量大小为 10;一开始是空数组，第一次添加元素时容量扩大至 10 的。
Arrays.copyof() 拷贝数组
int newCapacity = oldCapacity + (oldCapacity >> 1);
可看出扩容因子子1.5
遍历用for 循环，效率高，用迭代器iterator 遍历会非常慢，因为做了很多安全检查但支持边遍历边remove
vector
很少用
线程安全，但性能低
增删改查很多方法都是synchronized 锁对象
扩容因子1
LinkedList
链表存储，不需要扩容
查找慢O{n),add remove 不需要移动节点，相对数组较快
CopyOnWriteArrayList
线程安全 读写分离
volatile Object[] array;
通过volatile 确保可见性和可序性
get，遍历等读操作不会占用锁
ReentrantLock lock = new ReentrantLock();
通过锁确保增删改
add remove 等增删改都是基于内存副本操作，先复制一份副本，在副本进行修改，修改后原数组指针指向副本，
确保读操作不会受影响,（此时内存有二份数组，二份数组一个读一个写互不影响）
确保读操作不会受影响,（此时内存有二份数组，二份数组一个读一个写互不影响）
缺点
占用内存 1 增删改操作都要复制一个数组出来
只能保证数据的最终一致性，不能保证数据的实时一致性。
比如线程A在迭代CopyOnWriteArrayList容器的数据。线程B在线程A迭代的间隙中将CopyOnWriteArrayList部分的数据修改了
(已经调用setArray()了)。但是线程A迭代出来的是原有的数据,跟数据库的幻读差不多
(已经调用setArray()了)。但是线程A迭代出来的是原有的数据,跟数据库的幻读差不多
MAP(散列表)
Interface
Interface
HashMap
数据结构
1.7 数组+链表
jdk1.8 数组+链表+红黑树
工作原理
Node[K,V] table
元素数组
键值对存储 每次读取插入删除会计算KEY的hash值,并通过哈希值计算对应数组的位置
hash 对应数组 位置 公式 (table.length - 1) & hashCode
如何解决哈希冲突
以1.8为例,会以链表或红黑树来保存多个node,
如果链表个数超过一定的门限,会转成红黑树存储,
如果红黑树的节点数小于门限,会转成链表
如果链表个数超过一定的门限,会转成红黑树存储,
如果红黑树的节点数小于门限,会转成链表
如何扩容
size
hashmap元素个数
length
table 数组 长度
默认填充因子
0.75
初始容量
默认16
数组的长度,通过计算都是2的幂数 ,
threshold
threshold=初始容量*默认填充因子
map的元素个数size > threshold 就会触发扩容 扩容的数组为原来length的2倍
扩容会重新申请新的数组,
并且把旧数组上元素重新计算hash值 添加到 新的数组上
并且把旧数组上元素重新计算hash值 添加到 新的数组上
如果可以预知要插入的数量,建议通过构造函数指定capacity的大小,
避免频繁扩容导致的性能损失
避免频繁扩容导致的性能损失
非线程安全
KEY value 允许null值 遍历是无序的
LinkedHashMap
保存着元素插入的顺序(插入有序性)，并且可以按照我们插入的顺序进行访问
数据结构
数组 + 单链表 + 红黑树 + 双链表
在hashmap的基础上用双链表保存元素之家的先后插入关系
遍历时是根据双链表进行遍历,跟hashmap不一样
IdentityHashMap
基本不用
允许key相同数据插入
HashTable
线程安全
key、value都不可以为null
底层数据结构及扩容原理跟HashTable差不多 扩容不需要2的n次方
增删改也是通过synchronized把整个对象锁住,效率不高
ConcurrentHashMap替代HashTable
ConcurrentHashMap
数据结构跟hashmap及扩容基本一样
数据结构
1.7 数组+链表
jdk1.8 数组+链表+红黑树
线程安全
1.7以前采用的分段锁,把数组切成多个段segment
1.8 采用NODE + CAS + synchronized
TreeMap
数据结构
基于红黑树实现
默认按照keys的自然排序排列
区别
HashMap 无序 LinkedHashMap 插入有序性 TreeMap 按Key自然排序
HashMap ConcurrentHashMap HashTable 数据结构基本一样 HashTable 的KEY,VALUE 不允许null
ConcurrentHashMap HashTable 线程安全,ConcurrentHashMap效率更高
如果只需要存储功能，使用HashMap与LinkedHashMap是一种更好的选择；
如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。
如果还需要保证统计性能或者需要对Key按照一定规则进行排序，那么使用TreeMap是一种更好的选择。
SET
interface
interface
HashSet
哈希表结构(底层HashMap)，主要利用HashMap的key来存储元素
基本就是HashMap的缩水版,因为没有value,只有key
TresSet
TresMap的缩水版
LinkedHashSet
LinkedHashMap的缩水版
0 条评论
下一页
