Java工程师成神之路 - Java集合类枚举 - 《Java 相关笔记》

→ 集合类
→ 枚举

→ 集合类

常用集合类的使用、ArrayList 和 LinkedList 和 Vector 的区别、SynchronizedList 和 Vector 的区别、HashMap、HashTable、ConcurrentHashMap 区别

ArrayList ：基于动态数组实现，查找快，增删慢，内存空间地址连续完整。底层维护了一个Object[] 用于存储对象，默认数组的长度是10，容量不够时自动增长为之前的1.5倍。线程不安全，性能好。

内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。

LinkedList ：基于双向链表实现，查找慢，增删快，无需开辟连续内存空间，而是通过地址指向。线程不安全。

LinkedList 是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用

Vector ：底部实现也是数组来操作， Vector默认情况下扩容后的容量是之前的2倍。线程安全，性能低。
Vector是java.util包中的一个类。 SynchronizedList是java.util.Collections中的一个静态内部类。
1.Vector使用同步方法实现，synchronizedList使用同步代码块实现。
2.两者的扩充数组容量方式不一样（两者的add方法在扩容方面的差别也就是ArrayList和Vector的差别。）
3.SynchronizedList可以指定锁定的对象。
4.使用SynchronizedList的时候，进行遍历时要手动进行同步处理。
5.SynchronizedList有很好的扩展和兼容功能。他可以将所有的List的子类转成线程安全的类。
HashMap

底层数组+链表实现，可以存储null键和null值，线程不安全
初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
计算index方法：index = hash & (tab.length – 1)
使用containsKey()判断元素是否存在

HashTable

底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
初始size为11，扩容：newsize = olesize*2+1
计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length
Hashtable的实现是基于Dictionary抽象类的。

ConcurrentHashMap ：锁分段机制

底层采用分段的数组+链表实现，线程安全。它是HashTable的替代，比HashTable的扩展性更好。
通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。
Hashtable的synchronized是每次锁住整张表让线程独占。ConcurrentHashMap 将hash表分为16个桶，一次锁住一个桶，实现16个写线程并发进行，不会抛出ConcurrentModificationException，即锁分离技术。
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，而读操作大部分时候都不需要用到锁。
扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容）
插入前检测需不需要扩容，有效避免无效扩容

当期望许多线程访问一个给定collection时，ConcurrentHashMap通常优于同步的HashMap， ConcurrentSkipListMap通常优于同步的TreeMap。
当期望的读数和遍历远远大于列表的更新时，CopyOnWriteArrayList优于同步的ArrayList。
【参考链接】https://www.cnblogs.com/heyonggang/p/9112731.html
https://www.cnblogs.com/zq-boke/p/8654539.html

Set 和 List 区别？Set 如何保证元素不重复？

1、list容器是有序的list可以允许重复对象和插入多个null值；有序不唯一，查找快，增删慢。
2、set容器是无序的，数据不重复不允许null值；无序唯一查找慢，增删快，需要重写hashCode和equals方法。
因为HashSet的底层是由HashMap实现的，而HashSet的add方法，是将元素作为map的key进行存储的，map的key是不会重复的，所以HashSet中的元素也不会重复。
将一个key-value放入HashMap中时，首先根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同，那么它们的存储位置相同。如果这个两个key的equals比较返回true，那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。
且HashSet中add()中 map.put(e, PRESENT)==null 为false，HashSet添加元素失败。因此,如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素。

Java 8 中 stream 相关用法、apache 集合处理工具类的使用、不同版本的 JDK 中 HashMap 的实现的区别及原因

Stream 是 Java8 中处理集合的关键抽象概念，它可以指定你希望对集合进行的操作，可以执行非常复杂的查找、过滤和映射数据等操作。
特点：1.不是数据结构，不会保存数据。
2.不会修改原来的数据源，它会将操作后的数据保存到另外一个对象中。（毕竟peek方法可以修改流中元素）
3.惰性求值，流在中间处理过程中，只对操作进行了记录，并不会立即执行，需要等到执行终止操作的时候才会进行实际的计算。

// 示例代码
List<Long> ids = skuList.stream().map(Sku::getId).collect(Collectors.toList());

1.流创建：

