首页  思维导图  详情

Java集合类

2020-12-18 18:35:02   1  举报





AI智能生成

为你推荐

查看更多



java集合

作者其他创作

大纲/内容

集合类

Collection

List

ArrayList

底层实现

动态数组

能够实现随机存取

实现了RandomAccess接口

fail-fast机制

在使用迭代器遍历list时，如果modCount和expectedCount不匹配，就会直接抛出异常

modCount在AbstractList中定义

自定义了序列化方法

因为arrayList的底层数组中，可能存在值为null的元素，序列化这些元素是没有意义的，因此自定义了序列化方法，只序列化数组中非null的元素

通过readObject()和writeObject()方法实现

源码实现

扩容：capacity=1.5*capacity

通过Arrays.copyOf()

System.copyOf()

font color=\"#c41230\

LinkedList

双向链表

常用api

add

offer

remove

适合插入删除多的场合

CopyOnWriteArrayList

和ArrayList基本一模一样，但它是线程安全的

任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，font color=\"#c41230\

适合多读少写的场景

缺点

1.复制的数组会消耗内存

2.不能读取实时性的数据

3.会产生大量的对象

Set

HashSet

底层是数组+链表+红黑树

基于HashMap实现

所有元素的value值都是一个static final Object

hashSet的存储是无序的

因为HashSet是根据对象的hashCode，进行计算后存储的

最后一个构造函数，为包访问权限是不对外公开，主要是为了支持LinkedHashSet

多了一个dummy变量

TreeSet

基于TreeMap实现

LinkedHashSet

基于LinkHashMap实现

Map

HashMap

1.7 数组+链表

数组的优点是访问速度快，但是插入删除操作慢

因为数组在内存中是连续存放的，因此存取很快

链表的优点是插入删除速度快，但是访问速度慢

由于链表不是连续存放的，因此插入删除时，只需要修改前后指针的指向即可，不需要移动元素位置

特点

存取的时间复杂度为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时，扩容的时候可能出现死循环，1.8没有这个问题

构造方法

数组的长度为大于指定值的最小二次幂

在第一次put()的时候，数组才初始化

数组默认大小为16

多线程可能出现的问题

1.扩容时可能出现死循环

2.put的时候可能被失效/覆盖

3.修改的时候可能被覆盖

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

1.8 数组+链表+红黑树

基本流程

1.7 通过两次hash确定

第一次Hash定位到Segment

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.put()

get不需要加锁，因为HashEntry的value值设定为了volatile

如果get()到的是null值，则可能这个key，value对正在put的过程中，如果出现这种情况，那么就通过lock加锁来保证取出的value是完整的

构造函数

先根据ConcurrentLevel构造出Segment数组

Segment数组大小是不大于concurrentLevel的最大的2的指数

每个Segment中的HashEntry数组的大小都是大于指定大小的最小二次幂

每个hashEntry的大小为大于initialCapacity/concurrentLevel的最小二次幂

初始参数

initialCapacity(每个HashEntry的长度)

loadFactor：扩容因子

concurrencyLevel：并发度，指Segment数组的长度

在定位到待删除元素的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去。尾结点指向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

为了防止外部修改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的关键点！！！！！

1.8 数组+链表+红黑树

拉链法由头插法改为了尾插法

因为头插法在多线程的时候可能会导致死循环

链表长度大于8的时候转化为红黑树

红黑树的转化也是比较消耗性能的

链表个数超过8则链表转换成树结构，链表个数小于6则树结构转换成链表