落风的风
0%

Java集合初探

Posted on Edited on In

Java集合初探面经。

Java集合初探

集合值得花单独的一篇来讲

先要了解整个集合的而体系，由什么接口或者父类实现继承而来

几个常用集合如何分类、底层原理、扩容原理、线程安全

1 java中的集合体系

[1] 此小节参考了库森的面试小抄

简单的来讲分为Collection和Map两个体系，list、set、queue都是实现Collection接口的集合类。

注意：Collection是一个接口，Map不是Collection的子接口。Collections是一个静态工具类，里面包含对集合的各种操作方法。

Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue（Java5新增的队列），因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。

List代表了有序可重复集合，可直接根据元素的索引来访问；Set代表无序不可重复集合，只能根据元素本身来访问；Queue是队列集合。

Map代表的是存储key-value对的集合，可根据元素的key来访问value。

上图中淡绿色背景覆盖的是集合体系中常用的实现类，分别是ArrayList、LinkedList、ArrayQueue、HashSet、TreeSet、HashMap、TreeMap等实现类。

img

image-20210403163751501

2 讲讲ArrayList和LinkedList

ArrayList和LinkedList都是实现了List接口的类，他们都是元素的容器，用于存放对象的引用，并可以对存放的元素进行增删改查的操作，还可以进行排序；

1
Collections.sort(list,(o1,o2)->(o2-o1)); //list数组，递减排序

2.1 ArrayList介绍

1 实现机制

  • 内部使用数组的形式实现存储，实现了RandomAccess接口，利用数组的下标进行元素的访问，因此对元素的随机访问速度特别快。
  • 但是进行元素插入的时候，需要移动插入位置之后的所有元素，位置越靠前，需要位移的元素越多，开销越大；

2 适用场景

  • ArrayList适用在查找多,增删少的场景。如果元素的增删总是发生在数组的尾部，那么也可以选择ArrayList

3 扩容机制

  • ArrayList在初始化的时候，有初始大小10，插入新元素的时候，会判断是否需要扩容，扩容的步长是0.5倍原容量，扩容方式是利用数组的复制，因此有一定的开销；

2.2 LinkedList介绍

1 实现机制

  • 内部使用双向链表的结构实现存储。因此对元素增删改速度更快，直接操作链表指针即可。
  • LinkedList的随机访问速度惨不忍睹，因为无论你要访问哪一个元素，都需要从head起步正向或反向的进行元素遍历；
  • 之所以采用双向链表而非单链表实现，也是采用了空间换性能的方式，来降低查询操作的时间复杂度。如果采用单链表实现只能从头至尾遍历查找，时间复杂度是O(n)；但采用双链表实现，根据当前链表中实际结点个数size和要查找的索引进行比较，选择正向或者反向遍历。这种查找算法会比单链表从头至尾遍历减少一半的查找时间，提高了查找性能

2 适用场景

  • LinkedList适用在增删多,查找少的场景。（长链表情景下查询尤其缓慢）

3 扩容机制

  • LinkedList的元素并不需要连续存放，但是每个存放元素的单元比元素本身需要更大的空间，因此LinkedList对空间的要求比较大，但是扩容的时候不需要进行数组复制，因此没有这一环节的开销。

2.3 ArrayList 与 Vector 区别？

  • Vector是线程安全的，ArrayList不是线程安全的。其中，Vector在关键性的方法前面都加了synchronized关键字，来保证线程的安全性。
  • ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍，这样ArrayList就有利于节约内存空间。

3 讲讲HashMap和ConcurrentHashMap

JDK8在JDK7的基础上做了较大的调整，以JDK7为基础讲解，然后提及JDK8的改进

3.1 JDK7中的Map集合

1 HashMap

  • 在JDK8以前的HashMap是通过数组 + 链表的数据结构实现的。数组中的每一个元素都是一个包含键值对以及一个next指针的Entry对象，通过int index =key.hashCode()&(length-1) （与运算）得到数组的下标索引，从而将键值对映射到数组的不同槽位。当发生哈希碰撞时（就是键的hash值相等），新节点经过头插法插入链表中。
  • 但是当具体相同Hash值的Key较多的时候，链表的长度将会很长，导致查询效率极其低下
  • 扩容机制：hashmap的初始容量16，当需要执行Resize()扩容时，会执行一个ReHash操作，ReHash在并发的情况下有可能使链表成环，因此是线程不安全的。