Collection下的 stream() 和 parallelStream() 方法
Arrays 中的 stream() 方法
Stream中的静态方法：of()、iterate()、generate()
BufferedReader.lines() 方法
Pattern.splitAsStream() 方法

2.中间操作

筛选与切片： filter：过滤流中的某些元素
limit(n)：获取n个元素
skip(n)：跳过n元素，配合limit(n)可实现分页
distinct：通过流中元素的 hashCode() 和 equals() 去除重复元素
映射：map：接收一个函数作为参数，该函数会被应用到每个元素上，并将其映射成一个新的元素。
flatMap：接收一个函数作为参数，将流中的每个值都换成另一个流，然后把所有流连接成一个流。
排序： sorted()：自然排序，流中元素需实现Comparable接口
sorted(Comparator com)：定制排序，自定义Comparator排序器
消费：peek()：如同于map，能得到流中的每一个元素。但map接收的是一个Function表达式，有返回值；而peek接收的是Consumer表达式，没有返回值。

3.流的终止操作

匹配聚合：allMatch：接收一个 Predicate 函数，当流中每个元素都符合该断言时返回true，否则返回false
noneMatch：接收一个 Predicate 函数，当流中每个元素都不符合该断言时才返回true，否则返回false
anyMatch：接收一个 Predicate 函数，只要流中有一个元素满足该断言则返回true，否则返回false
findFirst：返回流中第一个元素 findAny：返回流中的任意元素
count：返回流中元素的总个数 max：返回流中元素最大值 min：返回流中元素最小值
规约操作： Optional< T > reduce(BinaryOperator< T > accumulator)
T reduce(T identity, BinaryOperator< T > accumulator)
U reduce(U identity,BiFunction accumulator,BinaryOperator< U > combiner)
收集操作： collect：接收一个Collector实例，将流中元素收集成另外一个数据结构。
Collectors.toList()
Collectors.toSet()
Collectors.toMap(Student::getName, Student::getAge)

apache 集合处理工具类的使用： CollectionUtils.isEmpty() 、CollectionUtils.isNotEmpty()
不同版本的 JDK 中 HashMap 的实现的区别及原因
HashMap 是用来存储数据的，它底层数据结构是数组，数组中元素是链表或红黑树，通过对 key 进行哈希计算等操作后得到数组下标，把 value 等信息放在链表或红黑树存在此位置。如果两个不同的 key 运算后获取的数组下标一致，就出现了哈希冲突。数组默认长度是16，如果实际数组长度超过一定的值，就会进行扩容。1.7和1.8主要在处理哈希冲突和扩容问题上区别比较大。
1.出现哈希冲突时，jdk1.7把数据存放在链表，jdk1.8是先放在链表，链表长度超过8就转成红黑树 treeifyBin()，复杂度由O(n)降至O(logn)，提高了查询效率，性能得到了提升。
2.jdk1.7扩容条件是数组长度大于阈值且存在哈希冲突，jdk1.8扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时。
3.重新拷贝数组元素时，key oldTable.length, 元素位置为原来的索引+oldTable.length，节省了重新计算hash的时间，提高了效率。
【参考链接】https://blog.csdn.net/kekekeqi/article/details/85464651

Collection 和 Collections 区别

1、java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有List与Set。
2、Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

Arrays.asList 获得的 List 使用时需要注意什么

1.基本数据类型转集合需要借助包装类，否则打印的都是地址值。
2.在使用Arrays.asList()后调用add，remove时出现java.lang.UnsupportedOperationException异常。
这是由于Arrays.asList() 返回的是 java.util.Arrays的内部类ArrayList 。 由于Arrays继承自AbstractList， AbstractList实现了List的接口，List中有add和remove这两个抽象方法，所以调用可以编译通过。但AbstractList中remove，add默认throw UnsupportedOperationException而且不作任何操作。这个内部类没有 override add()和remove()这两个方法，所以执行报错。

Enumeration 和 Iterator 区别

