⾯试最常⻅问题之 Java 集合框架

Java中的List、Set和Map区别

Java中的List、Set和Map都是集合类,但它们之间有以下区别:

1. List:列表,有序集合,可以包含重复元素。主要实现类有ArrayList和LinkedList。

2. Set:集,无序且不可重复。主要实现类有HashSet和TreeSet。

3. Map:映射,存储key-value键值对,key不能重复。主要实现类有HashMap和TreeMap。

更具体的区别如下:

- List:

- 有序:元素的插入顺序是元素在List中的顺序

- 可重复: List可以包含多个相同的元素

- 主要实现类:ArrayList, LinkedList, Vector等

- Set:

- 无序:元素不排列,所以不存在索引或插入顺序

- 不可重复:Set中不能包含相同的元素

- 主要实现类:HashSet, TreeSet, LinkedHashSet等

- Map:

- 键值对:Map中元素是键值对(key-value)形式存储

- key不可重复:一个Map中不同的key值必须唯一

- value可以重复:一个Map中多个key可以映射到同一个value

- 主要实现类:HashMap, TreeMap, HashTable, LinkedHashMap等

List和Set都存储对象,但List有序可重复,Set无序不可重复。Map存储键值对,key不可重复,用于 value的快速查找

如何选⽤集合?

在Java中选择合适的集合类时,可以根据以下几个考虑因素:

1. 是否需要存储序:如果需要根据元素的插入顺序来获取元素,或者需要对元素进行排序,那么应选择List集合,如ArrayList。如果不需要存储序,可以选择Set集合,如HashSet。

2. 是否允许重复元素:如果需要存储重复元素,选择List集合,如ArrayList。如果不允许重复元素,选择Set集合,如HashSet。

3. 查询速度和插入/删除速度的权衡:

- List集合:查找快,增删慢。如ArrayList。

- Set集合:查找慢,增删快。如HashSet。

- Map集合:通过key快速查找value,增删快。如HashMap。

4. 元素数量:

- 数量少:ArrayList、HashSet、HashMap。

- 数量多:LinkedList、TreeSet、TreeMap。

5. 线程安全性:

- 线程不安全:ArrayList、HashSet、HashMap。

- 线程安全:Vector、TreeSet、TreeMap。

所以综上,选择集合的原则是:

- 需要存储序或允许重复元素,选择List,如ArrayList。

- 不需要存储序和不允许重复元素,选择Set,如HashSet。

- 需要映射关系,选择Map,如HashMap。

- 考虑线程安全性,可选择Vector、TreeSet和TreeMap。

- 考虑查询速度或增删速度,选择ArrayList、LinkedList、HashSet。

- 元素数量少用ArrayList和HashSet,多用LinkedList和TreeSet。

综合这几个原则可以很好地根据需求选择Java集合。

迭代器 Iterator 是什么？

Iterator(迭代器)是一种对象,它可以遍历并选择序列中的对象(如列表或集合)。Iterator对象本身也是一种对象,它跟踪集合中的位置和遍历状态。

主要用途:

1. 遍历集合元素:我们可以通过Iterator对象来遍历Set、List和Map等集合的元素。

2. 逐个访问集合元素:Iterator允许我们逐个访问集合的元素,而不需要预先知道集合的大小。

3. 可以删除元素:Iterator提供了remove()方法来删除迭代器返回的最后一个元素。

4. 实现类:每个集合类都有自己的迭代器实现,如:

- ArrayList - Iterator

- LinkedList - Iterator

- HashSet - Iterator

- HashMap - KeyIterator 和 ValueIterator

- TreeSet - Iterator

- TreeMap - KeyIterator 和 ValueIterator

使用Iterator的常见步骤:

1. 通过集合的iterator()方法获取对应的Iterator对象。

2. 使用Iterator对象的hasNext()方法判断集合中是否还有元素。

3. 使用Iterator对象的next()方法返回集合中的下一个元素。

4. Optional:可以使用Iterator对象的remove()方法删除集合中的元素。

5. 重复步骤2-4,直到hasNext()方法返回false。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
    Integer elem = iter.next();
    System.out.println(elem);
}

有哪些集合是线程不安全的？怎么解决呢？

java中的大多数集合类都是线程不安全的,比如:

- ArrayList

- HashSet

- HashMap

- LinkedHashSet

- LinkedHashMap

这是因为这些集合类在进行add、remove、set等修改操作时,内部索引会发生变化,在多线程环境下容易出现线程安全问题。

解决线程不安全集合的常用方式有两种:

1. 使用线程安全的集合类:

- Vector替代ArrayList

- Collections.synchronizedList() / Set() / Map() 方法替代相应的集合类

- ConcurrentHashMap替代HashMap

例如:

java

List<Integer> list = Collections.synchronizedList(new ArrayList<>());
Set<Integer> set = Collections.synchronizedSet(new HashSet<>());
Map<Integer, Integer> map = new ConcurrentHashMap<>();

2. 对集合进行同步:在多线程环境下,同一时间只能有一个线程操作集合,可以使用同步代码块或者锁来实现。

示例:

java

List<Integer> list = new ArrayList<>();
synchronized (list) {
    // 修改list
}

Set<Integer> set = new HashSet<>();
synchronized (set) {
    // 修改set  
}

或者:

List<Integer> list = new ArrayList<>();
Lock lock = new ReentrantLock();
lock.lock();
try {
    // 修改list
} finally {
    lock.unlock(); 
}

所以总结来说,要解决线程不安全集合的问题,有两种主要方案:

