Why use collections

Arrays and collections are containers for storing data in Java

Arrays can also store data, so why collections

Take a look at the disadvantages of arrays

  1. Once the size of an array is determined, it cannot be changed and is not suitable for dynamic storage

  2. The array provides a limited number of methods

Collections can solve the above disadvantages of arrays

Java internally provides us with collection classes, which can store arbitrary objects, whose length can be changed, and which have numerous methods for manipulating data

Also note:

Arrays can store primitive data types as well as reference types

Collections can only store reference types (base data types are automatically boxed as reference types)

Classification of sets

(Photo source: Cainiao Tutorial)

The Java Collections framework mainly consists of two types of containers: A Collection, which stores a Collection of elements, and a Map

  • Collection
    • List
      • ArrarList
      • LinkedList
      • Vector
    • Set
      • HashSet
        • LinkedHashSet
      • TreeSet
  • Map
    • HashMap
      • LinkedHashMap
    • TreeMap
    • ConcurrentHashMap
    • Hashtable

Collection common methods

Public Boolean add(E E) // Add the given object to the current collection. Public void clear()// Clears all elements in the collection. Public Boolean remove(E E)// Remove the given object from the current collection. Public Boolean Contains (Object obj)// Determines whether the current collection contains the given Object. Public Boolean isEmpty()// check whether the set isEmpty. Public int size()// Returns the number of elements in the collection. Public Object[] toArray()// Stores the elements of the collection into an arrayCopy the code

The List collection

The List collection stores data that is ordered and repeatable

ArrayList

  • Advantages: The underlying data structure is an array, fast query, slow add and delete.
  • Disadvantages: Thread insecurity, high efficiency

Take a look at the source code analysis of ArrayList (how to dynamically expand it) :

  1. Properties of ArrayList:

As you can see, the default capacity definition DEFAULT_CAPACITY is 10

EMPTY_ELEMENTDATA and DEFAULTCAPACITY_EMPTY_ELEMENTDATA are defined as two empty arrays of Object[]. When the Arraylist is empty, the empty array is assigned to the Arraylist. One is returned when the user specifies a capacity of 0.

ElementData is responsible for holding the elements added to the ArrayList

Size indicates the actual size of the ArrayList

  1. ArrayList constructor:

Parameterized constructor: Returns EMPTY_ELEMENTDATA when the capacity is initialized to 0

Constructor with no arguments: DEFAULTCAPACITY_EMPTY_ELEMENTDATA is returned by default

  1. Add method: Dynamic capacity expansion is implemented in Add

The add method performs the following steps:

Check to see if you need to expand, insert elements into elementData, and the array length increases

Vector

  • Advantages: The underlying data structure is an array, fast query, slow add and delete.
  • Disadvantages: Thread safety, low efficiency

The biggest difference from ArrayList is that Vector is synchronous

Of course, if ArrayList needs to be synchronized, you can use the methods in Collections to do so

List list =Collcetions.synchronizedList(new ArrayList());
Copy the code

LinkedList

  • Advantages: The underlying data structure is linked list, slow query, fast add and delete.
  • Disadvantages: Thread insecurity, high efficiency

As you can see, LinkedList is implemented through a two-way LinkedList

The Set collection

The data stored in a Set is unordered and non-repeatable

Unordered: Not randomness. The data stored in the underlying array is added not in the order of the array index, but in accordance with the hash value of the array. (Although elements are placed in no order, their position in the set is determined by the element’s HashCode, which is actually fixed.)

