Preface

Usually , We always get some conditions to create objects while the program is running , These are created dynamically Objects need to be saved in some way . We can use arrays to store them , However, it is important to note that the size of an array, once defined, cannot be changed , We don't know how many objects the program will produce as it runs , The size of the array is then limited .Java The utility library also provides a set of container classes to solve this problem , The basic type is :List 、Set、Queue and Map. These object types are also called Collection classes , But because of Java The class library is used Collection This name refers to a special subset of the class library , So use the terminology “ Containers ” To call them . The following is a brief introduction Java Basic concepts and functionality of container class libraries 、 Different versions of each container are implemented and the relationships between containers are analyzed as a whole .

Java An overview of container class libraries

Java A block diagram of the container class

Java The main purpose of a container class library is “ Save the object ”, We divide it into the following two different concepts :

Collection

A separate element Sequence ( A way of storing a set of objects ), These elements are subject to one or more rules .List The elements must be saved in the order they were inserted ;Set There can be no duplicate elements in ;Queue According to the queuing rules to determine the order of object generation .

Collection Is a highly abstract container interface , This contains the basic operations and properties of the container .

Map

One makes right “ Key value pair ” object , Allows you to use keys to find values .

There are many more in the framework class diagram Abstract class , It is mainly convenient for us to create an instance of the container ,Abstract The methods in the interface are basically implemented in the class , We just need to choose the method we want to override .

Iterator

Let's see Iterator, We usually use Iterator Iterator to iterate over the container . Pictured above Collection Depend on Iterator Refer to : Realization Collection Need to achieve iterator() function , I can return one Iterator object .ListIterator It's specifically for traversal List The iterator .

Tool class Arrays and Collections Add elements to the container

java.util In bag Arrays and Collections Classes contain many utility methods .Arrays Class contains various methods that manipulate arrays , Also contains a static Arrays.asList() Method accepts an array or comma-separated list of elements , Convert it to a list object .Collection Class contains various methods for manipulating collections . We can also use Collections.addAll() Add a set of elements to the container .Collections.addAll() Accept one Collection Object and an array or comma-separated list of elements , Adds the element to Collection In the object .

Arrays.asList() The underlying implementation is an array , That is to use Arrays.asList() Generated List The size of can not be modified ( Add or remove elements ), Otherwise it will be thrown UnsupportedOperationException abnormal .

List

List Interface inherited from Collection Interface , be used for Collection All the methods in , stay Collection A number of methods have also been added , Make it possible to List Insert and delete elements in .List There are two basic implementations :ArrayList and LinkedList

  • Basic ArrayList, It is suitable for randomly accessing elements , But it is slow to insert and delete elements
  • LinkedList Suitable for use when elements are inserted and deleted more frequently , Random access is slower

Set

Set Does not hold duplicate elements in , The set of meanings and mathematical concepts . Set It is often used to test attributes , That is, query whether an element is in a certain Set in . Because of this, the search is done Set Important operations . Usually choose HashSet The implementation of the , It is optimized for quick lookups .Set There are also many different implementations , Different Set Implementations not only have different behaviors , And they can be in particular Set There are also different requirements for the type of elements placed in .

  • Set(interface)

    Deposit in Set Each element of must be uniquely correct . Join in Set Must be defined equals() Method to ensure the uniqueness of the object .Set Interfaces do not guarantee the order of maintenance elements .

  • HashSet

    Designed for quick lookups Set. Deposit in HashSet Must be defined hashCode(). Use HashMap Realization .

  • TreeSet

    In order Set, The bottom layer is a tree structure . Use it from Set Extract ordered sequences from . The element must be implemented Comparable Interface . Use TreeSet Realization .

  • LinkedHashSet

    have HashSet Query speed of , Internally, a linked list is used to maintain the order of elements ( Insertion order ). Iterate over this using an iterator Set when , The results are displayed in the order in which the elements were inserted . The element must also be defined hashCode() Method

