首页  思维导图  详情

Java集合框架学习

2020-09-02 09:30:17   25  举报





AI智能生成

Java集合框架总结

Java

JDK

集合框架

思维导图

学习笔记

作者其他创作

大纲/内容

整体结构图

主要分为三类，list，map和set

@SuppressWarnings

让编译器忽略掉一些警告（在使用list时未参数化）

Collection接口

Lambda 之 Collection Stream

removeIf过滤

stream

stream()优点 无存储。stream不是一种数据结构，它只是某种数据源的一个视图，数据源可以是一个数组，Java容器或I/O channel等。 为函数式编程而生。对stream的任何修改都不会修改背后的数据源，比如对stream执行过滤操作并不会删除被过滤的元素，而是会产生一个不包含被过滤元素的新stream。 惰式执行。stream上的操作并不会立即执行，只有等到用户真正需要结果的时候才会执行。 可消费性。stream只能被“消费”一次，一旦遍历过就会失效，就像容器的迭代器那样，想要再次遍历必须重新生成。

spliterator

List子接口

AbstractList

既实现了 List 的期望 也继承了 AbstractCollection 的传统 还创建了内部的迭代器 Itr, ListItr 还有两个内部子类 SubList 和 RandomAccessSublist；

LIstIterator是一个更加强大的Iterator的子类型,它只能用于各种List类的访问,尽管Iterator只能向前移动,但是ListIterator可以双向移动,它还可以产生相对于迭代器在列表指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素. 你可以通过ListIterator()方法产生一个指向List开始处的ListIteraor,并且还可以通过调用ListIterator(n)方法创建一个一开始就指向索引列表n的元素处的ListIterator

第一个实现随机访问方法的集合类，但不支持添加和替换

ArrayList

size(), isEmpty(), get(), set() iterator(), ListIterator() 方法的时间复杂度都是 O(1) add() 添加操作的时间复杂度平均为 O(n) 其他所有操作的时间复杂度几乎都是 O(n)

支持 RandomAccess 的对象，遍历时使用 get 比迭代器更快。 由于 ArrayList 继承自 RandomAccess，而且它的迭代器都是基于 ArrayList 的方法和数组直接操作， 所以遍历时 get 的效率要 >= 迭代器。failfast的，并发要加锁

trimToSize()来去除预增长的多余容量，增长grow（）：oldCapacity + (oldCapacity >> 1)

一般这么实例化List list=new ArrayList()程序要尽量依赖于抽象，不依赖于具体。 从Java语法上，这种方式是使用接口引用指向具体实现。这样在更改接口实现时需要进行的改动很小

AbstractSequentialList

只支持按照次序访问是 List 接口的简化版实现

不支持 RandomAccess访问，使用迭代器效率较高

LinkedList

基于双端链表，添加/删除元素只会影响周围的两个节点，开销很低； 只能顺序遍历，无法按照索引获得元素，因此查询效率不高； 没有固定容量，不需要扩容； 需要更多的内存，如文章开头图片所示 LinkedList 每个节点中需要多存储前后节点的信息，占用空间更多些。

Vector

被称为线程安全的arraylist没有线程安全的需求，一般推荐使用 ArrayList，而不是 Vector，因为每次都要获取锁，效率太低。

扩容时增长数量，允许用户自己设置。如果这个值是 0 或者负数，扩容时会扩大 2 倍

Stack

除了 push()，剩下的方法都是同步的

官方推荐在使用栈时优先使用 Deque，而不是 Stack

AbstractCollection

子类必须实现这两个抽象方法 public abstract Iterator<E> iterator(); public abstract int size();

默认不支持添加单个元素，若调用add（E）会报错； 若子类是支持添加的需自己实现该方法

AbstractCollection 默认的构造函数是 protected 官方推荐每个子类都要新建一个无参数的构造方法

Set子接口

TreeSet

不能重复有序（红黑树基于TreeMap实现）

HashSet

不能重复无序；先计算hashcode若相等继续使用equals 进行比较.如果 equals为true 那么HashSet认为新加入的对象重复了,所以加入失败。如果equals 为false那么HashSet 认为新加入的对象没有重复.新元素可以存入.

Queue子接口

Dqueue子接口

todo

Map接口

KeySet,Values,Entry三种方式遍历 Map 的每个实现类都应该实现 2 个构造方法： 无参构造方法，用于创建一个空的 map 参数是 Map 的构造方法，用于创建一个包含参数内容的新 map

