Java集合知识点
2022-03-21 15:26:26 73 举报
登录查看完整内容
Java集合知识点
作者其他创作
大纲/内容
代表了栈这种数据结构，继承自Vector
所以Stack是一种基于数组来实现的栈数据结构
Stack
Vector是一种类似于ArrayList（基于数组来实现的）数据结构，有序的集合
每次扩容默认是2倍
Vector
遍历HashMap，遍历的顺序，不是按照你插入的key-value的顺序来的。
遍历LinkedHashMap，是按照插入key-value对的顺序遍历出来的。
LinkedHashMap底层是基于链表来实现的，TreeMap是基于红黑树来实现顺序的
HashMap，LinkedHashMap，TreeMap区别
默认false，get一个key，或者是覆盖这个key的值，都不会改变他在链表里的顺序
是true的话，get一个key，或者是覆盖这个key的值，就会导致个key-value对顺序会在链表里改变，他会被挪动到链表的尾部去
final boolean accessOrder;
关键属性
基于HashMap实现
特点
LinkedHashMap
基于Map实现，底层基于红黑树，可以按照key的自然顺序来排序，和遍历。
TreeMap
Set都是直接基于Map来实现的，比如说HashSet就是基于HashMap来实现的，只有key是有值的，value都是null值，都是空的
里面的元素是无序的，没有重复的。
底层是有数组的，你可以在构造HashSet的时候就传入数组的大小，避免扩容的问题
HashSet
底层基于LinkedHashMap实现，有顺序的set，迭代LinkedHashSet的顺序跟你插入的顺序是一样的
LinkedHashSet.add()方法，底层会调用LinkedHashMap.put()方法，记住加入元素的顺序。遍历的时候，是从LinkedHashMap里遍历元素，直接遍历维护好的链表的。
LinkedHashSet
底层基于TreeMap来实现，默认根据插入元素的值排序的，而且可以定制Comparator，自己决定排序的算法和逻辑
TreeSet
java集合中，迭代器在迭代的时候，会发生ConcurrentModificationException并发修改的异常，这个机制就叫做fail fast
定义
modCount实现fail fast机制，各个集合都有这个modCount的概念，只要这个集合被修改了，那么就会对modCount++
modificationCount，修改次数，只要修改一次，就会更新这个，add、remove、set
获取和初始化一个迭代器的时候，里面的expectedModCount就会被初始化为modCount，然后就不会变了
迭代过程中，对集合进行add，remove等操作，expectedModCount!=modCount了，这时就会扔出ConcurrentModificationException()并发修改冲突异常。
java集合包下的类，都是非线程安全的，所以针对并发修改集合的问题设计了fail fast机制
原理
fail-fast机制
基于数组实现，直接根据内存地址定位某个元素，随机读性能很高。
查找数据快
数组来实现的话，要是往数组中间加一个元素，要把新增元素后面的元素全部往后面挪动一位，所以性能比较差
数组扩容的时候，会用老的大小 + 老的大小 >> 1（相当于除以2），也就是扩容大小1.5倍，再进行数组的拷贝。
所以不要频繁的往arraylist里头塞数据，导致频繁的数组扩容，避免扩容的时候，较差的性能影响了系统运行。
插入数据慢
默认构造函数会给数组一个默认初始大小10，创建的时候，最好给一个合理的初始化的数组的大小
使用
ArrayList
基于双向链表实现，需要从头开始遍历链表获取元素。
底层是一个双向队列的数据结构
如果数据在队列前半部分，从头开始遍历，在后半部分，从后开始遍历。
源码实现
查找数据慢
插入数据只需要挪动指针，不需要进行扩容和元素拷贝，速度很快。
插入数据快
LinkedList
时间复杂度O(n)
数组+链表
JDK1.8以前
时间复杂度在树化前是O(n)，树化之后是O(logN)
数组+链表+红黑树
JDK1.8以后
数组的元素是Node类型的，可组成单向链表。
数组
代表了一个key-value对
包含了key的hash值
有一个next的指针，指向下一个Node
子主题
数组中节点
有多少个key-value对
transient int size;
大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
数组默认初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认的负载因子，如果你在数组里的元素的个数达到了数组大小（16） * 负载因子（0.75f），默认是达到12个元素，就会进行数组的扩容
负载因子（扩容用）
capacity(默认数组的大小) * loadFactory
如果size达到threshold就开始扩容
int threshold;
扩容阈值
常用属性源码解析
对key，进行hashCode()运算，得到hash值
再用hash值对数组的长度进行取模，根据取模结果，将key-value对方在数组中的某个元素上
过程描述
对key进行hash获取对应的hash值，key、value传入到putVal()方法里面去，将key-value对儿根据其hash值找到对应的数组位置
通过hashCode()方法，直接获取hash值。
把32位的二进制的hash值，所有的bit往右侧右移了16位
将他的高16位和低16位进行一个异或运算，同时保留高16位和低16位的特征，减少hash冲突。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
hash(key)
获得key的hash值
&与操作，来实现取模的效果，位运算，性能很高
数组默认初始length，以及未来每次扩容的值，都是2的n次方，保证hash % 数组.length取模的一样的效果
(n - 1) & hash
对hash值进行取模运算
源码解析
hash值一样会导致他们放到同一个数组的索引的位置上去
或者多个key的hash值不一样，但对一个数组的length取模，获取到的这个数组的index位置，是一样的。
导致多个元素挂在数组同一索引位置上，成一个链表。
大量hash冲突会导致性能从O(1)变成O(n)
问题描述
JDK 1.8优化了HashMap的数据结构，如果一个链表长度超过8，会自动将链表转换为红黑树，查找性能，是O(logn)。
解决方法
hash冲突
红黑树是二叉查找树，左小右大，根据这个规则可以快速查找某个值
普通的二叉查找树，可能会出现不平衡的情况，导致查询性能变成O(n)，线性查询。
红黑树，红色和黑色两种节点，有很多条件限制，尽可能保证树是平衡的
如果插入节点的时候破坏了红黑树的规则和平衡，会自动重新平衡，变色（红 <-> 黑），旋转，左旋转，右旋转
红黑树特性
拓展知识
数据设置
JDK 1.8以后，扩容一定是2的倍数。
newCap = oldCap << 1
每个key-value对，都会基于key的hash值重新寻址找到新数组的新的位置
很多key在新数组的位置都不一样了，如果是之前冲突的这个key可能就会在新的数组里分布在不同的位置上了。
如果是一个链表里的元素的话，那么要么是直接放在新数组的原来的那个index，要么就是原来的index + oldCap
2倍扩容 + rehash
数据扩容
HashMap
Java集合
0 条评论
回复 删除
下一页