Map

Map Has the following characteristics :

  • Map Is a key-value pair that maps keys to values (key-value) Interface

  • A map cannot contain duplicate keys , Each key can map to at most one value , But a value can be mapped by more than one key

  • Map It provides three Set The view is accessible to us : Keyed Set、 It's worth it Set That's the key value Set

  • The order of the mappings is defined as the mappings accessed Set The iterator on returns the order of the elements .TreeMa class , You can make certain guarantees about the order of the mappings ; Other , There is no guarantee

  • Mutable objects as mapping keys need to be very careful

  • Map Two of the implementation classes should be provided “ standard “ Constructors

    first ,void( No parameter ) Construction method , Used to create an empty map

    the second , With a single Map The constructor for a type parameter , Use to create a key that has the same key as its parameter - New mapping of value mapping relationships . With a single Map The constructor for a type parameter , Use to create a key that has the same key as its parameter - New mapping of value mapping relationships

Map Several basic implementations of :

  • HashMap

    Map Is a hash-based implementation ( To replace the HashTable).HashMap Use hash codes ( object hashCode() Generated value ) To do a quick search .

  • LinkedHashMap

    Be similar to HashMap, But iterating , The order in which key - value pairs are obtained is the order in which they are inserted , Or least recently (LRU) The order of the . Only than HashMap Slow down a little , Iterative access is faster , Because the internal order is maintained using linked lists .

  • TreeMap

    Implementation based on red black tree . see “ key ” perhaps “ Key value pair ” when , They're going to be sorted ( The order by Comparable or Comparator decision ).TreeMap Is that the results are sorted .TreeMap Is the only one with subMap() Of Map, You can return a subtree .

  • WeakHashMap

    Weak bond (weak key) mapping , Allows you to release the object that the map points to , This is designed to solve a particular type of problem . If there is no reference to something outside of the map “ key ”, Then this “ key ” It can be recycled by garbage .

  • ConcurrentHashMap

    A thread safe Map, Synchronization locking is not involved . It will be introduced in concurrency .

Stack and Queue

Stack It's a First in, then out (LIFO) The container of . Put the books in the box , Put it in first and take it out last , The last one in can be taken out , This model is the stack (Stack) describable .LinkedList There are methods to implement all the functions of the stack , Sometimes you can just say LinkedList Used as a stack .

The queue is a typical fifo (FIFO) The container of . The order in which things are put into the container is the same as the order in which they are taken out ( Priority queues queue things according to their priority ). Queues are often used as a reliable way to transfer objects from one area of a program to another . Queues are particularly important in concurrent programming . Again ,LinkedList Methods are also provided to support the behavior of queues , And it did Queue Interface .

Priority queue PriorityQueue

Fifo describes typical queue rules . Queue rules are defined for a given set of queue elements , Determines the rule for the next element in the pop-up queue . The next element that pops up from the priority queue declaration is the one that is most needed ( The element with the highest priority ).

We can do it in PriorityQueue On the call offer() Method to insert an object , This object will be sorted in the queue , The default sort is natural sort , Sort by insertion order , But we can do that by providing our own Comparator I'm going to change this sort . When calling peek()、poll() and remove() When the method is used , Gets the highest priority element of the queue .

The data structure implemented by the priority queue algorithm is usually a heap .

iterator

For access containers , Is there a way to make the same traversed code work for different types of containers ? To achieve this, use iterators . Use iterator objects , Traverses and selects the objects in the sequence , The client does not have to know or care about the underlying structure of the sequence .Java There are some restrictions on iterators , such as Java Of Iterator It can only move in one direction , This Iterator Can be used to :

  • Use next() Method to get the next element of the sequence
  • Use hasNext() Method checks if there are any elements in the sequence
  • Use remove() Method removes the element recently returned by the iterator , That means it's calling remove() You have to call it first next()

