A collection about Java

Java collections, also known as containers, are derived from two main interfaces: Collection and Map

The collection encapsulates basic data structures for better storage

The difference between the two interfaces is that Collection stores single data, while Map stores K-V key-value pairs

Collection

Let’s start with the topmost Collection, which specifies the basic methods of the Collection that are implemented by the implementation class.

And these methods are similar to the operation in the database, nothing more than **[add, delete, change, check]** and some operations on the whole collection (such as whether empty, size, etc.).

The underlying implementation class inherits these methods and adds new ones, resulting in different data structures that facilitate the best response to everyday situations.

Let’s start with the SubInterfaces layer

  • List is ordered and repeatable

  • Set is unordered and cannot be repeated

  • Query is a first-in, first-outFIFOData structure of

List

Lists are implemented by ArrayList and LinkedList

The biggest difference is the underlying data interface:

  • The underlying layer of an ArrayList is an array
  • The underlying LinkedList is a LinkedList

The biggest characteristic of array is random access storage. Physically, data is continuous

For the index query:

ArrayList is faster than LinkedList

Arrays can compute offsets, whereas linked lists can only iterate

For query object A:

ArrayList and LinkedList are similar

Arrays and lists can only be traversed

For most searches, an ArrayList is more efficient because it is an array

What about additions and deletions?

Because of the physical continuity of the array, the efficiency of adding and deleting elements at the end of the array is fine (except for adding and expanding elements), but the efficiency of moving elements at other places is low. Lists, on the other hand, are easy to add, quickly disconnect and connect to the next element. ** But add(int index, E E), remove(E E), remove(int index), you have to take into account the location of index, linked list to find the destination location is slower than array calculation offset. ** And arrays still have advantages in tail operations and large amounts of data.

conclusion

  1. Select ArrayList for most cases
  2. Add and delete the selection ArrayList at the end
  3. In other cases, if the time complexity is the same, choose ArrayList because memory usage is more efficient.

ArrayList expansion

Speaking of array scaling, let’s take a look at the scaling mechanism of ArrayList.

As you can see, ArrayList expands by moving the binary one bit to the right. The effect of moving the binary one bit to the right is to divide by two. The newly defined array is 1.5 times the size of the original array

Vector

Vector, like ArrayList, is based on arrays

But it’s now deprecated because it adds too much synchronized

Although it is thread-safe, the cost of thread-safe is low efficiency, so synchronIED is not currently added at the data structure level

So how is it different from an ArrayList?

capacity

We’ve seen that ArrayList expands by 1.5 times as many new arrays as old ones

What about Vector’s capacity expansion mechanism?

The Vector of capacity

It is easy to understand the capacityIncrement mechanism of vector because capacityIncrement is not defined, so by default the capacityIncrement is twice the size of the original array

Query&Deque

A Query is a linear data structure that goes in and out at one end, whereas a Deque is a linear data structure that goes in and out at both ends (simplex, full-duplex?).

Query

The Query API is somewhat special and can be roughly divided into throw exception groups and return value groups

If the queue is empty, things like remove() throw an exception, and poll() returns NULL

Both groups have the same function, so how to choose?

  • Same set of apis, consistent
  • If you need to throw an exception, you throw an exception, and vice versa

Waiting for updates…