是的，这个帖子我就是要通关 JAVA 集合

1.png

顺着上面的脑图，主要描述下 Java里面常用的数据结构，再结合源码进行解读一些方法，如 HashMap 的 put(k，v)，集合如何应对并发情况。以及一些应用如 BlockingQueue 双向会话，还结合 阿里Java手册泰山版，对集合的一些规约进行解读

个人理解，所有的数据结构，物理层面只有两种，内存连续或者不连续，即 数组（Array） 和 链表（LinkdList） ，其他的是 都是在此基础上，衍生的逻辑数据结构，并且设计冗余数据，如记录下一个数据位置，以空间换时间 or 时间换空间。

Collection

List

1） Array 和 ArrayList

  • Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型

  • Array 大小是固定的，ArrayList 的大小动态变化，可以扩容

  • ArrayList 提供了更多的方法和特性，如：addAll()，removeAll()，iterator() 等

2）ArrayList 和 LinkedList

20200720_161254.png

  • LinkedList 实现了 Deque 接口，可称为双向链表，该接口是妙笔并赋能
	LinkedList<Integer> lists = new LinkedList<>();
 	lists.addFirst(1);
	lists.push(2);
 	lists.addLast(3);
	lists.add(4);
	lists.addFirst(5);

	lists.forEach(System.out::println);
	// 5 2 1 3 4

  • LinkedList 在插入和删除数据时效率更高，ArrayList 在查找某个 index 的数据时效率更高

    ArrayList 直接开辟一块连续的内存空间，在随机访问的时候，会根据数据下标进行查询，删除单个数据有两个 重载方法 remove(int index) 和remove(Object o) ，会发现需要判断数组是否越界、元素是否非空、遍历整个集合查询是否包含该元素、使用fastRemove、以及modCount计数、快速失败概念，整体看是比较麻烦的；LinkedList 不用连续，用首尾相连的节点关系，描述数据位置，插入和删除只需要修改 Node 的前后指向，就非常方便啦

    链表相对于数组来说，链表的添加和删除速度很快，是顺序添加删除很快，因为一个 linkedList 会保存第一个节点和最后一个节点，时间复杂度为O(1)，但指定位置添加 add(int index, E element) ，那么会先遍历，然后找到改位置的节点，将节点添加到他前面，此时时间复杂度最大值为 O(n)

  • LinkedList 比 ArrayList 需要更多的内存，相对数据结构更复杂，头节点、尾节点都需要占用内存空间

3）ArrayList 和 Vector

  • 线程安全：
    Vector 多线程环境下线程安全，它的方法之间是线程同步（synchronized 进行同步）； ArrayList 多线程环境下线程不安全，并发量很小的情况下，用户量很少的管理项目，就用 ArrayList 咯，效率高，线程同步是会牺牲执行效率的，因为没有获得锁的线程，阻塞状态，会在等待锁的时候，存在时间消耗

  • 扩容：
    ArrayList 与 Vector 都有一个初始的容量大小，当存储元素超过容量时，就会触发扩容机制。这个扩容，会因为 JDK 版本不同，策略也不同，扩容概念都是一样的，直接看下面的 HashMap 扩容解读吧

Vector 虽然 是很旧很旧的容器了~~~ 但子类 Stack 依然常用
Stack 通过五个操作对类 Vector 进行了扩展，允许将向量视为堆栈。提供通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法

堆栈 (Stack) ： 如子弹入弹夹一样 先进后出（LIFO : last-in-first-out）

栈结构属于一种先进者后出，类似于一个瓶子，先进去的会压到栈低（push 操作），出去的时候只有一个出口就是栈顶，返回栈顶元素，这个操作称为 pop。

Stack 类继承自 Vector，所有方法都加入了 sync 修饰，使得效率很低，线程安全。

队列（Queue）：如排队过隧道 先进先出

它是一个双端队列。我们用到的 linkedlist 就是实现了 deque 的接口。支持在两端插入和移除元素。