API Medium Iterator The method in the interface is as above , Realization Iterator Object needs to be implemented hashNext() Methods and next() Method ,remove Method is an optional operation .forEachRemaining yes Java 1.8(Java SE8) The method added in , be used for Lambda expression .

Here is a simple example of using an iterator to access a container :

class Cat{
private static int counter = 0;
private int id = counter++;
@Override
public String toString() {
return "Cat: " + id;
}
} public class IteratorAccessContainer {
// Traversal container methods that do not contain any container type information
public static void showElement(Iterator<Cat> it) {
while (it.hasNext()) { //hasNext() Check if there are any elements in the sequence
Cat cat = it.next(); //next() Returns an element in a sequence
System.out.print(cat + "\t");
}
System.out.println();
} public static void main(String[] args) {
ArrayList<Cat> cats1 = new ArrayList<Cat>();
LinkedList<Cat> cats2 = new LinkedList<>(); // Type parameters can be omitted The compiler can infer this automatically
HashSet<Cat> cats3 = new HashSet<>();
for(int i=0;i<3; i++) {
cats1.add(new Cat());
cats2.add(new Cat());
cats3.add(new Cat());
}
showElement(cats1.iterator());
showElement(cats2.iterator());
showElement(cats3.iterator());
}
}
/*
output:
Cat: 0 Cat: 3 Cat: 6
Cat: 1 Cat: 4 Cat: 7
Cat: 2 Cat: 8 Cat: 5
*/

showElement() A method does not contain any information about the sequence type it traverses , So that shows you Iterator The benefits of : Ability to separate the operation of traversing a sequence from the underlying structure of the sequence . It can also be said that , Iterators unify access to containers .

As can be seen from the frame diagram of the container ,Collection Is the root interface that describes the commonality of all sequence containers . But in C++ in , The standard C++ There are no common base classes for other containers in the class library , The commonality between containers is achieved through iterators . stay Java in , Bind the two methods together , Realization Collection At the same time to achieve iterator() Method ( Returns the iterator for the container ).

ListIterator

ListIterator It's a much stronger one Iterator subtypes , But it can only be used for all kinds of things List The interview of .Iterator You can only move forward , but ListIterator It allows us to move back and forth . It can also generate a previous and a subsequent index that points to the current position in the list relative to the iterator , And you can use set() Method replaces the last element it visited .remove() Method can delete the last element it accessed . We need to pay attention to , The last element in both places is just a call next() perhaps previous Returned element , That means call set()、remove() Before these two methods , Want to call first next() perhaps previous().

We need to pay attention to ListIterator Cursor position and in the sequence Iterator Different ,Iterator Is always in the call cursor position previous() The elements and calls that will be returned next() Will return between the elements . The length is n The list of iterator cursor positions has n+1 individual .

Use ListIterator Iterate forward and back over the list , And the use of set() Example of replacing a list element :

public class ListIteration {
public static void main(String[] args) {
List<Cat> catList = new ArrayList<>();
for(int i=0; i<5; i++) {
catList.add(new Cat());
} ListIterator<Cat> it = catList.listIterator();
System.out.println("CatNo.\t nextIndex\t previousIndex"); // Positive traversal
System.out.println(" Positive traversal :");
while (it.hasNext()) {
Cat cat = it.next();
System.out.println(cat+"\t\t"+it.nextIndex()+"\t\t"+it.previousIndex());
}
System.out.println(); System.out.println(" When the iterator cursor is at the end of the last element :");
ListIterator<Cat> it2 = catList.listIterator();
while (it2.hasNext()) {
Cat cat = it2.next();
System.out.println(cat+"\t\t"+it.nextIndex()+"\t\t"+it.previousIndex());
}
System.out.println(); // Reverse traversal
System.out.println(" Reverse traversal ");
while(it.hasPrevious()) {
Cat cat = it.previous();
System.out.println(cat+"\t\t"+it.nextIndex()+"\t\t"+it.previousIndex());
}
System.out.println(); // Produces an iterator for the specified cursor position Replace forward from the second position in the list Cat object
System.out.println(" Replace forward from the second position in the list Cat object ");
it = catList.listIterator(2);
while(it.hasNext()) {
it.next();
it.set(new Cat());
}
System.out.println(catList);
}
}
/*
CatNo. nextIndex previousIndex
Positive traversal :
Cat: 0 1 0
Cat: 1 2 1
Cat: 2 3 2
Cat: 3 4 3
Cat: 4 5 4 When the iterator cursor is at the end of the last element :
Cat: 0 5 4
Cat: 1 5 4
Cat: 2 5 4
Cat: 3 5 4
Cat: 4 5 4 Reverse traversal
Cat: 4 4 3
Cat: 3 3 2
Cat: 2 2 1
Cat: 1 1 0
Cat: 0 0 -1 Replace forward from the second position in the list Cat object
[Cat: 0, Cat: 1, Cat: 5, Cat: 6, Cat: 7]
*/

