首页  思维导图  详情

Java集合框架整理

2019-07-30 20:52:08   72  举报





AI智能生成

java集合整理

java

Java集合

作者其他创作

大纲/内容

接口

抽象类

类

List

Queue

Set

ArrayList

基本特征

排列有序，可重复

底层使用数组

查询速度快，增删慢

线程不安全

当熔料不够时，容量以1.5倍增加

底层

底层实现

动态数组

能够实现随机存取

实现了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()

初始化时初始化容器大小为10

Collection

LinkedList

底层

底层实现

双向链表

底层实现

双向链表

适合插入删除多的场合

基本特征

排列有序，可重复

底层使用双向循环链表数据结构

查询速度慢，增删快，add()和remove()方法快

线程不安全

Deque

SortedSet

NavigableSet

TreeSet

底层

基于TreeMap实现

add()时，value值都是一个static final Object对象,因此当key相等时就会覆盖，也实现了没有重复元素的问题

基本特征

排列无序列，不可重复

底层使用二叉树实现

排序存储

内部是TreeMap的SortedSet

AbstractCollection

AbstractList

HashSet

底层

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

基于HashMap实现

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

hashSet的存储是无序的

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

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

HashSet(int initialCapacity, float loadFactor, boolean dummy)

多了一个dummy变量

基本特征

排列无序，不可重复

底层使用Hash表实现

存储速度快

内部时HashMap

AbstractSet

LinkedHashSet

采用Hash表存储，并用双向链表记录插入顺序

内部是LinkedHashMap

ArrayDeque

Vector

配列有序，可重复

底层使用数组

查询速度快，增删慢

线程安全，效率低

当容量不够时，Vector默认扩展一倍容量

Stack

Map

SortedMap

AbstractMap

ConcurrentMap

HashTable

底层

HashTable是线程安全的，因为所有方法上都加了synchronized关键字。

HashTable的key和value都不可以为null。

扩容时，capacity=2*capacity+1

数组默认大小为11

查找下标时，没有使用hash&length-1，而是直接进行计算的

基本特征

键不可重复，值可重复

底层哈希表

线程安全

key、value都不能是null

Dictionary

Properties

NavigableMap

IdentityHashMap

WeakHashMap

HashMap

底层

底层实现

1.7 数组+链表

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

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

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

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

1.8 数组+链表+红黑树

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

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

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

红黑树的时间复杂度为logn,线性表查找的平均时间复杂度为n/2,因此在链表长度为8时进行转化效率最高

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

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

特点

存取的时间复杂度为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

底层

键不可重复，值可以重复

底层哈希表

线程不安全

允许key为null，value也可以为null

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节点

TreeMap

键不可重复，值可重复

底层二叉树

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的关键点！！！！！

类

RandomAccess

Collections

Arraays

工具类

CopyOnWriteArrayList

底层

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

任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，这样就不会影响COWIterator中的数据了，不会抛ConcurrentModificationException异常(对set,add没有作用，因为set,add本来就要加锁)，修改完成之后改变原有数据的引用即可。

读操作不加锁，写操作加锁，在进行add,set等操作时，会通过ReentrantLock进行加锁

适合多读少写的场景

缺点

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

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

3.会产生大量的对象

ConcurrentHashMap

底层实现

1.7 segment数组+HashEntry数组(数组+链表)

chm由一个segment数组组成

segment

每个segment元素包含一个HashEntry数组，每个HashEntry包含一个链表