03_集合
2021-08-17 20:08:31 3 举报AI智能生成
登录查看完整内容
详细总结了集合的一些知识，面试可以参考哦
作者其他创作
大纲/内容
元素有序，可以重复
动态数组，链表实现
底层基于数组实现
数组元素长度固定
内存空间连续
基本原理
优点：基于数组实现，适合随机读取数组某个索引位置元素，性能很好
缺点：频繁插入数据，会导致数组扩容，元素移动，性能较差
优缺点
int DEFAULT_CAPACITY = 10
Object[] EMPTY_ELEMENTDATA = {}
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
Object[] elementData
数组中存放元素的个数
int size
属性
传入初始容量，如果大于0就初始化elementData为对应大小，如果等于0就使用EMPTY_ELEMENTDATA空数组，如果小于0抛出异常
ArrayList(int initialCapacity)
使用无参构造方法，初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组，会在添加第一个元素的时候扩容为默认的大小，即10
ArrayList()
构造方法
添加一个元素到末尾，平均时间复杂度为O(1)
第一步，检查是否需要扩容
第二步，把元素插入到数组尾部，同时，size++
add(E e)方法
添加元素到指定位置，平均时间复杂度为O(n)
第一步，检查索引是否越界
第二步，检查是否需要扩容
第三步，把 index 索引位置及其之后的元素都往后移动一位
第四步，在 index 索引位置插入 element 元素
第五步，size++
更新指定索引位置的元素，时间复杂度为O(1)
第一步，检查索引是否越界，这里只检查是否越上界，如果越上界抛出 IndexOutOfBoundsException 异常
第二步，返回索引位置处的元素
第三步，更新索引位置元素为新值
第四步，返回旧的索引位置元素
获取指定索引位置的元素，时间复杂度为O(1)
get(int index)方法
删除指定索引位置的元素，时间复杂度为O(n)
第二步，获取指定索引位置的元素
第三步，如果删除的元素不是最后一位，则将index之后的元素往前移动一位
第四步，将最后一个位置的元素置为null，方便GC回收
第五步，返回删除的元素
值得注意的是，ArrayList删除元素的时候没有缩容操作
remove(int index)方法
核心方法
如果 elementData 等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 则初始化容量大小为 DEFAULT_CAPACITY
新容量是老容量的1.5倍（oldCapacity + (oldCapacity >> 1)），如果加了这么多容量发现比需要的容量还小，则以需要的容量为准
创建新容量的数组并把老数组拷贝到新数组
数组扩容
元素移动
基于数组，最大的问题就是不要频繁的往里面灌入大量的数据，导致频繁的数组的扩容，新老数组元素的拷贝，中间位置插入元素，删除元素，会导致大量元素的移动，性能很差；随机获取一个元素，性能极高；
应用场景
ArrayList
底层基于双向链表实现
内存空间不连续
可以作为队列或者栈来使用
非常适合频繁插入、删除元素，性能很高
随机读取某个位置元素，性能很差，需要遍历链表
Node<E> first
Node<E> last
Node节点
双向链表
无界队列
LinkedList()
时间复杂度是O(1)
头部添加元素
尾部添加元素
需要使用node(int index) 这个方法，对链表进行遍历
时间复杂度为O(n)
通过比较 index 和 (size >> 1) 的大小，如果在前半部分，就会从头部开始遍历，如果在后半部分，就会从尾部开始遍历
中间位置添加元素
添加元素
获取头部元素
获取尾部元素
获取中间位置的元素
获取元素
删除头部元素
删除尾部元素
删除中间位置元素
删除元素
基于链表实现，所以不会出现任何大量元素的移动，也不会出现数组的扩容，插入、获取、删除都可以从对头、队尾来实现，可以作为队列使用
LinkedList
Vector底层实现和ArrayList很相似
int elementCount
动态扩容容量
int capacityIncrement
指定初始容量和每次动态扩容容量两个参数
不指定动态扩容容量，如果动态扩容容量为0，它会走默认的扩容逻辑
Vector(int initialCapacity)
如果初始化容量也不指定，初始化容量默认为10
Vector()
添加元素的原理也很简单，和ArrayList 几乎一样，不同的是Vector每次扩容是默认2倍扩容，ArrayList 是1.5倍扩容
每个添加元素方法都有 synchronized 修饰，所以添加元素保证并发安全，但是锁力度比较粗，所以实际业务中用的非常少
获取元素的方法也有 synchronized 修饰，所以获取元素保证并发安全，实际业务中用的非常少
删除元素的方法也有 synchronized 修饰，所以删除元素保证并发安全，实际业务中用的非常少
Vector
堆栈是一种先进后出的队列，常见的操作就是 pop (出栈) 和 push（入栈）
Stack 继承 Vector
入栈操作，把元素压到栈的顶部
push(E item)
出栈操作，把栈顶元素删除
pop()
取出栈顶元素但是不删除
peek()
判断栈是否为空
empty()
堆栈中搜索指定元素
int search(Object o)
Stack
List
HashMap 采用key/value存储结构，每个key对应唯一的value
查询和修改的速度都很快，能达到O(1)的平均时间复杂度，非线程安全的，且不保证元素存储的顺序
简介
JDK 1.8中，HashMap 的实现采用了（数组 + 链表 + 红黑树）的复杂结构
添加元素时，根据元素的hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素，则把元素以链表的形式放置在链表的尾部
当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则会把链表转化为红黑树，从而提高效率
数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率
存储结构
数组默认的初始容量为16
int DEFAULT_INITIAL_CAPACITY = 1 << 4
数组最大的容量为2的30次方
int MAXIMUM_CAPACITY = 1 << 30
默认的装载因子为0.75
float DEFAULT_LOAD_FACTOR = 0.75f
当一个桶中的元素个数大于等于8时进行树化
int TREEIFY_THRESHOLD = 8
当一个桶中的元素个数小于等于6时把树转化为链表
int UNTREEIFY_THRESHOLD = 6
当桶的个数达到64的时候才进行树化
int MIN_TREEIFY_CAPACITY = 64
数组，又叫作桶（bucket）
元素的数量
装载因子，不建议修改，会影响扩容的速度
float loadFactor
表示当桶的使用数量达到多少时进行扩容，threshold = capacity * loadFactor
int threshold
1、容量为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化
size > threshold
2、装载因子用来计算容量达到多少时才进行扩容，默认装载因子为0.75
3、树化，当容量达到64且链表的长度达到8时进行树化，当链表的长度小于6时反树化
重点理解扩容和树化的时机
核心成员变量
空参构造方法，全部使用默认值
HashMap()
判断传入的初始容量和装载因子是否合法
计算扩容门槛，扩容门槛为传入的初始容量最近的2的n次方
HashMap(int initialCapacity)
代码实现
思想：计算好的hash值右移16位的结果与计算好的hash值进行异或运算作为真正的hash值，保留hash值高16位和低16的特征
结果：hash值的高低16位都可以参与后面索引位置的运算，降低冲突的概率
优化后的降低冲突概率的hash算法
思想：hash值与（n - 1）进行与运算，计算元素在哪个桶中(hash 寻址)
结果：hash值与（n - 1）进行与运算，性能更好
数组刚开始的初始值，以及未来每次扩容的值，都是2的n次方，只要保证数组的大小是2的n次方，就可以保证hash值与（n - 1）进行与运算和直接hash值对数组长度取模计算元素对应数组索引位置index的效果一样
高性能hash寻址算法
hash值对数组长度取模计算元素对应数组索引位置index的性能不高，所以是基于hash值与（n-1）进行与运算来优化性能
JDK 1.8，扩容一定是2的倍数，保证说，每次扩容之后，重新rehash，元素的位置要么还是原来的那个index（5）的位置，要么是变成原来的index（5）+ oldCap（16） = 21的位置
高性能rehash算法
几处优化
第一步，计算key的hash值
第二步，如果桶（数组）数量为0，则初始化桶，无参构造函数会使用默认初始容量，默认负载因子
第三步，(n - 1) & hash 计算元素在哪个桶中(hash 寻址)，也就是元素在数组中的index位置
第一种情况，如果这个桶中还没有数据，则创建一个节点放在桶中的第一个位置
第二种情况，如果桶中第一个位置的元素的key和插入元素的key相同，则判断是否需要替换旧值，并直接返回旧值
第三种情况，如果桶中元素是一棵红黑树，则在红黑树中插入一个节点
如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
树化的条件：链表的长度大于等于8，同时，数组的长度大于64
树化的过程：先是把链表转成TreeNode组成的双向链表，然后将双向链表转成一棵红黑树
树化的效果：优化性能，链表和红黑树的时间复杂度
如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化，链表转成红黑树
第四种情况，则遍历桶对应的链表查找key是否存在于链表中
如果这个桶中已经存在元素
第四步，插入元素
第五步，插入元素成功，数组数量加1，并判断是否需要扩容
底层是基于数组实现，存在扩容问题
扩容原理非常简单，2倍扩容
扩容的过程：JDK 1.7，重新rehash，基于key的hash值对数组长度取模进行重新计算，重新在新的数组里找到新的位置，很多key在新数组的位置都不一样，之前冲突的key，现在可能就分布在新数组不同的位置，这里具体看下JDK 1.8对rehash的优化
第二步，(n - 1) & hash 计算元素在哪个桶中(hash 寻址)，也就是元素在数组中的index位置
第一种情况，如果当前位置元素的hash值和要获取元素的hash值一样，并且key也相同，匹配元素
第二种情况，如果当前桶位置是一棵红黑树，遍历红黑树，直至匹配元素
第三种情况，如果当前桶位置是一个链表，遍历链表，直至匹配元素
否则
第三步，匹配元素
第四步，返回元素key对应的value值
get(Object key)
HashMap
对于HashMap来说，如果遍历HashMap，遍历的结果，不会按照插入key-value元素的顺序进行遍历
LinkedHashMap是HashMap的子类，会记录插入key-value元素的顺序，可以实现顺序遍历
底层基于链表实现，内部维护一个双向链表，迭代遍历的时候，会从链表头部顺序遍历
新增元素
默认情况下，覆盖元素不会改变元素在双向链表的顺序
如果需要改变元素在双向链表中的顺序，可以将accessOrder参数设置为true，保证说每次覆盖元素都会把元素移动到双向链表的尾部
覆盖元素
原理同覆盖元素
将元素从内部双向链表中移除
LinkedHashMap
底层基于红黑树实现，自己实现的一个数据结构
TreeMap会按照key的大小顺序进行排序，可以定制Comparator，自己实现排序的算法
TreeMap
CurrentHashMap
(key/value) 的映射结构，Map 中的元素是一个 key 只能对应一个 value，不能存在重复的key
Map
基于HashMap实现
元素是无序的，key不能重复，正好可以直接使用HashMap，HashSet内部维护了一个HashMap
HashSet
基于LInkedHashMap实现
保证元素的顺序按照插入的顺序，key不能重复，正好可以直接使用LinkedHashMap，LinkedHashSet内部维护了一个LinkedHashMap
LinkedHashSet
基于TreeMap实现
保证元素的顺序是按照元素的值来排序，可以定制Comparator，正好可以直接使用TreeMap，TreeSet内部维护了一个TreeMap
TreeSet
元素不能重复
Set
各自的优缺点以及适用场景，结合项目
各个操作的原理
数组扩容的原理
元素移动的原理
ArrayList源码剖析
双向链表的数据结构
画图剖析指针的移动原理
LinkedList源码剖析
ArrayList和Linked List的区别
手写ArrayList
遍历链表
手写LinkedList
聊聊Vector和Stack
聊聊 1.8 对HashMap做了哪些优化
1、聊聊hash算法的优化，为什么要高位和低位做异或运算
2、聊聊hash寻址的优化，为什么是hash值和数组.length-1进行与运算
3、聊聊hash冲突的优化，链表转红黑树（树化）的时机，带来了什么好处
4、聊聊扩容机制的优化，其实就是重新寻址（rehash）的优化，hash & （n -1），判断二进制结果中是否多了一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index + oldCap
聊聊HashMap的底层原理
聊聊LinkedHashMap的底层实现原理
聊聊TreeMap的底层实现原理
Set的原理很简单，就是基于Map来实现，元素放入key，value都是一个空对象
聊聊HashSet、LinkedHashSet、TreeSet
聊聊Set的原理
迭代器应对多线程并发修改
感知到其它线程修改集合，迭代过程会快速失败，抛出ConcurrentModificationException异常
实现原理：内部维护modCount变量，集合被修改，都会改变这个变量的值，迭代器初始化过程中会初始化expectedModCount这个变量，通过expectedModCount和modCount这两个变量值的比较，来判断是不是遍历过程有线程修改集合
聊聊fail_fast机制
面试题精选
Java集合
收藏
收藏
0 条评论
回复 删除
下一页