1.通过Enumeration，我们只能读取集合的数据，而不能对数据进行修改。Iterator除了能读取集合的数据之外，也能数据进行删除操作。
2.Iterator是支持fail-fast机制的：当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
3.Enumeration 与 iterator 都是迭代输出的方法，Enumeration先进后出，iterator先进先出。
4.还有一点要注意的就是，使用Iterator来遍历集合时，应使用Iterator的remove()方法来删除集合中的元素，使用集合的remove()方法将抛出ConncurrentModificationException异常。

fail-fast 和 fail-safe

快速失败 : 迭代器遍历集合过程中使用一个 modCount 变量。如果该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)，则迭代器使用hashNext()/next()遍历下一元素之前检测到 modCount != expectedmodCount ，会抛出ConcurrentModificationException，产生fail-fast事件。
java.util包下的集合类都是快速失败的。
如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。所以fail-fast机制，是一种错误检测机制。不能依赖于这个异常是否抛出进行并发操作的编程。
安全失败： 采用安全失败机制的集合容器，在遍历时先复制原有集合内容，在拷贝的集合上进行遍历。所以在遍历过程中对原集合所作的修改不能被迭代器检测到，所以不会触发ConcurrentModificationException。但是也就不能访问到修改以后的内容。
java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。
【参考链接】
https://blog.csdn.net/tb9125256/article/details/80892859
https://www.cnblogs.com/shamo89/p/6685216.html

ConcurrentSkipListMap和CopyOnWriteArrayList区别？

第一个问题中写到：

当期望许多线程访问一个给定collection时，ConcurrentHashMap通常优于同步的HashMap， ConcurrentSkipListMap通常优于同步的TreeMap。当期望的读数和遍历远远大于列表的更新时，CopyOnWriteArrayList优于同步的ArrayList。

ConcurrentSkipListMap是TreeMap的有序容器的并发版本。底层是通过跳表来实现的。跳表（Skiplist）是一个链表，但是通过使用“跳跃式”查找的方式使得插入、读取数据时复杂度变成了O（log（N）），和线程数几乎无关，也就是说在数据量一定的情况下，并发的线程越多，ConcurrentSkipListMap越能体现出他的优势。
ConcurrentSkipListMap线程安全的原理与非阻塞队列ConcurrentBlockingQueue的原理一样：利用底层的插入、删除的CAS原子性操作，通过死循环不断获取最新的结点指针来保证不会出现竞态条件。
特点：
1、ConcurrentSkipListMap 的key是有序的。
2、ConcurrentSkipListMap 支持更高的并发。
3、ConcurrentSkipListMap是线程安全的。适用于高并发场景。
在非多线程的情况下，应当尽量使用TreeMap。此外对于并发性相对较低的并行程序可以使用。
在多线程程序中，如果需要对Map的键值进行排序时，请尽量使用ConcurrentSkipListMap，可能得到更好的并发度。
注意，调用ConcurrentSkipListMap的size时，由于多个线程可以同时对映射表进行操作，所以映射表需要遍历整个链表才能返回元素个数，这个操作是个O(log(n))的操作。

CopyOnWriteArrayList使用了一种叫写时复制的方法，当有新元素添加到CopyOnWriteArrayList时，先从原有的数组中拷贝一份出来，然后在新的数组做写操作，写完之后，再将原来的数组引用指向到新数组，合适读多写少的场景。写操作拷贝数组会消耗内存，如果原数组的内容比较多的情况下，可能导致young gc或者full gc。
CopyOnWriteArrayList的整个add操作都是在锁的保护下进行的。这样做是为了避免在多线程并发add的时候，复制出多个副本出来,把数据搞乱了，导致最终的数组数据不是我们期望的。不能用于实时读的场景，像拷贝数组、新增元素都需要时间，所以调用一个set操作后，读取到数据可能还是旧的,虽然能做到最终一致性,但是还是没法满足实时性要求。
特点：

首先它是线程安全的；
拥有List的所有的基础功能；
比较适用于多读少写的并发场景；
使用写时复制的方法来实现线程安全。
设计思想
a. 读写分离，读和写分开；
b. 数据的最终一致性；
c. 以空间来换时间，来解决并发问题

【参考链接】https://blog.csdn.net/Sophisticated_/article/details/94331335
https://www.cnblogs.com/java-zzl/p/9767255.html
Java集合类枚举 - 图1

