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
Map
HashMap
定义
基于Hash表的Map实现，属于key和value的键值对映射
特点
非线程安全
可以允许null键和null值
key不能重复，value可以重复
数据结构
数组+链表
数组+红黑树
hash冲突
多个不同的键映射到相同的桶中，例如这里的3和19
容量
默认容量
DEFAULT_INITIAL_CAPACITY = 1 << 4; //16
默认装载因子
loadFactor = 0.75
扩容条件
当添加元素个数 > 数组长度*loadFactor
JDK8优化后的动态扩容
旧容量与新容量，新数组每次扩容2倍
判断节点在新数组的位置
如果 node.hash & oldCap == 0，
则节点在新table数组中的下标不变。
则节点在新table数组中的下标不变。
如果 node.hash & oldCap != 0，
则节点在新table数组中的下标变为 oldI+ oldCap
（其中 oldI 是节点在旧table数组中的下标）
则节点在新table数组中的下标变为 oldI+ oldCap
（其中 oldI 是节点在旧table数组中的下标）
通过构造函数，传入的参数initialCapacity
不是2的幂次方，hashMap如何初始化
不是2的幂次方，hashMap如何初始化
HashMap参数构造初始化
重新计算容量，寻找比initialCapacity
大的第一个2的幂次方数
大的第一个2的幂次方数
自定义构造初始化为何阈值=数组容量
数据存储
计算键的哈希值
计算key的hashCode
计算hash值
key.hashCode()
h>>>16
key.hashCode() ^ h>>>16
这里为什么使用异或操作，而不是与或者非呢？
计算key在数组中的index值
计算index
为什么使用hash&(n-1)代替取模运算呢
插入前的容量检查
在插入之前，HashMap 会检查数组 table 是否已经初始化。
如果 table 为空或容量为零，会调用 resize() 方法进行初始化。
如果 table 为空或容量为零，会调用 resize() 方法进行初始化。
如果 size 超过 threshold（阈值），会触发 resize() 进行扩容。
扩容时，数组长度通常加倍，并重新计算每个元素的位置。
扩容时，数组长度通常加倍，并重新计算每个元素的位置。
处理哈希冲突
空位置插入
如果计算得到的位置索引是空的，HashMap 会直接在该位置插入新节点。
链表处理
如果该位置已有节点（发生哈希冲突），会通过链表方式进行处理。
遍历链表查看是否有与插入键相同的节点，若有则更新其值；
否则，将新节点追加到链表末尾。
遍历链表查看是否有与插入键相同的节点，若有则更新其值；
否则，将新节点追加到链表末尾。
红黑树优化
如果链表长度超过一定阈值（默认8），会将链表转换为红黑树，以提高查找和插入效率。
扩容检查
在插入新节点后，HashMap 会增加 size 的计数，并再次检查是否需要扩容。
如果当前大小超过阈值，会触发 resize() 方法进行扩容，并重新分配所有节点的位置。
如果当前大小超过阈值，会触发 resize() 方法进行扩容，并重新分配所有节点的位置。
返回值
如果插入的键已经存在，put() 方法会返回旧的值；如果是新的键值对插入，返回 null。
链表树化
目的：处理hashMap中单个数组位置存储的链表元素过多的问题
触发条件
链表节点个数 >= 8
table数组大小 >= 64
树化过程
从链表转化为红黑树
时间复杂度
链表：O(n)
红黑树：O（log n）
代价
树化过程耗时较多
红黑树占用空间更大
避免频繁链表树化
table数组长度 < 64 时，触发动态扩容而非链表树化
通过扩容将长链表拆分为短链表
反树化
目的：红黑树中节点较少，转化回链表
触发条件
当红黑树中的节点数量为2-6
LinkedHashMap
特点
能实现快速的增删改查
容器内部有序遍历
继承自HashMap
结构
哈希表+双向有序链表
和HashMap的结构差异性，
多了before和next字段用于排序
多了before和next字段用于排序
HashMap的节点包含的字段
LinkedHashMap包含的字段
顺序结构
按照插入顺序
按照访问顺序
增删改查操作对链表排序的影响
插入顺序
仅put操作会影响链表排序
访问顺序
put操作是将当前元素放入到双向链表尾节点
get和修改操作都会将元素节点置于双向链表最后一位
LRU缓存
特点
LRU缓存会预设一个缓存大小。当缓存满了之后，
LRU缓存会优先淘汰访问时间最早的数据。
LRU缓存会优先淘汰访问时间最早的数据。
实现
继承LinkedHashMap实现LRU缓存
基于匿名内部类来实现
List
Queue
0 条评论
下一页