可以使用 Map 作为 Map 的值，但禁止使用 Map 作为 Map 的键。因为在这么复杂的 Map 中，equals() 方法和 hashCode() 比较难定义。 另一方面，你应该尽量避免使用“可变”的类作为 Map 的键。如果你将一个对象作为键值并保存在 Map 中，之后又改变了其状态，那么 Map 就会产生混乱，你所保存的值可能丢失。

AbstractMap

HashMap

元素是无序的，而且顺序会不定时改变

不是同步的

采用拉链法解决哈希冲突

key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法

允许空键，但放在第一个且只能有一个

插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）

遍历整个 Map 需要的时间与桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）

桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化,红黑树结构O(logn)

新初始化哈希表时，容量为默认容量，阈值为容量*加载因子 已有哈希表扩容时，容量、阈值均翻倍 如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构 复制给新哈希表中需要重新索引（rehash），这里采用的计算方法是 e.hash & (newCap - 1)，等价于 e.hash % newCap 结合扩容源码可以发现扩容的确开销很大，需要迭代所有的元素，rehash、赋值，还得保留原来的数据结构。 所以在使用的时候，最好在初始化的时候就指定好 HashMap 的长度，尽量避免频繁 resize()。

LinkedHashMap

HashMap和双向链表合二为一，是一个将所有Entry节点链入一个双向链表双向链表的HashMap

它的迭代顺序默认是插入顺序，也可以是访问顺序

IdentityHashMap

使用==来比较key是否重复，及比较对象在内存中的地址

实现不同于HashMap，虽然也是数组，不过IdentityHashMap中没有用到链表，解决冲突的方式是计算下一个有效索引，并且将数据key和value紧挨着存在map中，即table[i]=key，那么table[i+1]=value。

没有使用Object的hashCode方法，而是使用的System.identityHashCode方法，这是Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方式

TreeMap

有序的key-value集合，它是通过红黑树实现

根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序

适用于按自然顺序或自定义顺序遍历键，否则一般使用hashmap

TreeSet是基于它实现的

提供了 Map 的基本实现，若要实现一个不可变的Map只需要实现唯一的抽象方法 public abstract Set<Entry<K,V>> entrySet();

想要实现一个可变的 Map,我们需要在上述操作外，重写 put() 方法，因为默认不支持 put 操作，会抛出异常

WeakHashMap

WeakHashMap的键是“弱键”。在WeakHashMap中，当某个键不再正常使用时，会从WeakHashMap中被自动移除（会被垃圾回收）

如果在系统中需要一张很大的Map表，Map中的表项作为缓存使用（即使没能从该Map中取得相应的数据，系统也可以通过候选方案获取这些数据）虽然这样会消耗更多的时间，但是不影响系统的正常运行。 在这种场景下，使用WeakHashMap是最合适的。因为WeakHashMap会在系统内存范围内，保存所有表项，而一旦内存不够，在GC时，没有被引用的表项又会很快被清除掉，从而避免系统内存溢出。

如果存放在WeakHashMap中的key都存在强引用，那么WeakHashMap就会退化成HashMap

key为null时，放入的是NULL_KEY，即：private static final Object NULL_KEY = new Object()，是一个静态常量。static不会被gc

只有通过remove方法才能删除null键所关联的value，建议在使用WeakHashMap的时候尽量避免使用null作为键。

Predicate函数接口

Pattern.compile().asPredicate()将正则表达式转换为Predicate

Iterator

替代Enumeration（允许调用者在遍历过程中语法正确地删除元素。）

在使用 Iterator 对容器进行迭代时如果修改容器 可能会报 ConcurrentModificationException 的错。 官方称这种情况下的迭代器是 fail-fast 迭代器。

CopyOnWriteArrayList，ConcurrentHashMap 替换 ArrayList， HashMap，在 copy 版本上进行修改， 不会影响原来的迭代。有内存消耗。

Collections.synchronizedList 加同步锁

红黑树

基本算法思想来源2-3树

Collections

操作集合

void reverse(List list)：反转 void shuffle(List list),随机排序 void sort(List list),按自然排序的升序排序 void sort(List list, Comparator c);定制排序，由Comparator控制排序逻辑 void swap(List list, int i , int j),交换两个索引位置的元素 void rotate(List list, int distance),旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面。

Collections中几乎对每个集合都定义了同步控制方法，例如 SynchronizedList(), SynchronizedSet()等方法，来将集合包装成线程安全的集合

Arrays

操作数组

sort()

equals

binarySearch

copy

copyOfRange

fill()