foreach With the iterator

foreach Syntax can be used for more than just arrays , It can also be used for anything Collection object . The reason it can be used in Collection object , Because Java SE5 Introduced Iterable Interface , The interface contains one that can be generated Iterator Of iterator() Method , also Iterable Interface is foreach Used to move in a sequence . therefore , If any implementations are created Iterable Class , You can use it for both foreach among . We need to pay attention to , Arrays can be used foreach Grammar traversal , But that doesn't mean that the array is Iterable Of .

Implement an iterable class , Use foreach Methods through

public class IterableClass implements Iterable<String>{
private String[] words = ("This is happy day.").split(" ");
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
private int index = 0;
// Determine if there is another element
public boolean hasNext() {
return index < words.length;
}
// Returns the next element
public String next() {
return words[index++];
}
public void remove() { //remove You don't have to implement
throw new UnsupportedOperationException();
}
};
} public static void main(String[] args) {
//foreach Syntax traversal is implemented Iterable The class of the interface
for(String s : new IterableClass()) {
System.out.println(s);
}
}
}
/*
This
is
happy
day.
*/

Summary

Yes Java The container class library is briefly introduced , The specific container usage and implementation will be covered in a later blog post . This article focuses on the introduction Iterator, It unifies access to containers , But there is still a bit of doubt :foreach The syntax traverses the container because the container is implemented Iterable Why , But you can also go through groups , Arrays are not Iterable Of . that foreach What is the basis for traversing groups ? The question has not yet been answered properly , If you have any ideas, please leave a message , Be deeply grateful !

Reference resources :

Java Collection series directory (Catedory): https://www.cnblogs.com/skywang12345/p/3323085.html

《Java Programming idea 》 The Fourth Edition

