Overview of the Java Collections Framework and Its Core Data Structures

The Java Collections Framework implements common basic data structures such as collections, linear lists, queues, stacks, and maps.

The class relationship diagram of the framework is shown below:

The framework mainly consists of the Collection interface and the Map interface. Collection has sub‑interfaces List, Set, and Queue. Common concrete classes include ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, as well as legacy classes such as Vector, Stack, and Hashtable.

1. Linear List

Linear lists have two implementations: the random‑access sequential list ArrayList and the linked list LinkedList. ArrayList is a sequential list that allows fast random access, but deletions require shifting many elements, which is inefficient. LinkedList is a doubly‑linked list that makes deletions easy, but element access is slower because it requires traversal.

2. Queue

Java’s queue is flexible and implemented as a double‑ended queue (deque), allowing insertion and removal at both head and tail.

There are two queue implementations: the sequential ArrayQueue and the linked LinkedList, which implements the Deque interface.

Java also provides PriorityQueue, which always removes the smallest element. It uses a heap internally and requires stored elements to implement Comparable.

3. Stack

The stack is implemented by the Stack class, which extends Vector; therefore, besides the usual push/pop at the top, elements can be added or removed at any position.

4. Set

A set represents a collection that does not allow duplicate elements, implemented by HashSet and TreeSet. HashSet uses a hash‑table structure (illustrated in the following image):

The hash table is implemented as an array of buckets, each bucket being a linked list. When adding an element s, its hashCode determines the bucket; if the bucket is empty, s is placed directly, otherwise the bucket is traversed to ensure no duplicate exists before insertion. TreeSet also builds on a hash‑table but adds a red‑black tree to keep elements sorted, allowing ordered traversal.

5. Map

A map stores key‑value pairs and is defined by the Map interface, which does not extend Collection. Implementations include HashMap and TreeMap. HashMap is similar to HashSet but stores Map.Entry<K,V> objects. Adding a pair <k,v> hashes k, selects a bucket, and either inserts a new entry or replaces the existing value for that key. TreeMap works like TreeSet, sorting entries by their keys.

A map can provide three views: the key set, the values collection, and the entry set, returned by the following methods:

Set<K> keySet();

Collection<V> values();

Set<Map.Entry<K,V>> entrySet();

Note that the returned Set objects are not instances of HashSet or TreeSet but are specific implementations that hide unsupported operations.

6. LinkedHashSet and LinkedHashMap

These classes remember the insertion order by maintaining a linked list on top of the hash‑table structure. LinkedHashMap can also remember access order when constructed with accessOrder=true. Each get or put moves the accessed entry to the end of the linked list, enabling LRU‑style caching.

7. Vector, ArrayList, Hashtable, and HashMap Vector and Hashtable are legacy classes. Vector is similar to ArrayList but its methods are synchronized, making it thread‑safe; Hashtable mirrors HashMap with synchronized methods.

Reference: "Java Core Technology".

© Copyright statement: Content sourced from the internet; rights belong to the original author. If any infringement is found, please notify us for prompt removal.

Original link: http://www.cnblogs.com/jqctop1/p/4722648.html