Java集合框架学习

Java集合框架学习

整体结构图

主要分为三类，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

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

ArrayList

支持 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

Queue子接口

Dqueue子接口

todo

Map接口

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

AbstractMap

HashMap

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

不是同步的

采用 拉链法 解决哈希冲突

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

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

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

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

新初始化哈希表时，容量为默认容量，阈值为 容量*加载因子已有哈希表扩容时，容量、阈值均翻倍如果之前这个桶的节点类型是树，需要把新哈希表里当前桶也变成树形结构复制给新哈希表中需要重新索引（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是基于它实现的

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

操作集合

Arrays

操作数组

sort()

equals

binarySearch

copy

copyOfRange

fill()