面试知识点-Java集合类
2021-10-11 18:35:51 606 举报AI智能生成
java集合类知识点
作者其他创作
大纲/内容
Collection
List
ArrayList
底层实现
动态数组
能够实现随机存取
实现了RandomAccess接口
fail-fast机制
在使用迭代器遍历list时，如果modCount和expectedCount不匹配，就会直接抛出异常
modCount在AbstractList中定义
使用迭代器自带的remove()函数的时候，如果删除了list中元素，不会出现fail-fast,因为迭代器会调整modCount和expectedCount值
自定义了序列化方法
因为arrayList的底层数组中，可能存在值为null的元素，序列化这些元素是没有意义的，因此自定义了序列化方法，只序列化数组中非null的元素
通过readObject()和writeObject()方法实现
源码实现
扩容：capacity=1.5*capacity
通过Arrays.copyOf()
System.copyOf()
每次扩容的时候，都会传入一个minCapacity,即扩容之后的数组长度，对于add方法，是原size+1,对于addAll方法，是size+newSize,如果原数组长度*1.5仍不能存放所需的元素，那么就会直接令数组长度为minCapacity
ArrayList是插入前扩容,扩容逻辑为 ensureCapacityInternal()--->ensureExplicitCapacity()---->grow()
LinkedList
底层实现
双向链表
常用api
add
offer
remove
适合插入删除多的场合
CopyOnWriteArrayList
和ArrayList基本一模一样，但它是线程安全的
任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，这样就不会影响COWIterator中的数据了，不会抛ConcurrentModificationException异常(对set,add没有作用，因为set,add本来就要加锁)，修改完成之后改变原有数据的引用即可。
读操作不加锁，写操作加锁，在进行add,set等操作时，会通过ReentrantLock进行加锁
适合多读少写的场景
缺点
1.复制的数组会消耗内存
2.不能读取实时性的数据
3.会产生大量的对象
Set
HashSet
底层是数组+链表+红黑树
基于HashMap实现
所有元素的value值都是一个static final Object
hashSet的存储是无序的
因为HashSet是根据对象的hashCode，进行计算后存储的
最后一个构造函数，为包访问权限是不对外公开，主要是为了支持LinkedHashSet
HashSet(int initialCapacity, float loadFactor, boolean dummy)
多了一个dummy变量
TreeSet
基于TreeMap实现
add()时，value值都是一个static final Object对象,因此当key相等时就会覆盖，也实现了没有重复元素的问题
LinkedHashSet
基于LinkHashMap实现
Map
HashMap
底层实现
1.7 数组+链表
数组的优点是访问速度快，但是插入删除操作慢
因为数组在内存中是连续存放的，因此存取很快
链表的优点是插入删除速度快，但是访问速度慢
由于链表不是连续存放的，因此插入删除时，只需要修改前后指针的指向即可，不需要移动元素位置
1.8 数组+链表+红黑树
拉链法由头插法改为了尾插法
因为头插法在多线程的时候可能会导致死循环
链表长度大于8的时候转化为红黑树
红黑树的时间复杂度为logn,线性表查找的平均时间复杂度为n/2,因此在链表长度为8时进行转化效率最高
红黑树的转化也是比较消耗性能的
链表个数超过8则链表转换成树结构，链表个数小于6则树结构转换成链表
特点
存取的时间复杂度为O(1)
源码分析
put()
1.判断key是否为null，如果为null，调用putlForNullKey，将key插入到数组下标为0的位置
2.调用hash()方法计算key的hashcode，得到hash值
3.调用indexFor()方法进行取模运算，得到元素的下标位置
1.indexFor方法为：h&(length - 1)
2.使用与运算，计算速度更快，因为二进制运算比十进制运算效率更高(十进制运算还需要将二进制转化为十进制)
3.length之所以要设定为2次幂，就是为了这个indexFor方法服务
4.可以让散列更加均匀，length-1的最后一位为1，因此进行与运算时，可以散列到奇数和偶数的下标位置，如果对length直接取模，由于length为2次幂，所以最后一位一定为0，所以与运算的结果一定是偶数，这也就导致奇数下标的位置不能被散列到。
4.依次和该下标位置上的链表中的node节点比较key是否相等
e.hash == hash && ((k = e.key) == key || key.equals(k))
首先判断e.hash==hash是因为不同的key值也可能被散列到同一个位置，因此首先判断hash值，如果不相等则两个key肯定不等
如果相等，再通过==和equals比较是否相等，之所以要先判断hash值是否相等，是因为equal()很耗性能，因此先判断hash值能够提高效率
重写了hashcode()方法就必须重写equals方法
5.如果相等，更新value值，如果不相等，使用头插法(1.7)/尾插法(1.8)将entry(1.7)/Node(1.8)插入到链表中
get()
和put()方法类似，获取到桶的下标，再在链表上查找key值，再获取key对应的value值
resize()
当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容
扩容时，令 capacity 为原来的两倍。
1.7时，需要new 一个新数组，并对旧数组上的所有元素进行indexFor()操作确定下标地址,这一步很费时，1.8时只需判断hash值的左边新增的那一位是否为1，即可判断此节点是留在原地lo还是移动去高位hi,如果为1，则移动去高位，否则不变
1.7时，扩容的时候可能出现死循环，1.8没有这个问题
构造方法
在第一次put()的时候，数组才初始化
数组的长度为大于指定值的最小二次幂
数组默认大小为16
多线程可能出现的问题
1.扩容时可能出现死循环
2.put的时候可能被失效/覆盖
线程A,B同时调用addEntry方法，同时获取到了相同的头节点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。
3.修改的时候可能被覆盖
线程A,B先后修改同一key值的value，会导致覆盖
4.put非null元素后get出来的却是null
扩容时调用的transfer方法，在获取数组的每个头节点的时候，在将e=头节点之后，都会将头节点置空，此时get可能导致获取到的值为0
ConcurrentHashMap
底层实现
1.7 segment数组+HashEntry数组(数组+链表)
chm由一个segment数组组成
segment
每个segment元素包含一个HashEntry数组，每个HashEntry包含一个链表
HashEntry大部分成员变量都为final
final k key
volatile V value
final int hash
final HashEntry<K,V> next
1.8 数组+链表+红黑树
源码分析
put()
基本流程
1.7 通过两次hash确定
第一次Hash定位到Segment
通过segmentFor()函数进行,计算方式也和indexFor()相同
SegmentMask
ssize-1
SegmentShift
32-sshift
ssize
是大于ConcurrentLevel的最小二次幂
第二次Hash定位到元素所在的链表的头部
定位方法和HashMap中的indexFor()相同
通过segment.lock加锁
1.8通过两次hash确定
通过CAS+synchronized加锁
1.如果没有hash冲突就直接通过CAS插入
2.如果有hash冲突或者CAS操作失败，说明存在并发情况，使用synchronized加锁
3.如果插入成功就调用addCount（）方法统计size，并且检查是否需要扩容
源码分析
1.ensureSegment
1.判断是否被其他线程初始化，这里使用了getObjectVolatile()方法
2.使用segment[0]的属性来初始化其他槽
3.使用while()循环，内部使用CAS操作，尝试初始化槽
2.使用segment[0]的属性来初始化其他槽
3.使用while()循环，内部使用CAS操作，尝试初始化槽
2.segment.put()
get()
get不需要加锁，因为HashEntry的value值设定为了volatile
如果get()到的是null值，则可能这个key，value对正在put的过程中，如果出现这种情况，那么就通过lock加锁来保证取出的value是完整的
resize()
构造函数
先根据ConcurrentLevel构造出Segment数组
Segment数组大小是不大于concurrentLevel的最大的2的指数
每个Segment中的HashEntry数组的大小都是大于指定大小的最小二次幂
每个hashEntry的大小为大于initialCapacity/concurrentLevel的最小二次幂
初始参数
initialCapacity(每个HashEntry的长度)
loadFactor：扩容因子
concurrencyLevel：并发度，指Segment数组的长度
remove
在定位到待删除元素的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去。尾结点指向e的下一个结点。e后面的结点不需要复制，它们可以重用。
因为HashEntry中的next是final，所以只能先把待删除之前的元素复制了再删除
size
size操作就是遍历了两次Segment，每次记录Segment的modCount值，然后将两次的modCount进行比较，如果相同，则表示期间没有发生过写入操作，就将原先遍历的结果返回，如果不相同，就需要将所有的Segment都锁住，然后一个一个遍历了，
HashTable
HashTable是线程安全的，因为所有方法上都加了synchronized关键字。
HashTable的key和value都不可以为null。
扩容时，capacity=2*capacity+1
数组默认大小为11
查找下标时，没有使用hash&length-1，而是直接进行计算的
TreeMap
底层实现为红黑树
能够保证树总是平衡的，如果插入删除导致树不平衡，会自动进行调整
变色
左旋
右旋
查找的平均时间复杂度为O(logN)
主要规则
1.每个节点或者是黑色，或者是红色。
2.根节点是黑色
3.叶子节点为黑色
4.如果一个节点是红色的，则它的子节点必须是黑色的
5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
TreeMap是一个有序的key-value集合，基于红黑树实现。该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序
接口实现
NavigableMap
是SortedMap接口的子接口，在其基础上扩展了一些方法，例如floorEntry，lowEntry,ceilingEntry等
为了防止外部修改Entry，使用了ExportEntry修饰floorEntry等方法
SortedMap
定义按照key排序的Map结构，能够令Map按照key的自然顺序或者构造器顺序进行排序。
Entry
包含了left，right，parent节点
LinkedHashMap
底层是数组+链表+红黑树+双向链表
同时使用一个额外的双向链表来维护链表的访问顺序
维护链表顺序和访问顺序
Node节点额外增加了before和after指针，用于维护链表的访问顺序
next指针用来维护链表顺序
LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在元素被访问后改变其在双向链表中的位置。
当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值false时，recordAccess方法什么也不会做。
LRU实现
插入数据后对调用afterNodeInsertion，afterNodeInsertion()方法中会调用removeEldestEntry，如果removeEldestEntry(first)返回true，按照LRU策略，那么会删除头节点(注意这里删除的是头节点！！！所以每次访问元素或者插入元素之后都要将该元素放到链表末尾)。这个也是实现LRU的关键点！！！！！
0 条评论
下一页
