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