时间戳

首页 > 技术文章 > 面试题系列二：集合框架

面试题系列二：集合框架

ftu-innovation 2021-06-10 22:35 原文

1.集合有哪些？

Collection接口和Map接口是所有集合框架的父接口：

  • Collection接口的子接口包括：Set接口和List接口

    (1) List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等；

    (2) Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等；

  • Map接口的实现类主要有：

    HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等

2.List、Set、Map 的区别？

3.数组和 list 之间的转换？

  • List转换成为数组：调用ArrayList的 toArray 方法。

  • 数组转换成为List：调用Arrays的 asList 方法。

4.ArrayList扩容机制

ArrayList集合大小如果创建时没有指定，则默认为0，若已经指定集合大小，则初始值为指；

当第一次添加数据的时候，集合大小扩容为10，

第二次及其后续每次按照

int oldCapacity = elementData.length; 
newCapacity = oldCapacity+(oldCapacity>>1)

5.ArrayList 、Vector和LinkedList 的区别？

  • ArrayList：底层基于数组，线程不安全，查询和修改效率高，但是增加和删除效率低，如果需要大量的查询和修改则可以选择ArrayList；

  • LinkedList：底层双向链表结构，线程不安全，查询和修改效率低，但是增加和删除效率高，如果需要大量的添加和删除则可以选择LinkedList；

  • Vector：如果创建Vector时没有指定容量，则默认容量为10，底层基于数组实现，线程是安全的，底层 采用synchronized同步方法进行加锁，很少用

6.Array 和 ArrayList 有何区别？

  • Array可以容纳基本类型和对象，而ArrayList只能容纳对象。

  • Array是指定大小后不可变的，而ArrayList大小是可变的。

  • Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。

7.在 Queue 中 poll()和 remove()有什么区别？

poll() 和 remove() 都是从队列中取出一个元素，但是 poll() 在获取元素失败的时候会返回空，但是 remove() 失败的时候会抛出异常。

8.如果要保证ArraList线程安全，有几种方式？

  1. 自己重写一个ArrayList集合类，根据业务一般来说，add/set/remove加锁

  2. 采用synchronized加锁：

    List<Object> list = Collections.synchronizedList(new ArrayList<>());

  3. 采用 ReentrantLock加锁：

    new CopyOnWriteArrayList<>().add("");

9.HashMap与HashTable的区别?

  • HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类；

  • HashMap允许K/V都为null；后者K/V都不允许为null；

  • HashMap没有考虑同步，是线程不安全的，效率上比hashTable要高；Hashtable使用了synchronized关键字，是线程安全的；

  • hashMap去掉了HashTable 的contains方法，但是加上了containsValue（）和containsKey（）方法。

  • 默认初始大小和扩容方式不同。HashMap 默认初始大小 16，容量必须是 2 的整数次幂，扩容时将容量变为原来的2倍；Hashtable 默认初始大小 11，扩容时将容量变为原来的 2 倍加 1。

  • 迭代器不同。HashMap 的 Iterator 是 fail-fast 迭代器；Hashtable 还使用了 enumerator 迭代器。

10.HashSet 的实现原理？

  • HashSet底层由HashMap实现

  • HashSet的值存放于HashMap的key上

  • HashMap的value统一为PRESENT

11.hashmap的底层原理，会不会产生哈希冲突？

12.HashMap遍历？

两种方式遍历：使用EntrySet遍历；使用KeySet 遍历

13.Set 遍历方法？

  • 迭代遍历：

Set<String> set = new HashSet<String>();  
Iterator<String> it = set.iterator();  
while (it.hasNext()) {  
  String str = it.next();  
  System.out.println(str);  
}

  • for循环遍历：

for (String str : set) {  
      System.out.println(str);  
}

14.HashSet和TreeSet的区别？

HashSet的存储方式：哈希码算法，加入的对象需要实现hashcode（）方法，快速查找元素 TreeSet的存储方式：按序存放，想要有序就要实现Comparable接口

不同点：

（1）HashSet由哈希表(实际上是一个HashMap实例)支持，不保证set的迭代顺序，并允许使用null元素。

（2）基于HashMap实现，API也是对HashMap的行为进行了封装，可参考HashMap

15.底层数据结构

  • Vector底层是数组。

  • Stack底层是Vector。

  • HashTable底层是链地址法组成的哈希表（即数组+单项链表组成）。

  • ArrayList底层是数组。

  • LinkedList底层是双向链表。

  • HashMap底层与HashTable原理相同，Java 8版本以后如果同一位置哈希冲突大于8则链表变成红黑树。

  • LinkedHashMap底层修改自HashMap，包含一个维护插入顺序的双向链表。

  • TreeMap底层是红黑树。

  • HashSet底层是HashMap。

  • LinkedHashSet底层是LinkedHashMap。

  • TreeSet底层是TreeMap。

16.迭代器 Iterator 是什么？

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

17.Iterator 怎么使用？有什么特点？

Java中的Iterator功能比较简单，并且只能单向移动：

  1. 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素；

    注意：iterator()方法是java.lang.Iterable接口,被Collection继承。

  2. 使用next()获得序列中的下一个元素；

  3. 使用hasNext()检查序列中是否还有元素；

  4. 使用remove()将迭代器新返回的元素删除。　

Iterator是Java迭代器最简单的实现，为List设计的ListIterator具有更多的功能，它可以从两个方向遍历List，也可以从List中插入和删除元素。

18.Iterator 和 ListIterator 有什么区别？

  • Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。

  • Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。

  • ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引，等等。

19.怎么确保一个集合不能被修改？

使用 JDK中java.util.Collections 类，unmodifiable*** 方法赋值原集合。

当再修改集合时，会报错 java.lang.UnsupportedOperationException。从而确保自己定义的集合不被其他人修改。

public class TestCollectionUnmodify {
 
    static List<String> list = new ArrayList<String>();
    static Set<String> set = new HashSet<String>();
    static Map<String, String> map = new HashMap<String, String>();
    
    static {
        list.add("1");
        list.add("2");
        list.add("3");
        
        set.add("1");
        set.add("2");
        set.add("3");
        
        map.put("1", "1");
        map.put("2", "2");
        map.put("3", "3");
    }
    
    public static void main(String[] args) {
        list = Collections.unmodifiableList(list);
        set = Collections.unmodifiableSet(set);
        map = Collections.unmodifiableMap(map);
        listModify();
        setModify();
        mapModify();
    }
    
    public static void listModify() {
        list.add("4");
    }
    
    public static void setModify() {
        set.add("4");
    }
    
    public static void mapModify() {
        map.put("3", "4");
    }
}




推荐阅读