是的,这个帖子我就是要通关 JAVA 集合
顺着上面的脑图,主要描述下 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
- 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 的修改还需要注意几点,尤其是他们之间的相互影响:
- 对父(sourceList) 子(subList)List 做的非结构性修改(non-structural
changes),都会影响到彼此。 - 对子List 做结构性修改,操作同样会反映到父List 上。
- 对父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);