什么是阻塞队列？阻塞队列的实现原理是什么？如何使用阻塞队列来实现生产者-消费者模型？

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。（就是生产者存放元素的容器，而消费者也只从容器里拿元素。）BlockingQueue 接口是 Queue 的子接口，它的主要用途并不是作为容器，而是作为线程同步的的工具，因此他具有一个很明显的特性，当生产者线程试图向BlockingQueue 放入元素时，如果队列已满，则线程被阻塞，当消费者线程试图从中取出一个元素时，如果队列为空，则该线程会被阻塞，正是因为它所具有这个特性，所以在程序中多个线程交替向 BlockingQueue 中放入元素，取出元素，它可以很好的控制线程之间的通信。

阻塞队列使用最经典的场景就是 socket 客户端数据的读取和解析，读取数据的线程不断将数据入队列，然后解析线程不断从队列取数据解析。

→ 枚举

枚举的用法、枚举的实现、枚举与单例、Enum 类

用法：定义常量、switch判断、enum实例必须在前、只能实现不能再继承、新增方法和覆盖方法、枚举集合。 https://blog.csdn.net/testcs_dn/article/details/78604547
实现：枚举本质上是通过普通的类来实现的，只是编译器为我们进行了处理。
每个枚举类型都继承自 java.lang.Enum，并自动添加了 values 和 valueOf 方法。
而每个枚举常量是一个静态常量字段，使用内部类实现，该内部类继承了枚举类。
所有枚举常量都通过静态代码块来进行初始化，即在类加载期间就初始化。
另外通过把 clone、readObject、writeObject 这三个方法定义为 final 的，同时实现是抛出相应的异常。
这样保证了每个枚举类型及枚举常量都是不可变的。可以利用枚举的这两个特性来实现线程安全的单例。
枚举与单例

/**
 * 懒汉式单例模式（适合多线程安全）
 */
public class Singleton {
    private static volatile Singleton singleton = null;
    private Singleton(){}
    public static Singleton getSingleton(){
        if(singleton == null){
            synchronized (Singleton.class){
                if(singleton == null){
                    singleton = new Singleton();
                }
            }
        }
        return singleton;
    }    
}

这种编写方式被称为“双重检查锁”，主要在getSingleton()方法中，进行两次null检查。这样可以极大提升并发度，进而提升性能。毕竟在单例中new的情况非常少，绝大多数都是可以并行的读操作，因此在加锁前多进行一次null检查就可以减少绝大多数的加锁操作，也就提高了执行效率。但是必须注意的是volatile关键字，该关键字有两层语义。第一层语义是可见性，可见性是指在一个线程中对该变量的修改会马上由工作内存（Work Memory）写回主内存（Main Memory），所以其它线程会马上读取到已修改的值，关于工作内存和主内存可简单理解为高速缓存（直接与CPU打交道）和主存（日常所说的内存条），注意工作内存是线程独享的，主存是线程共享的。volatile的第二层语义是禁止指令重排序优化，我们写的代码（特别是多线程代码），由于编译器优化，在实际执行的时候可能与我们编写的顺序不同。编译器只保证程序执行结果与源代码相同，却不保证实际指令的顺序与源代码相同，这在单线程并没什么问题，然而一旦引入多线程环境，这种乱序就可能导致严重问题。volatile关键字就可以从语义上解决这个问题，值得关注的是volatile的禁止指令重排序优化功能在Java 1.5后才得以实现，因此1.5前的版本仍然是不安全的，即使使用了volatile关键字。或许我们可以利用静态内部类来实现更安全的机制，静态内部类单例模式如下：

/**
 * 静态内部类
 */
public class SingletonInner {
    private static class Holder {
        private static SingletonInner singleton = new SingletonInner();
    }
    private SingletonInner(){}
    public static SingletonInner getSingleton(){
        return Holder.singleton;
    }
}

静态内部类实现单例模式，这种方式优于上面两种方式，他即实现了线程安全，又省去了null的判断，性能优于上面两种。
但是以上两种写法是不考虑放射机制和序列化机制的情况下实现的单例模式，举个例子就能知道上面的单例不是很安全，以双重检索的单例模式为例子，我利用放射，能够创建出新的实例：

