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