Java面试基础篇之集合

文章目录

• • 你知道的集合都有哪些?
  • 哪些集合是线程安全的?
  • Collection
  • • 集合类和数组有什么不同?
    • Collection和Collections有什么区别?
    • 如何确保一个集合不能被修改?
    • List和Set的区别?
    • List集合
    • • ArrayList和LinkedList的区别?
      • ArrayList动态扩容机制?
      • List和数组之间可以转换吗?
      • 讲一讲Vector集合?
      • ArrayList和Vector的区别?
      • 讲一讲Stack集合?
    • Set集合
    • • 讲一讲HashSet?
      • 讲一讲LinkedHashSet?
      • 讲一讲TreeSet?
    • Queue队列
    • • 讲一讲Queue?
      • 说一下Queue中remove()和poll()的区别?
  • Map集合
  • • 什么是HashMap?
    • 说一说HashMap的底层数据结构?
    • 为什么要改成"数组+链表+红黑树"?
    • 为什么链表转红黑树的阈值是8?
    • 那么转回链表的阈值用的是6怎么不复用8?
    • HashMap的扩容机制
    • 负载因子为什么是0.75不是别的?
    • 简单说一下TreeMap?
    • 简单说一下LinkedHashMap?
    • ConcurrentHashMap和HashMap的区别?
    • ConcurrentHashMap如何保证线程安全的?
    • CAS是什么?
    • 说一说Hashtable?
    • Hashtable和HashMap有什么区别?
  • Iterator迭代器
  • • Iterator迭代器是什么?
    • 说一说ListIterator迭代器?
    • Iterator和ListIterator有什么区别?
    • 关于forEach?

你知道的集合都有哪些?

• List
  • ArrayList
  • LinkedList
  • Vector
  • Stack
• Set
  • HashSet
  • LinkedHashSet
  • TreeSet
• Map
  • HashMap
  • LinkedHashMap
  • TreeMap
  • ConcurrentHashMap
  • Hashtable

哪些集合是线程安全的?

• Vector
• Stack
• Hashtable
• ConcurrentHashMap

Collection 集合类和数组有什么不同?

• 数组长度是固定的,而集合类的长度是可变的,数组用来存放基本数据类型,集合用来存放对象

Collection和Collections有什么区别?

• Collection是一个集合接口,它提供了对集合对象进行基本操作的通用接口方法,List和Set是它的子类
• Collections是一个包装类,包含了很多静态方法,不能被实例化,属于一个工具类,提供一些工具方法,比如:sort(list)排序等

如何确保一个集合不能被修改?

• 可以使用Collections.unmodifiableCollection(Collection c)方法来创建一个只读集合
• 对集合进行任何修改操作都会抛出UnsupportedOperationException异常

List list = new ArrayList<>();
list.add("x");
Collection cList = Collections.unmodifiableCollection(list);
cList.add("y"); // 运行时此行报错
System.out.println(list.size());

List和Set的区别?

• List接口实例储存的是有序的,可以重复的元素,可以通过索引直接操作元素
• Set接口实例储存的是无序的,不可以重复的元素,不能通过索引获取元素,元素的唯一性靠储存的元素类型是否重写hashCode()和equals()方法来保证,如果没有重写这两个方法,则无法保证元素的唯一性

List集合 ArrayList和LinkedList的区别?

• ArrayList的底层是由动态数组的数据结构实现,查询速度快,增删速度慢
• LinkedList的底层实现基于双向链表,查询慢,增删速度快

ArrayList动态扩容机制?

• 在JDK1.8中,先创建时,数组的初始容量为0
• 当添加第一个元素时,真正的分配容量,默认分配为10
• 当容量不足时(容量为size,添加第size+1个元素时),先判断按照1.5倍(位运算)的比例扩容能否满足最低容量要求,能满足则按照1.5倍扩容,不能满足则以最低容量要求进行扩容

List和数组之间可以转换吗?

• 数组转List: 使用Arrays.asList(array)进行转换
• List转数组: 使用List自带的toArray()方法

讲一讲Vector集合?

