Shulou(Shulou.com)06/03 Report--

1. Brief introduction

JDK1.2 introduces the Java collection framework, which contains a set of data structures. Unlike arrays, the storage space of these data structures increases dynamically as elements are added. Among them, some support adding repeating elements, others do not, some support null, and some can print elements in ascending order automatically.

All these data structures are in the java.util package, including Collection, List, Set, Map, SortedMap interfaces. The implementation classes of these interfaces are LinkedList, TreeSet, ArrayList, HashMap and so on. In addition to these data structures, the java.util package also provides utility classes such as Date, GregorianCalender, StringTokenizer, and Random.

two。 classification

The data structures in the collection framework can be classified according to interface, implementation, and algorithm.

Interfaces: Collection, List, and Map make up the interfaces of all the concrete implementation classes in the collection framework, and they define the methods that subclasses must implement, which are easy to remember. For example, adding elements to a collection uses the add () method defined in Collection

Implementation: all classes that implement the above three interfaces are called collection frameworks and are actually data structures. Such as LinkedList, TreeSet, etc.

Algorithms: the set framework provides many algorithms that can be called directly, such as finding maximum and minimum values, sorting, filling, etc.

3. Advantages and disadvantages

It has the following four advantages

Reduces workload while increasing software availability: there is no need for every programmer to sort, find, and find out the number of times elements appear in the data structure

Faster and more persistent: the underlying data structures of the collection framework are divided into two categories, node-based and array-based, the former is more efficient when frequently added, and the latter is faster when frequently read. Some data structures are synchronized thread-safe, but affect speed, while others are not thread-safe. Programmers should clearly understand these factors before choosing data structures.

Interoperability and transformation: due to the implementation of the Collection interface, data structures can be converted to each other. You can clone, you can convert existing structures to synchronized versions, and you can convert linked list-based data structures to array-based structures.

Have the following two shortcomings

Beware of type conversion: great care should be taken when converting between collection framework classes, especially considering generic type compatibility

Runtime type checking: the collection framework throws an exception at run time, which requires more attention when programming

4. Inheritance system

The data structure inheritance system in java.util is divided into two categories, one is to implement Collection interface, the other is to implement Map interface.

Cdn.xitu.io/2019/9/21/16d53f88a64f30c4?w=640&h=599&f=jpeg&s=34805 ">

Collection inheritance system

Map inheritance system (picture from Wikipedia)

Core interfaces and implementation classes of the collection framework:

Collection: root interface, most data structures implement the methods in the Collection interface

Set: the data structure that implements the Set interface does not allow duplicate elements, such as HashSet, LinkedHashSet

SortedSet: data structures that implement the SortedSet interface can print elements in ascending order by default, such as TreeSet

List: the data structure that implements the List interface allows repeating elements, which can be accessed through index, such as LinkedList, ArrayList, Vector

Map: the data structure that implements the Map API stores key-value pairs. Duplicate key is not allowed, such as HashMap, LinkedHashMap, Hashtable.

SortedMap: inherits the Map interface, stores key-value pairs, does not allow duplicate key, and prints elements in ascending order of key by default, such as TreeMap

The default sorting of SortedSet and SortedMap is the natural order, which can be customized through the Comparator or Comparable interface.

There are also some abstract classes between the interface and the concrete implementation class, as shown in the following figure:

These abstract classes add a lot of functionality to the collection:

HashSet: implement Set interface, do not allow duplicate elements, underlying data structure hash table

LinkedHashSet: implement Set interface, no duplicate elements, underlying data structure hash table and double linked list

TreeSet: implement NavigableSet interface, no duplicate elements are allowed, and the underlying data structure is red-black tree.

ArrayList: implements List interface, allows repeating elements, and variable array of underlying data structures

LinkedList: implement List interface, allow repeating elements, underlying data structure double linked list

Vector: implements List interface, allows repeating elements, and variable array of underlying data structures

HashMap: implement Map interface, do not allow duplicate key, underlying data structure hash table

LinkedHashMap: implement Map interface, do not allow duplicate key, underlying data structure hash table and double linked list

HashTable: implement Map interface, do not allow duplicate key, underlying data structure hash table

TreeMap: implement SortedMap interface. Duplicate key is not allowed. The underlying data structure is red-black tree.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.