Java—— Container class library framework analysis of more related articles

  1. java Containers --- Collection summary

    Think about why you want to introduce the concept of container ? Java There are many ways to save objects ( It should be a reference to an object ), For example, the most efficient way to save a set of objects when using arrays , If you want to save a set of basic types of data , This method is also recommended , But we all know that arrays have fixed ...

  2. 【Java Conclusion six 】Java In the container ——Collection

    stay [Java Five lessons are summed up ]Java On the container —— In this blog post , I am right. Java Container class library has a preliminary understanding from a macro perspective Java Container Libraries . And in this blog post , I want to focus on Collection Containers ...

  3. 【Java Five lessons are summed up 】Java On the container —— Container exploration

    In mathematics, we have the concept of set , So called a set , It is to classify several objects into one or several different shapes and sizes .  In general , A set is a whole of things with certain characteristics , Or a collection of validation objects . The things or objects that make up a set are called elements or components ...

  4. Java Containers (list, set, map)

    java A simplified diagram of the container class library : ( The dotted box represents the interface , A solid wireframe represents a common class , The hollow arrow indicates that a specific class implements the interface , The solid arrow indicates that a class can generate the class object indicated by the arrow ) Inherit Collection The main ones are Set and Lis ...

  5. Java A comprehensive summary of container related knowledge

    Java The utility class library provides a fairly complete set of containers to help us solve many specific problems . Because I am a Android developer , A lot of Android development, including me , The best is ListView(RecycleView)+BaseAda ...

  6. Java Printing of containers

    Java There are two main types in a container class library , The difference between them is that each " Slot " Number of saved elements Clollection The container can only hold one element in the , Such containers include : List, It holds a set of elements in a specific order S ...

  7. Java Container summary

    Container summary Java Container kit frame diagram List,Set,Map Differences among the three List( A good helper against the order ): List Interface stores a set of non unique ( Multiple elements can refer to the same object ), Orderly objects Set( Focus on uniqueness ...

  8. 013- Concurrent programming -java.util.concurrent.locks And -AbstractQueuedSynchronizer- Framework for building locks and synchronization containers 、 Acquisition and release of exclusive lock and shared lock

    One . summary AbstractQueuedSynchronizer ( abbreviation AQS), be located java.util.concurrent.locks.AbstractQueuedSynchronizer It's a bag , A ...

  9. JAVA Learning notes -- First knowledge of container class library

    One . Preface JAVA Everything is an object , thus , Holding objects is particularly important . stay JAVA in , We can hold objects by creating a reference to them : HoldingObject holding; You can also create an array of objects to hold ...

Random recommendation

  1. There is no... In the registry Python3.5 Installation path pywin32-

    When installed pywin32 appear Python Version 3.5 required which was not found in the registry On the surface, there is no Python3.5 Installation path for ...

  2. CentOS The basic operation command of firewall

    CentOS Configure firewall operation instance ( Qi . stop . open . Closed port ): notes : The basic operation command of firewall : Query firewall status : [root@localhost ~]# service   iptables status< ...

  3. php Package file upload

    This is a common problem in projects , So encapsulate a , Share with you . One , Early stage configuration php.ini     If you upload more than php Configuration then $_POST perhaps $_FILES And so on are empty arrays , This is a pit , Because it wasn't at that time ...

  4. LA_4670_Dominating_Patterns_(AC automata +map)

    describe https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_pr ...

  5. 【 turn 】MyISAM and InnoDB difference

    InnoDB and MyISAM yes MySQL The two most commonly used table types , Each of these table types has its advantages and disadvantages , It depends on the application . The basic difference is :MyISAM Types do not support advanced processing such as transaction processing , and InnoDB Type of support .MyISAM The table of types emphasizes ...

  6. Minix3 Signal processing and analysis

    The structure of signal processing of process PM Process descriptors of all processes are stored in , In a process descriptor , There's a pointer , Point to one sigaction Structure an item in a two-dimensional array , Represents the operation of all signals in this process . One sigaction The structure contains letters ...

  7. Vboxmanage changes uuid The solution to error reporting

    My environment : Virtualbox 4.3.10 r93012 operating system :win7 problem :Virtualbox When using the copied virtual disk, you will be prompted uuid Conflict : Because a hard disk with ...

  8. HDU 3377 Plan

    Problem Description One day, Resty comes to an incredible world to seek Eve -- The origin of life. L ...

  9. jmeter Stress test notes - HTTP agreement

    One . The goal is Use jmeter Conduct HTTP Interface pressure test : Run in command line mode , Convenient in linux Environment is running : Two . Problems faced Support multi environment testing ( Development . test . Production environment ) Support user data . Number of threads . The number of cycles, etc. are configured at run time from ...

  10. LOJ-10104( Cut point +dfs)

    Topic link : Portal Ideas : At the same time, we find the logarithm of the unconnected points left after the cut point is deleted , After the completion of traversal, backtrack the number of statistical points , See the code for specific operation : Be careful : The result is long long type . #include<iostrea ...