1. 使用线程安全的集合类,如Vector、Collections.synchronizedXxx()或ConcurrentHashMap。

2. 对线程不安全的集合加锁,使其同一时间只能被一个线程访问。

3。java9的Listof方法

Arraylist 和 Vector 的区别?

ArrayList和Vector都是List接口的实现类,用于存储元素的有序集合。但是,它们之间有以下几点主要区别:

1. 线程安全性:

- ArrayList是线程不安全的,不适用于多线程环境。

- Vector是线程安全的,适用于多线程环境。底层使用synchronized关键字修饰方法实现同步。

2. 扩容机制:

- ArrayList的扩容机制是每次扩容1.5倍,如初始容量是10,那么下一次扩容是15,然后22,33等等。

- Vector的扩容机制是每次扩容两倍,如初始容量是10,那么下一次扩容是20,40,80等等。

3. 性能:

- 由于线程安全带来的同步操作,Vector的性能略低于ArrayList。

- 在单线程环境下,ArrayList的性能更好,但在多线程环境下Vector性能更稳定。

4. 元素访问开销:

- ArrayList的随机访问开销较低,通过下标直接定位,时间复杂度O(1)。

- Vector的随机访问开销较高,需要进行同步检查,时间复杂度O(n)。

5. 添加、删除元素开销:

- 两者的添加、删除元素开销接近,都是 LinkedList > ArrayList > Vector。

- 这是因为Vector和ArrayList都基于数组实现,LinkedList基于双向链表实现。

综上,主要结论如下:

- 如果在单线程环境下,优先选择ArrayList;在多线程环境下选择Vector。

- 如果追求高性能,选择ArrayList;如果追求线程安全,选择Vector。

- 两者的添加、删除开销接近,远高于LinkedList。

- ArrayList扩容机制是1.5倍,Vector是2倍,会影响内存占用。

Arraylist 与 LinkedList 区别?

ArrayList和LinkedList都是List接口的实现类,但是它们的底层实现方式不同,这导致了以下几点主要区别:

1. 内存结构:

- ArrayList基于动态数组实现,LinkedList基于双向链表实现。

- 数组支持随机访问,但插入删除元素时可能需要移动大量元素,效率低。

- 链表不支持随机访问,但插入删除元素时只需要更改指针,效率高。

2. 插入和删除元素的时间复杂度:

- ArrayList:插入和删除元素的时间复杂度为O(n),因为可能需要移动大量元素。

- LinkedList:插入和删除元素的时间复杂度为O(1)。

3. 存储空间占用:

- ArrayList的空间浪费主要体现在列表前段留出的容量空间上。

- LinkedList的空间占用稍多,需要存储prev和next指针。

4. 访问元素时间复杂度:

- ArrayList:通过下标随机访问元素,时间复杂度为O(1)。

- LinkedList:需要从头节点或者尾节点遍历查找指定位置的元素,时间复杂度为O(n)。

5. 线程安全性:

- 两者都是线程不安全的,都需要在多线程环境下加锁进行同步。

综上,主要结论如下:

- 如果需要频繁地插入删除元素,使用LinkedList;如果需要频繁地随机访问元素,使用ArrayList。

- 如果追求插入删除性能和内存节省,选择LinkedList;如果追求访问性能和内存稍微浪费些,选择ArrayList。

- 两者都是线程不安全的,在多线程环境下都需要加锁进行同步。

- 其他方面两者相近,都是List接口的常用实现类。

所以具体使用时,需要根据实际需求场景选择 ArrayList 或者 LinkedList。两者性能和特点有差异,但都非常实用。

双向链表和双向循环链表

双向链表和双向循环链表都是链表的变种,它们的区别如下:

双向链表:

- 每个节点都有前驱节点和后继节点的指针,所以可以向前和向后遍历。

- 第一个节点的前驱节点和最后一个节点的后继节点都指向null。

双向循环链表:

- 和双向链表类似,每个节点都有前驱节点和后继节点的指针,可以向前和向后遍历。

- 但是,第一个节点的前驱节点指向最后一个节点,最后一个节点的后继节点指向第一个节点,形成一个环。

示例代码:

双向链表:
java
public class DoublyLinkedList {
    private Node head;
    
    private class Node {
        int value;
        Node prev;
        Node next;
        
        public Node(int value) {
            this.value = value;
        }
    }
    
    public void add(int value) {
        if (head == null) {
            head = new Node(value);
            return;
        } 
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }
        Node newNode = new Node(value);
        node.next = newNode;
        newNode.prev = node;
    }
    
    public void printList() {
        Node node = head;
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
    }
}

双向循环链表:

java
public class DoublyCircularLinkedList {
    private Node head;
    
    private class Node {
        int value;
        Node prev;
        Node next;
        
        public Node(int value) {
            this.value = value;
        }
    }
    
    public void add(int value) {
        if (head == null) {
            head = new Node(value);
            head.next = head;
            head.prev = head;
            return;
        }
        
        Node node = head;
        while (node.next != head) {
            node = node.next;
        }
        
        Node newNode = new Node(value);
        node.next = newNode;
        newNode.prev = node;
        newNode.next = head;
        head.prev = newNode;
    }
    
    public void printList() {
        Node node = head;
        do {
            System.out.print(node.value + " ");
            node = node.next;
        } while (node != head);
    }
}

所以总结来说,双向链表和双向循环链表的主要区别就在于头节点和尾节点的连接方式不同。双向链表的头尾节点为空,双向循环链表的头尾节点相连,形成一个环。其他特性基本相同。