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 条评论
回复 删除
下一页
