Java集合框架JCF
2024-08-15 17:17:09 0 举报
AI智能生成
登录查看完整内容
Java集合框架JCF(Java Collections Framework)提供了一套统一、灵活的接口和类,用于在Java程序中操作和存储对象。这个框架的核心内容是:接口、实现类和算法。其中,接口是JCF的主要部分,如Collection、Map、List、Set、Queue、Deque等,它们定义了操作和存储对象的方式。实现类,如ArrayList、LinkedList、TreeMap、HashSet等,是接口的具体实现,具有不同的特性和性能。算法则是一些通用的方法,如排序、搜索、计数等,可以应用于不同的集合类型。JCF中所有的类都是继承自Object类,并且经常被定义为泛型,以增加类型安全和减少运行时错误。总的来说,JCF为Java程序员提供了一种强大且易于使用的机制来操作和存储对象。
作者其他创作
大纲/内容
Set
基于Hash表的Map实现,属于key和value的键值对映射
定义
非线程安全
可以允许null键和null值
key不能重复,value可以重复
特点
数组+链表
数组+红黑树
数据结构
多个不同的键映射到相同的桶中,例如这里的3和19
hash冲突
DEFAULT_INITIAL_CAPACITY = 1 << 4; //16
默认容量
loadFactor = 0.75
默认装载因子
当添加元素个数 > 数组长度*loadFactor
扩容条件
旧容量与新容量,新数组每次扩容2倍
如果 node.hash & oldCap == 0,则节点在新table数组中的下标不变。
如果 node.hash & oldCap != 0,则节点在新table数组中的下标变为 oldI+ oldCap(其中 oldI 是节点在旧table数组中的下标)
判断节点在新数组的位置
JDK8优化后的动态扩容
HashMap参数构造初始化
重新计算容量,寻找比initialCapacity大的第一个2的幂次方数
自定义构造初始化为何阈值=数组容量
通过构造函数,传入的参数initialCapacity不是2的幂次方,hashMap如何初始化
容量
计算key的hashCode
key.hashCode()
h>>>16
key.hashCode() ^ h>>>16
这里为什么使用异或操作,而不是与或者非呢?
计算hash值
计算键的哈希值
为什么使用hash&(n-1)代替取模运算呢
计算index
计算key在数组中的index值
在插入之前,HashMap 会检查数组 table 是否已经初始化。如果 table 为空或容量为零,会调用 resize() 方法进行初始化。
如果 size 超过 threshold(阈值),会触发 resize() 进行扩容。扩容时,数组长度通常加倍,并重新计算每个元素的位置。
插入前的容量检查
如果计算得到的位置索引是空的,HashMap 会直接在该位置插入新节点。
空位置插入
如果该位置已有节点(发生哈希冲突),会通过链表方式进行处理。遍历链表查看是否有与插入键相同的节点,若有则更新其值;否则,将新节点追加到链表末尾。
链表处理
如果链表长度超过一定阈值(默认8),会将链表转换为红黑树,以提高查找和插入效率。
红黑树优化
处理哈希冲突
在插入新节点后,HashMap 会增加 size 的计数,并再次检查是否需要扩容。如果当前大小超过阈值,会触发 resize() 方法进行扩容,并重新分配所有节点的位置。
扩容检查
如果插入的键已经存在,put() 方法会返回旧的值;如果是新的键值对插入,返回 null。
返回值
数据存储
目的:处理hashMap中单个数组位置存储的链表元素过多的问题
链表节点个数 >= 8
table数组大小 >= 64
触发条件
从链表转化为红黑树
链表:O(n)
红黑树:O(log n)
时间复杂度
树化过程
树化过程耗时较多
红黑树占用空间更大
代价
table数组长度 < 64 时,触发动态扩容而非链表树化
通过扩容将长链表拆分为短链表
避免频繁链表树化
链表树化
目的:红黑树中节点较少,转化回链表
当红黑树中的节点数量为2-6
反树化
HashMap
能实现快速的增删改查
容器内部有序遍历
继承自HashMap
哈希表+双向有序链表
HashMap的节点包含的字段
LinkedHashMap包含的字段
和HashMap的结构差异性,多了before和next字段用于排序
结构
按照插入顺序
按照访问顺序
顺序结构
仅put操作会影响链表排序
插入顺序
put操作是将当前元素放入到双向链表尾节点
get和修改操作都会将元素节点置于双向链表最后一位
访问顺序
增删改查操作对链表排序的影响
LRU缓存会预设一个缓存大小。当缓存满了之后,LRU缓存会优先淘汰访问时间最早的数据。
继承LinkedHashMap实现LRU缓存
基于匿名内部类来实现
实现
LRU缓存
LinkedHashMap
Map
List
Queue
JCF
0 条评论
回复 删除
下一页