• Vector集合的内部实现类似于ArrayList,Vector也是基于一个容量能够动态增长的数组实现,但是Vector的扩容机制是2倍扩容,很多方法都加入同步语句(源码方法中有synchronized),所以线程相对安全

ArrayList和Vector的区别?

• ArrayList是线程不安全的,Vector是线程相对安全的
• 因为Vector中加入同步语句,所以效率性能不如ArrayList
• Vector的扩容机以是2倍扩容,而ArrayList是以1.5倍扩容的

讲一讲Stack集合?

• Stack集合继承了Vector集合,所以底层也是由数组实现,是线程安全的
• 以一种"后进先出"(LIFO)的线性数据结构来储存元素,是一种特殊的线性表
• 元素的添加和删除操作只能在表的一端进行,即栈顶,对元素的访问加以限制,仅仅提供对栈顶元素的访问操作
• 对栈顶元素的操作实际上是对数组尾部元素的操作

Set集合 讲一讲HashSet?

• HashSet底层是基于HashMap实现的,所以底层基本是直接调用HashMap的相关方法完成,HashSet保存无序不重复的元素,线程不安全

讲一讲LinkedHashSet?

• LinkedHashSet继承于HashSet,但是它的底层并不是以HashMap实现,而是以LinkedHashMap实现,通过在HashSet的构造方法中传入一个参数true,来引用LinkedHashMap,以下为源码:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

讲一讲TreeSet?

• TreeSet底层是由TreeMap实现的,添加的数据存入的Map的key位置,而value则是固定的PRESENT(Object)
• TreeSet的元素是有序且不重复的,向TreeSet中存放的对象必须实现Comparable,线程不安全

Queue队列 讲一讲Queue?

• Queue继承了Collection是一种特殊的线性表,遵循的是"先进先出"(FIFO)的的基本原则
• 一般来说,它只允许在表的前端进行删除操作,在表达后端进行插入操作,但是某些队列允许在任何地方插入删除,比如说常用的LinkedList集合,实现了Queue接口
• 队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分

说一下Queue中remove()和poll()的区别?

• poll() 移除并返回队列头部的元素,如果队列为空,则返回null
• remove()移除并返回队列头部的元素,如果队列为空,则抛出NoSuchElementException异常

Map集合 什么是HashMap?

• HashMap : 哈希表,也称为散列表是一种插入,查找,删除操作性能很高的数据结构,保存key-value的映射关系的集合,线程不安全

说一说HashMap的底层数据结构?

在JDK1.8之前是HashMap是采用数组+链表实现的,JDK1.8之后HashMap的底层是通过数组+链表+红黑树来实现的

• HashMap的主干是一个Entry数组,每一个Entry包含一个key-value键值对
• 在存入数据时,会先计算key的hashCode来确定在数组上的储存位置,这个位置通常称为hash桶
• 两个不同元素计算出的hashCode可能相同,这种情况称为**hash冲突(hash碰撞),这时当元素准备存入hash桶时,发现已经被其他元素占用**,这时HasMap采用链地址的方法,就是将元素通过链表的结构储存
• 如果定位到的数组包含链表,存入前先遍历链表,存在即覆盖,否则新增
• 当数组长度大于64,链表长度超过8,链表结构会更变为红黑树
• 对于移除,当链表长度小于等于6时,该位置的节点从红黑树转换成链表
• 由于查询时,定位在链表结构的数据时,仍然需要遍历链表HashMap中的链表出现越少,性能越好

为什么要改成"数组+链表+红黑树"?

• 主要是为了提升hash冲突严重链表过长的查询性能

为什么链表转红黑树的阈值是8?

• HashMap在设计时也面临空间与时间的权衡,红黑树的节点大小约为链表的两倍,如果阈值设置太小,红黑树的查询性能得不到体现,浪费空间
• 根据计算链表中节点的个数到达8时,红黑树的性能才会开始展现

那么转回链表的阈值用的是6怎么不复用8?

• 如果节点数在8之间来回徘徊,就会频繁的更改数据结构,对性能造成损耗

HashMap的扩容机制

• 不指明初始大小时初始容量是16,容量必须是2的N次方,当数组中的元素的个数达到扩容阈值threshold,触发两倍扩容
• 扩容阈值 = 容量 * 负载因子(默认是0.75),可以理解为总容量的75%

