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