public void test1(){ Set set=new HashSet(); set.add(123); set.add("AA"); set.add(new People("Jack",20)); Iterator iterator=set.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code

Non-repeatability: Ensure that added elements cannot return true when judged by equals()

When you add a new element to an array, you find the hash of the new element, you compute the hash of the new element in the underlying array, you compare the hash of the new element with the hash of the previous element,

If the hash value is different, the two elements are different and the element is added successfully. If the hash values are the same, call equals() to compare the two elements and return true

        set.add(123);
        set.add(123);
Copy the code

HashSet

  • Thread unsafe, efficient, allows null elements to be stored

Hash table + red-black tree

A HashSet guarantees element uniqueness by overwriting the hashCode() and equals() methods of the elements, not by overwriting them.

LinkedHashSet

LinkedHashSet: Threads are insecure and efficient.

The underlying data structure is hash table + linked list

As data is added, two references are maintained for each data, recording the data before and after this data

TreeSet can sort by the specified attribute of the added element

The underlying data structure is a red-black tree

The data added to the TreeSet requires objects of the same class

Two sorts: Natural (implements the Comparable interface) Custom (Comparator)

Through the Collection

  1. The iterator

Collections inherit from Iterator, and any Collection can use Iterator to iterate over the Collection

The main methods in iterator:

  • HasNext (): Determines if there is a next element

  • Next (): Moves the pointer down to return the element at the set position after the move

        Iterator iterator =coll.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
Copy the code
  1. Enhanced for loop
For (Collection object: collection)Copy the code

Map collections

The stored elements in a Map are two objects, one for the key and one for the value. Keys cannot be repeated, but values can be

Common methods in Map:

V put(K key, Remove () // Remove the specified key object clear() // Empty the set object Boolean isEmpty() // Return true if the length is 0 otherwise false Boolean ContainsKey (Object key) // Checks whether the set contains the specified key value GET (key) // Checks whether the key existsCopy the code

How to traverse a Map:

1. Remove all keys from map set and store them in set set. Set<K> keySet() returns the Set of all key objects, and gets the value of the key using the get method. Map.Entry Encapsulates the key-value mappings in the Map set into an Entry object. Map.Entry uses the getKey of map. Entry, GetValue gets its key and value.Copy the code

A:

public void test1(){ Map<String,Integer> map=new HashMap<String, Integer>(); map.put("a",20); map.put("b",19); map.put("c",18); // Method 1: Convert a map set to a set, Maptoset = map.keyset (); mapToSet = map.keyset (); Iterator iterator=maptoset.iterator(); while(iterator.hasNext()){ String key= (String) iterator.next(); Integer value=map.get(key); System.out.println("key="+key+" " +"value="+value); }}Copy the code

Method 2:

public void Test2(){ Map<String,Integer> map=new HashMap<String, Integer>(); map.put("a",20); map.put("b",19); map.put("c",18); // Method 2: Obtain all values through values Collection<Integer> value = map.values(); Iterator<Integer> integer=value.iterator(); while(integer.hasNext()){ Integer v = integer.next(); System.out.println(v); }}Copy the code

Three:

public void Test3(){ Map<String,Integer> map=new HashMap<String, Integer>(); map.put("a",20); map.put("b",19); map.put("c",18); EntrySet //Map.Entry contains key and value objects // Set Set of Map.Entry objects to be returned Set< map. Entry<String, Integer>> es= map.entryset (); Iterator<Map.Entry<String, Integer>> integer=es.iterator(); while(integer.hasNext()){ Map.Entry<String,Integer> me=integer.next(); String key=me.getKey(); Integer value=me.getValue(); System.out.println("key="+key+" value"+value); }}Copy the code

HashMap:

The bottom layer is: array + linked list + red black tree

Threads are not synchronized, they can store null keys, null values

To keep the keys unique, you need to override the hashCode and equals methods

HashTable:

Threads are synchronous and cannot store null keys, null values

TreeMap:

Bottom layer: red black tree

TreeMap can sort the keys in a Map collection

But you need to use Comparable or Comparator for comparison sorting

Method 1: The elements themselves are comparative

You need to implement the Comparable interface for objects stored at key locations, overriding the compareTo method

Mode two: Containers are comparative

Define a class that implements the interface Comparator and overrides the compare method

List, Set, and Map are all interfaces. The first two are inherited from the Collection interface. Map is an independent interface

The Collections utility class

Is a utility class that operates on Collection and Map

Common methods:

BinarySearch (Collection,Object)// Find the elements in the specified Collection, Reverse ()// Reverse the order of the elements in the set swap(List List,int I,int j)// Swap the position of the specified element index in the setCopy the code

Example: list inversion

        List coll =new ArrayList();
        coll.add(12);
        coll.add(10);
        coll.add(6);

        Collections.reverse(coll);
        System.out.println(coll);
Copy the code

Reference blog Map reference blog