2 ConcurrentHashMap

  • ConcurrentHashMap就是为了解决hashmap线程不安全的问题，JDK8之前的ConcurrentHashMap是采用锁分段技术实现了线程安全。相当于将HashMap中的table数组拆分成若干个分段数组，每一个Segment管理table数组的一个区间。Segment继承了ReentrantLock可重入锁，一个Segment就是一把锁。当对table数组的数据进行修改时，必须首先获得与它对应的Segment锁。

  • 这种方式是一种粗粒度的并发控制方案，当两个操作位于不同的两个段时可以不受线程安全的影响，但是位于同一个数组段的不同槽位的更新操作依然会受到并发控制的互斥限制

3.2 JDK8中的Map集合

HashMap和ConcurrentHashMap的实现都做了大的调整

1 HashMap

  • HashMap主要对长链表时查询缓慢的问题进行了改进，主要就是将长链表换成了红黑树。因此JDK8的HashMap采用了数组+短链表+红黑树的数据结构实现，在链表的长度超过8个节点的时候，将会将链表通过旋转的方式直接转换成红黑树（称之为树化），红黑树的引入在查询效率上至少提升了2倍以上。
  • JDK8的HashMap的table数组元素是由一个个Node或TreeNode节点组成，红黑树对应的数组槽位中始终存储其根节点，对于链表结构，每一次新元素采用“尾插法”插入链表
  • JDK8的HashMap对以前版本扩容可能造成环形链的问题进行了修复。但依然可能存在数据覆盖的问题出现，因此依然不是线程安全的。多线程环境下依然需要使用ConcurrentHashMap

2 ConcurrentHashMap

  • JDK8的ConcurrentHashMap则将分段锁的概念细划到单个的数组槽位上，即一个table数组槽位一个锁，因此只有更新操作具有相同hash值的线程之间才会存在竞争。JDK8抛弃分段锁不但节省了不必要的空间消耗，而且用回了传统的synchronized关键字的重量级锁。
  • ConcurrentHashMap内部维护了一个0.75的加载因子，也就是每当内部的数组占用率达到75%的时候就会将数组扩容至原来的2倍大小，并将原来的所有元素拷贝到新数组中，拷贝的时候为了充分利用里面多出来的空间，和提高查询搜索速度，会将一些长链表或红黑树拆分成两个体积更小的链表或红黑树分别存放于新数组的原位置和原位置+原数组长度的位置
  • ConcurrentHashMap的优化使扩容可以由多个参与线程一起辅助完成，从而减小时间消耗，但扩容本身还是是开销比较大操作，尽量在使用之前就确定大概需要的容量

3.3 ConcurrentHashMap的并发

1 ConcurrentHashMap 的 get 方法是否要加锁，为什么？

  • get 方法不需要加锁。因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

2 哈希桶table用volatile修饰的原因？

  • 哈希桶table用volatile修饰主要是保证在数组扩容的时候保证可见性。

3 ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？

  • 我们先来说value 为什么不能为 null ，因为ConcurrentHashMap 是用于多线程的 ，如果map.get(key)得到了 null ，无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，这就有了二义性。而用于单线程状态的HashMap却可以用containsKey(key) 去判断到底是否包含了这个 null 。
  • （不支持key为null，是规定，就这么设计的）

3.4 其他map集合和Set集合

1 TreeMap和LinkedHashMap区别

  • LinkedHashMap 拥有 HashMap 的所有特性，它比 HashMap 多维护了一个双向链表，保证了元素是按照插入的顺序排列。是有序的，
  • TreeMap 的底层就是一颗红黑树，它的 containsKey , get , put and remove 方法的时间复杂度是 log(n) ，并且它是按照 key 的自然顺序（或者指定排序）排列

2 ConcurrentHashMap与HashTable的区别

  • 都是线程安全的Map集合类，都用synchronized关键字来实现同步
  • ConcurrentHashMap锁的方式是稍微细粒度的，锁一个数组元素；
  • HashTable直接锁整个数组，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

3 HashSet的实现

  • HashSet的底层其实就是HashMap，只不过我们HashSet是实现了Set接口并且把数据作为K值，而V值一直使用一个相同的虚值来保存。
  • HashMap的K值本身就不允许重复，就可以实现set集合的不重复的性质

4 集合的遍历

[1] 参考了这篇HashMap遍历的四种方式

这里主要介绍map集合的4种遍历方式。list集合的遍历大概三种：1用索引get(i)方法遍历、2用增强for遍历、3用迭代器遍历。后两种map中都有体现、而第一种比较简单，不需要讲。

