是的,这个帖子我就是要通关 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);