public static void main(String[] args) throws Exception {
        Singleton s=Singleton.getInstance();
        Singleton sual=Singleton.getInstance();
        Constructor<Singleton> constructor=Singleton.class.getDeclaredConstructor();
        constructor.setAccessible(true);
        Singleton s2=constructor.newInstance();
        System.out.println(s+"\n"+sual+"\n"+s2);
        System.out.println("正常情况下，实例化两个实例是否相同："+(s==sual));
        System.out.println("通过反射攻击单例模式情况下，实例化两个实例是否相同："+(s==s2));
    }

结果为：

cn.singleton.Singleton@1641e19d cn.singleton.Singleton@1641e19d cn.singleton.Singleton@677323b6 正常情况下，实例化两个实例是否相同：true 通过反射攻击单例模式情况下，实例化两个实例是否相同：false

枚举单例（Enum Singleton）是实现单例模式的一种新方式

public enum  EnumSingleton {
    INSTANCE;
    public EnumSingleton getInstance(){
        return INSTANCE;
    }
}

检测一下枚举的单例模式，结果会报Exception in thread “main” java.lang.NoSuchMethodException。出现这个异常的原因是因为EnumSingleton.class.getDeclaredConstructors()获取所有构造器，会发现并没有我们所设置的无参构造器，只有一个参数为（String.class,int.class）构造器，而且在反射在通过newInstance创建对象时，会检查该类是否ENUM修饰，如果是则抛出异常，反射失败。所以枚举是不怕发射攻击的。
显然枚举单例模式确实是很不错的选择，因此我们推荐使用它。但是这总不是万能的，对于android平台这个可能未必是最好的选择，在android开发中，内存优化是个大块头，而使用枚举时占用的内存常常是静态变量的两倍还多，因此android官方在内存优化方面给出的建议是尽量避免在android中使用enum。但是不管如何，关于单例，我们总是应该记住：线程安全，延迟加载，序列化与反序列化安全，反射安全是很重要的。
Enum 类：因为在没有枚举类的时候，我们要定义一个有限的序列，比如星期几，男人女人，春夏秋冬，一般会通过上面那种静态变量的形式，但是使用那样的形式如果需要一些其他的功能，需要写很多奇奇怪怪的代码。所以，枚举类的出现，就是为了简化这种操作。
Java集合类枚举 - 图2
【参考链接】https://www.cnblogs.com/saoyou/p/11087462.html 清晰易懂
 https://blog.csdn.net/javazejian/article/details/71333103 比较复杂
使用== 和使用equals方法的执行结果是一样的。因为在Enum类里面已经重写了equals方法，而方法里面比较就是直接使用 ==来比较两个对象的。所以在外边直接使用也是可以的。

switch 对枚举的支持

switch判断的是枚举类的ordinal方法，即枚举值的序列值。

枚举的序列化如何实现

枚举自己处理序列化
单例模式有一个比较大的问题，就是一旦实现了Serializable接口就不再是单例的了，因为每次调用 readObject()方法返回的都是新创建的对象，有一种解决办法就是使用readResolve()方法来避免此事发生。但是为了保证枚举类型像Java规范中所说的那样，每一个枚举类型及其定义的枚举变量在JVM中都是唯一的，在枚举类型的序列化和反序列化上，Java做了特殊的规定。
在序列化的时候Java仅仅是将枚举对象的name属性输出到结果中。反序列化的时候则是通过java.lang.Enum的valueOf()方法来根据名字查找枚举对象。所以enum类型在添加新的enum对象时，如果没有用到新的对象，那么enum的序列化和反序列化是不会有异常的。同时，编译器是不允许任何对这种序列化机制的定制的，因此禁用了writeObject、readObject、writeReplace和readResolve等方法。所以，JVM对序列化有保证。
【参考链接】 https://www.cnblogs.com/z00377750/p/9177097.html

枚举的线程安全性问题

我们在深度分析Java的ClassLoader机制（源码级别）和Java类的加载、链接和初始化两个文章中介绍过，当一个Java类第一次被真正使用到的时候静态资源被初始化、Java类的加载和初始化过程都是线程安全的。所以，创建一个enum类型是thread-safe(线程安全的) 。

Java集合类 枚举