SoFunction
Updated on 2025-03-06

Deeply understand the collection framework in Java basics

Java Collections Framework (JCF), also known as containers, can be compared here to STL in C++. It seems that a book that has been introduced in detail has not been found on the market. Here we mainly conduct source code analysis on the following parts and common questions in interviews.

For example, the HashMap and ConcurrentHashMap principles that are frequently asked in Ali. In-depth source code analysis is a necessary skill in interviews. Through reading this article, you will have a deeper understanding of the collection framework.

1. Overview

The Java collection framework provides a way to hold objects in data and provides operations on data collections. The Java collection framework is located inThere are three main categories:Collection(Interface)、Map (interface)、Collection Tools。

Collection

  • ArrayList：Threads are out of sync. The default initial capacity is 10, and the capacity is expanded to 1.5 times when the array size is insufficient. In order to pursue efficiency, ArrayList does not implement synchronized. If multiple threads are required to access concurrently, users can synchronize manually or use Vector instead.
  • LinkedList：Threads are out of sync。Two-way link implementation. LinkedList implements both the List interface and the Deque interface, which means it can be regarded as both a sequential container, a queue, and a stack. From this point of view, LinkedList is simply an all-around champion. When you need to use a stack or queue, you can consider using LinkedList. On the one hand, it is because the Java official has stated that it is not recommended to use the Stack class. What's more unfortunately, there is no class called Queue in Java at all (it is an interface name). Regarding stacks or queues, the first choice now is ArrayDeque, which has better performance than LinkedList (when used as stacks or queues).
  • Stack and Queue: There is a class called Stack in Java, but no class called Queue (it is an interface name). When you need to use the stack, Java no longer recommends using Stack, but recommends using a more efficient ArrayDeque; since Queue is just an interface, ArrayDeque is preferred when you need to use a queue (the second choice is LinkedList).
  • Vector：Thread synchronization. The default initial capacity is 10, and the capacity is expanded to 2 times when the array size is insufficient. Its synchronization is throughIteratorMethod plussynchronizedAchieved.
  • Stack：Thread synchronization. Inherited from Vector, several methods have been added to complete the functions of the stack. Stack is now deprecated, with limited use of ArrayDeque in stacks and queues, followed by LinkedList.
  • TreeSet：Threads are out of sync, internal useNavigableMapoperate. The default elements are arranged in "natural order", which can be passedComparatorChange the sorting. There is a TreeMap (adapter mode) in TreeSet
  • HashSet：Threads are out of sync, uses HashMap internally for data storage, and the methods provided are basically called HashMap methods, so the two are essentially the same. The collection element can be NULL.
  • Set:Set is a collection that does not contain duplicate elements. Set has at most one null element. Set collections can usually be obtained through adapter mode through Map collections.
  • PriorityQueue: PriorityQueue in Java implements the Queue interface, and null elements are not allowed; it is implemented through the heap, specifically through a complete binary treeSmall top pile(The weight of any non-leaf node is not greater than the weight of its left and right child nodes), which means that it can be implemented as the underlying PriorityQueue through an array.
    • The function of a priority queue is to ensure that each element retrieved is the smallest weight in the queue.(Java's priority queue takes the smallest element each time, and C++'s priority queue takes the largest element each time). This involves the relationship between size and size.The evaluation of element size can be through the natural ordering of the element itself, or through the comparator passed in during construction.(Comparator, similar to C++ functor).
  • NavigableSet: Added a search function to search for a given element: less than, less than or equal, greater than, greater than or equal to, and put back a key closest to the given element that meets the criteria.
  • EnumSet: Threads are out of sync. Internal implementation of Enum array, speed ratioHashSetquick.Only enum values ​​of enumeration classes passed in constructors。

Map

  • TreeMap: Threads are not synchronized, based onRed and black treeThe NavigableMap implementation of (Red-Black tree) can sort the records it saves according to the key. By default, it is sorted in ascending order of key values. You can also specify the sorted comparator. When it is traversed with Iterator, the records obtained are sorted.
    • The bottom layer of TreeMap is implemented through Red-Black tree, that meanscontainsKey(),get(),put(),remove()Alllog(n)time complexity. The specific algorithm implementation is based on the Introduction to Algorithm.
  • HashTable：Thread safety, the iterator of HashMap isfail-fastIterator.HashTable cannot store the key and value of NULL.
  • HashMap: Threads are out of sync. according tokeyofhashcodeUse static internal classes internallyNodeThe array of , the default initial size is 16 , doubled each time. When a Hash conflict occurs, the zipper method (link list) is used. JDK 1.8:When the number of elements in a single bucket is greater than or equal to 8, the linked list implementation is changed to a red and black tree implementation; when the number of elements is less than 6, it is changed back to the linked list implementation. This prevents hashCode attacks.
    • Java HashMap uses conflicting linked list method.
    • HashMap is a lightweight implementation of Hashtable that can accept key values ​​(keys) and values ​​(values) as null, which Hashtable does not allow.
  • LinkedHashMap：Save the insertion order of records, When traversing LinkedHashMap with Iterator, the first record obtained must be inserted first. You can also use parameters during construction and sort by the number of applications. It will be slower than HashMap when traversing, but there is an exception. When HashMap has a large capacity and is less actual data, it may be slower than LinkedHashMap, because the traversal speed of LinkedHashMap is only related to the actual data and has nothing to do with the capacity, while HashMap's traversal speed is related to its capacity.
  • WeakHashMap: From the name, it can be seen that it is some kind of Map. What's special about it is that the entry in WeakHashMap may be automatically deleted by GC, even if the programmer does not call itremove()orclear()method. The storage structure of WeakHashMap is similar to that of HashMap
    • Since there is WeekHashMap, is there WeekHashSet? The answer is no! However, the Java Collections tool class provides a solution.(Map<E,Boolean> map)Methods can wrap any Map into a Set.

Collection Tools

  • Collections、Arrays: A tool class help class of the collection class, which provides a series of static methods for sorting, searching, and thread-safe operations such as various operations in the collection.

  • Comparable、Comparator: Generally used for comparison of objects to realize sorting, and there are slight differences between the two.

    • The class designer did not implement the Comparable interface without considering the comparison problem. This is how we can use Comparator, in this case we do not need to change the object.
    • In a collection, we may need multiple sorting criteria. At this time, if you use Comparable, it will be a bit stretched. You can inherit Comparator and provide multiple standard comparators for sorting.

illustrate: When threads are not synchronized, you can use the () method to wrap a thread synchronization method

General implementation

Implementations
Hash Table Resizable Array Balanced Tree Linked List Hash Table + Linked List
Interfaces Set HashSet TreeSet LinkedHashSet
List ArrayList LinkedList
Deque ArrayDeque LinkedList
Map HashMap TreeMap LinkedHashMap

This is the end of this article about a deep understanding of the collection framework in Java. For more related contents of Java collection frameworks, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!