1 map集合的三种遍历方式

map集合的三种遍历方式分别是：1 keySet()搜索value、 2 entrySet()遍历键和值 3迭代器Iterator。三种方法各有优缺点（建议第二种）

  • 1 keySet()搜索value，在使用上更简单，但是通过key来查找value是耗时的操作。所以是一个低效的遍历（不推荐）
  • 2 entrySet()遍历键和值，一般情况下推荐使用这种。
  • 3迭代器Iterator，迭代器使用上虽然复杂，但是是老版本遍历map的唯一选择。并且只有使用迭代器才可以在迭代的时候从map中删除entry（通过调用iterator.remover()方法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Map<String,Integer> map = new HashMap<>();
map.put("aa",1);
map.put("bb",2);
map.put("cc",4);

//1 keySet()增强for遍历、实际上keySet()出来就是一个set集合
for(String key:map.keySet()){
    System.out.println(key+","+map.get(key));
}
//如果只遍历value,可以用values()获得值得集合
for (Integer i:map.values()){
    System.out.println(i);
}

//2 entrySet()遍历键和值、实际上map.entrySet()出来就是一个Entry对象得set集合
//Set<Map.Entry<String, Integer>> entries = map.entrySet();
for(Map.Entry<String,Integer> entry:map.entrySet()){
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key+","+value);
}

//3 迭代器遍历 实际上是迭代器遍历set集合（迭代器可以遍历所有的集合）
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
    Map.Entry<String, Integer> entry = iterator.next();
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key+","+value);
}

2 foreach和Iterator的关系

foreach是jdk5新增加的一个循环结构，其本身就是由iterator实现的。相当于是做了一层简单的封装，使遍历的语法更简洁了，但是并不是继承了iterator的所有方法。

foreach和iterator最大的不同之处就在于remove()方法上

  • iterator的remove()方法，不仅会删除元素，还会维护一个标志，用来记录目前是不是可删除状态。比如不能连续两次调用remove()，至少间隔一次next()方法
  • foreach中删除元素、直接报错。即快速失败（fail—fast） 机制

3 使用for循环与使用迭代器iterator的对比

  • for循环适合于支持随机访问的集合，比如ArrayList。效率更高
  • iterator迭代适合于链式的顺序结构，比如LinkedList。效率更高

5 其他数据结构

5.1 各种树形结构及其特点

  • 二叉查找树

  • 左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大

  • 缺点：正常的情况下，查找的时间复杂度为 O（logn）。但极端情况退化为链表，时间复杂度为O(n)

  • 平衡二叉树

    • 是二叉查找树，并且要求左右子树树高差严格不超过1。

    • 缺点：查询效率很高，但插入和删除的效率低，因为需要通过旋转来保证严格的平衡，过多的旋转是耗时的

  • 红黑树

    • 红黑树是一种弱平衡二叉树，通过对各个结点着色，仅保证没有一条路径会比其它路径长出两倍。相对于要求严格的AVL树来说，它的旋转次数少，适合增删多的场景。红黑树高度是O(log(n)).

  • B树

    • 平衡多路查找树：有j个孩子的非叶结点恰好有j-1个关键码，关键码按递增次序排列

    • 适用场景

      • B树多用于做文件系统的索引。文件太大的话无法一次加载到内存，使用B树可以多路储存，每次只加载一个结点来查找。

    • B+树，类似于B树的升级版本，数据都存放在叶子节点上。适合做索引、特别是顺序查找和范围查找

5.2 位图

其实就是桶数组的思想，每一个bit位作为一个桶。01表示存在或者不存在。

int的范围是-21亿到21亿之间，用位图的话 其实就是桶数组，存int相当于至少要42亿的坑位，42亿/32 相当于 1.2亿个byte。大约600Mb左右的内存。（10亿 1e9个byte约10G）

long范围-9200亿亿到9200亿亿，位图不可能放的下。所以数据的状态不能过多！！

位图，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

，数组的每一个元素的每一个二进制位都可以表示一个数据在或者不在，0表示数据存在，1表示数据不存在。因为比特位只有两种状态，要不是0，要不就是1，所以位图其实就是一种直接定址法的哈希，只不过位图只能表示这个值在或者不在。

赋值操作：（和该位为1的数）按位或将对应比特位置为1

删除操作：先取反，然后（和0）按位与，将对应比特位置0

判断是否存在：（和该位为1的数）按位与，结果不为0，说明对应位置存在！！

-------------感谢阅读没事常来-------------