负载因子为什么是0.75不是别的?

一样的思路,空间和时间的权衡,0.75是比较合适的值

• 负载因子太小,会导致表中的数据还很少就开始扩容,浪费空间

• 负载因子太大,可能会导致表中的链表长度变长,影响查询效率

简单说一下TreeMap?

• TreeMap底层通过红黑树实现,存入的元素默认情况下通过key值的自然顺序排序,线程不安全

简单说一下LinkedHashMap?

• LinkedHashMap继承自HashMap,可以说LinkedHashMap = HashMap + 双向链表,保证了插入的Entry中的顺序,默认按照插入顺序排序,线程不安全

ConcurrentHashMap和HashMap的区别?

• ConcurrentHashMap是线程安全的
• HashMap是线程非安全的

ConcurrentHashMap如何保证线程安全的?

• 在JDK1.7版本,使用了分段锁思想,采用Segment字段,解决了HashTable锁范围广的问题,将数据分段储存,给每一段数据加锁

• 在JDK1.8版本,采用数组中的元素作为锁,从而实现对头节点进行加锁,并发控制使用synchronized和CAS来操作

CAS是什么?

• Compare-And-Swap比较并替换,CAS需要3个操作数: 内存地址V,旧的预期值A,即将要更变的新目标值B
• CAS指令执行时,仅当内存地址V和预期值A相等时,将内存地址V的值更改为B,否则什么都不做
• CAS是乐观锁技术,当多个线程尝试使用CAS同时更新同一个变量时,只有一个线程能够更新,其他的线程都失败,失败的线程不会被挂起,而是被告知这次竞争中失败,并不断再次尝试
• 详见会在Java面试基础篇之线程中

说一说Hashtable?

• Hashtable的底层和HashMap非常类似,但是它是线程安全的,通过源码可以看到它的主要方法加上了**synchronized**

Hashtable和HashMap有什么区别?

• Hashtable是线程安全的,HashMap是线程非安全的
• Hashtable 的锁范围非常大,代价很高,效率性能低
• Hashtable的默认初始容量是11,扩容机制是2倍+1
• key和value都不允许为null,如果为null会抛出异常

Iterator迭代器 Iterator迭代器是什么?

• Iterator不是集合,是一个接口,可以遍历集合的对象,为各种容器提供了公共的操作接口,隔离对容器的遍历操作和底层实现,从而解耦,只能单向遍历(向后遍历)

• 也就是说,当前遍历的集合元素被增删时(迭代器调用remove方法除外),会抛出ConcurrentModificationException (并发修改异常)

• 迭代器的的核心方法:

  • next()会返回迭代器的下一个元素,并且更新迭代器指针的位置

  • hasNext()用于检测集合中是否还有元素

  • remove()将迭代器返回的元素删除

List coll = new ArrayList<>();
        coll.add("李冰冰");
        coll.add("范冰冰");
        coll.add("高圆圆");
        coll.add("陈圆圆");

        Iterator it = coll.iterator();
        while (it.hasNext()) {
            String s = it.next();
            System.out.println(s);
            coll.add("章子怡");// 报异常
            coll.remove(s);// 报异常
            it.remove();
        }
        System.out.println("=====================" + coll);

说一说ListIterator迭代器?

• ListIterator继承于Iterator接口,只能用于List集合的访问
• 比起Iterator来说,ListIterator对集合的遍历更加灵活,可以双向遍历(向前/向后遍历)

Iterator和ListIterator有什么区别?

ListIterator的功能更加强大

• Iterator只能单向遍历,ListIterator可以双向遍历
• ListIterator可以使用add()在List中添加元素,Iterator不行
• ListIterator可以用nextIndex()和previousIndex()定位当前索引位置,Iterator不行
• ListIterator可以通过set()方法对对象进行修改,Iterator不行

关于forEach?

• forEach增强for循环,是JDK1.5后出现的高级for循环,开业用来遍历数组和集合
• 内部原理就是一个Iterator迭代器
• 使用forEach在遍历过程中不能对元素进行增删操作