public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(1);
    queue.offer(2);
    queue.offer(3);

    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
}

// 1, 2 , 3
常见形式：

LinkedList 是链表结构，队列呢也是一个列表结构，继承关系上 LinkedList 实现了 Queue，所以对于 Queue 来说，添加是 offer(obj)，删除是 poll()，获取队头(不删除)是 peek() 。

1） 我直接写个生产者消费者模型吧

2） 再来个双向会话，网络编程

拓展：为什么阿里手册中，要求谨慎使用 ArrayList 中的 subList 方法

分析和答案：subList是List接口中定义的一个方法，该方法主要用于返回一个集合中的一段、可以理解为截取一个集合中的部分元素，他的返回值也是一个List。
List 的subList 方法并没有创建一个新的List，而是使用了原List 的视图，这个视图使用内部类SubList 表示。所以，我们不能把subList 方法返回的List 强制转换成ArrayList 等类，因为他们之间没有继承关系。
另外，视图和原List 的修改还需要注意几点，尤其是他们之间的相互影响：

  1. 对父(sourceList) 子(subList)List 做的非结构性修改（non-structural
    changes），都会影响到彼此。
  2. 对子List 做结构性修改，操作同样会反映到父List 上。
  3. 对父List 做结构性修改，会抛出异常ConcurrentModificationException。
如何创建新的List？

如果需要对subList 作出修改，又不想动原list。那么可以创建subList 的一个
拷贝：

subList = Lists.newArrayList(subList);
list.stream().skip(strart).limit(end).collect(Collectors.toList());

资料援引：
https://www.jianshu.com/p/5854851240df
https://www.cnblogs.com/ljdblog/p/6251387.html

Set

HashSet

1）HashSet 如何保证数据不可重复

是底层通过 HashMap 实现 ，因为 HashMap 保证了 K 值存储不重复

private transient HashMap<E,Object> map;

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

HashSet、TreeSet 和 LinkedHashSet 选择

需要能快速访问的 Set，那么就要用 HashSet，HashSet 底层是 HashMap 实现的，其中的元素没有按顺序排列。

如要一个可排序 Set，那么你应该用 TreeSet，TreeSet 的底层实现是 TreeMap。

如要记录下插入时的顺序时，应该使用 LinedHashSet。

Set 集合中不能包含重复的元素，每个元素必须是唯一的，你只要将元素加入 set 中，重复的元素会自动移除。所以可以去重，很多情况下都需要使用（但是去重方式不同）。

LinkedHashSet 正好介于 HashSet 和 TreeSet 之间，它也是一个基于 HashMap 和双向链表的集合，但它同时维护了一个双链表来记录插入的顺序，基本方法的复杂度为 O(1)。

三者都是线程不安全的，需要使用 Collections.synchronizedSet(new HashSet(…));

Map

HashMap

1） put 和 get 存取值 过程 （这个简直不要太经典，回答也可深可浅
）
2） 如何决定使用 HashMap 还是 TreeMap

3） Spring 中 BeanFactory 体系实现，从 hashtable 到 ConcurrentHashMap 变化原因

拓展

  • 常用的缓存 Map 类
  • 优雅 并且合理 New 一个带有初始容量的 Map

分析和答案：
在已知HashMap 中将要存放的KV 个数的时候，设置一个合理的初始化容量可以有效的提高性能。
在Jdk 1.7 和Jdk 1.8 中，HashMap 初始化这个容量的时机不同。jdk1.8
中，在调用HashMap 的构造函数定义HashMap 的时候，就会进行容量的设定。
而在Jdk 1.7 中，要等到第一次put 操作时才进行这一操作。

我们可以认为，当明确知道HashMap 中元素的个数的时候，把默认容量设置成expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存

return (int) ((float) expectedSize / 0.75F + 1.0F);

or 谷歌的 guava 中的实现：

Map<String, String> map = Maps.newHashMapWithExpectedSize(7);