Skip to content

Latest commit

 

History

History
71 lines (48 loc) · 4.47 KB

java-collection-questions-01.md

File metadata and controls

71 lines (48 loc) · 4.47 KB
title category tag head
Summary of Common Java Collection Interview Questions (Part 1)
Java
Java Collections
meta
name content
keywords
Collection,List,Set,Queue,Deque,PriorityQueue
meta
name content
description
A summary of common knowledge points and interview questions about Java collections, hoping to be helpful to you!

Overview of Collections

Overview of Java Collections

Java collections, also known as containers, are primarily derived from two major interfaces: one is the Collection interface, which is mainly used to store single elements; the other is the Map interface, which is mainly used to store key-value pairs. For the Collection interface, there are three main sub-interfaces: List, Set, and Queue.

The Java collection framework is shown in the diagram below:

Overview of Java Collection Framework

Note: The diagram only lists the main inheritance relationships and does not enumerate all relationships. For example, it omits abstract classes like AbstractList, NavigableSet, and other auxiliary classes. For a deeper understanding, you can refer to the source code.

What are the differences between List, Set, Queue, and Map?

  • List (a good helper for order): The stored elements are ordered and can be duplicated.
  • Set (emphasizing uniqueness): The stored elements cannot be duplicated.
  • Queue (a call machine that implements queuing functionality): Determines the order based on specific queuing rules, and the stored elements are ordered and can be duplicated.
  • Map (an expert in searching using keys): Stores key-value pairs (key-value), similar to the mathematical function y=f(x), where "x" represents the key and "y" represents the value. Keys are unordered and cannot be duplicated, while values are unordered and can be duplicated, with each key mapping to at most one value.

Summary of Underlying Data Structures in the Collection Framework

First, let's look at the collections under the Collection interface.

List

Set

  • HashSet (unordered, unique): Implemented based on HashMap, using HashMap to store elements.
  • LinkedHashSet: A subclass of HashSet, implemented internally using LinkedHashMap.
  • TreeSet (ordered, unique): A red-black tree (self-balancing sorted binary tree).

Queue

Now let's look at the collections under the Map interface.

Map

  • HashMap: Before JDK1.8, HashMap was composed of an array and a linked list, where the array was the main body and the linked list existed mainly to resolve hash collisions (using the "chaining method" to resolve conflicts). After JDK1.8, there were significant changes in resolving hash collisions. When the length of the linked list exceeds a threshold (default is 8), it converts the linked list to a red-black tree to reduce search time. For details, see: HashMap Source Code Analysis.
  • LinkedHashMap: Inherits from HashMap, so its underlying structure is still based on a chained hash structure composed of an array and a linked list or red-black tree. Additionally, LinkedHashMap adds a doubly linked list to maintain the insertion order of key-value pairs. It also implements access order logic through appropriate operations on the linked list. For details, see: LinkedHashMap Source Code Analysis.
  • Hashtable: Composed of an array and a linked list, where the array is the main body and the linked list exists mainly to resolve hash collisions.
  • TreeMap: A red-black tree (self-balancing sorted binary tree).

How to Choose a Collection?

We mainly choose the appropriate collection based on the