Summary of the collection

What is a set

In general, a collection is a container used to hold data. Java collections can only store references to objects (that is, reference types). Each element in a collection is a reference variable, and the actual content is stored in the heap or method area. We can’t store the eight basic data types in Java, because the basic data types are allocated on the stack memory, and the data on the stack can be retrieved at any time, but because the eight basic data types have corresponding wrapper classes (objects), so when we store the data of the basic data types in the collection, Java automatically boxing the basic data types into their wrapper classes (such as int to Integer) and then storing reference types into collections.

The difference between collections and arrays

  • The types stored in arrays can only be basic data types or reference data types, and the types stored in collections can only be reference data types.

  • Arrays are static; an array instance has a fixed size and cannot change its capacity once created. Collections can be dynamically expanded in capacity and can be dynamically changed in size as needed.

  • When you initialize an array, you need to declare the data type to be stored in the array. Collections can be declared or not declared. When not declared, they default to type Object.

The difference between Collection and Collections

  • Java.util. Collection is a Collection interface (a top-level interface of the Collection class). It provides common interface methods for performing basic operations on collection objects. The Collection interface has many concrete implementations in Java class libraries. The meaning of the Collection interface is to provide the maximum unified operation mode for various specific collections.

  • Collections is a utility/helper class for Collections classes that provides a series of static methods for sorting, searching, and thread-safe operations on the elements of Collections.

The basic interface to the Java Collections Framework

  • Collection, Collection is one of the basic interfaces of the Collection framework in JavaNo direct implementation of this interface is provided.
  • MapA Map is an object that maps keys to values. A Map cannot contain duplicate keys. Each key can be mapped to one value at most.
  • List, List is a collection that can contain repeating elements
  • Set, a Set is a Set that cannot contain duplicate elements
  • Queue, the Queue interface is the implementation of the Queue structure in the data structure
  • 可迭代, the Iterable interface implementation class can iterate over the collection (such as Iterator)

The class diagram of the Collection interface

Map Interface class diagram

The Java Collections framework commonly uses collection classes

The List interface

The List interface has four main implementation classes: ArrayList, Vector, LinkedList, and CopyOnWriteArrayList

How do I iterate over a List

  • The for loop iterates
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}
Copy the code
  • Iterator Iterator
Iterator = list.iterator(); While (iterator.hasnext ()){system.out.println (iterator.next()); }Copy the code
  • ForEach loop traversal. ForEach uses Iterator to iterate over a List, but forEach is not allowed to delete or modify the elements of the List during the process.
for (Object o : list) {
    System.out.println(o);
}
Copy the code

Best practices

  • One is provided in the Java CollectionRandomAccess(random access) interface, if a collection implements the interface, then the collection supportsRandom fast accessArrayList, for example, implements this interface, so it supports random fast access, and its underlying traversal of collection elements is a for loop that is fast traversal or query time.
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Copy the code
  • In the Collections utility class, the binarySearch() binarySearch method is used to do this. When using this method to find elements, it first determines whether the collection implements a RandomAccess interface and therefore uses indexedBinarySearch().[index]The method is iteratorBinarySearch()[Iterator]Methods.
public class Collections { public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }}Copy the code

The difference between Iterator and ListIterator

When ArrayList iterates through a collection, the iterator() method that gets the iterator is the iterator() method of the List interface. Calling that method returns an iterator object. The Iterator () method for LinkedList is in the AbstractSequentialList abstract class Iterator() method, which in turn calls the listIterator() method of AbstractList abstract class to return a listIterator object.

The difference between Iterator and ListIterator

  • Iterators can iterate over sets and lists, while Listiterators can only be used to iterate over lists.
  • Both iterators and Listiterators can delete elements, but listiterators can modify elements over time, using the set() method. Iterator can only traverse, not modify.
  • Iterator traverses only one way[hasNext(), next() methods)], and the ListIterator can iterate in both directions (forward/backward)[hasPrevious(), previous() method].
  • The ListIterator interface inherits from the Iterator interface and then adds some additional functionality, such as adding an element, replacing an element, and getting the index position of the preceding or following elements.
  • ListIterator (); list.listiterator (); list.listiterator (int index); index is the location of the specified cursor.
  • Iterator: List. Iterator ()

ListIterator inherits the Iterator interface and adds its own methods

  • Void hasPrevious() determines whether the cursor is preceded by an element;
  • Object Previous () returns the element before the cursor, moving the cursor one bit forward.
  • Int nextIndex() returns the index position of the element after the cursor, starting at 0 and ending at N when traversing N elements;
  • Int previousIndex() returns the position of the element in front of the cursor, initially -1.
  • Void add(E) inserts an element before the cursor
  • Void set(E) updates the last element of the iterator to E, which is the element returned by the last call to next() or previous().
  • Void remove() removes the element from the last operation of the iterator
List<Integer> List = arrays.aslist (1,2,3,4); ListIterator<Integer> listItr = list.listIterator(); System.out.print(" from front to back: "); while(listItr.hasNext()) System.out.print(listItr.next()+ ""); System.out.print(" from back to front: "); while(listItr.hasPrevious()) System.out.print(listItr.previous());Copy the code

The fast-fail iterator

Iterator is a fast – fail iterators, when a thread through the iterators iterate through the elements in the List, another thread to modify or delete the elements in the List is not allowed (), abnormal Iterator ConcurrentModificationException motivated to stop this happening, Such iterators are called fast-fail iterators.

Exception to removing element using forEach loop edge traversal

ArrayList<Integer> list = new ArrayList<Integer>(); list.add(1); list.add(2); list.add(3); for (Integer ele : list) { list.remove(ele); } System.out.println(list.size()); / / throw Exception Exception in the thread "is the main" Java. Util. ConcurrentModificationException ats java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911) at java.util.ArrayList$Itr.next(ArrayList.java:861) at com.gjy.demo.collection.list.main(list.java:47)Copy the code

The compilation looks like this:

// After compilation: ArrayList<Integer> list = new ArrayList(); list.add(1); list.add(2); list.add(3); Iterator var2 = list.iterator(); while(var2.hasNext()) { Integer ele = (Integer)var2.next(); list.remove(ele); } System.out.println(list.size());Copy the code

In the compiled code, we can see that when we use the forEach loop to remove elements, the underlying iterator is used to iterate over elements, and the ArrayList is removed using the ArrayList remove method, so the iterator is not aware of the changes in the elements in the ArrayList. When an element is removed using the remove() method of the ArrayList, The checkForComodification() method is called the next time the iterator calls the next() method to check for concurrent changes in the iterator (determine whether modCount and expectedModCount are equal). When initializing the iterator, the value of modCount is assigned to the expectedModCount, and during the iteration, the expectedModCount = modCount equation does not hold as long as modCount changes]), If have, throw ConcurrentModificationException, prevent concurrent modification ArrayList object. Therefore, the correct edge traversal to remove elements should be implemented using the Iterator.

The Set interface

Collections that implement the Set interface are primarily used to store unordered (not necessarily in the same order) elements whose values cannot be repeated. The equality nature of an Object is determined by the hashCode value of the Object (when hashCode() is not overwritten, the call to the Object’s hashCode() method is calculated based on the memory address calculation of the Object). If you want two different objects to be considered equal, You must override the hashCode() and equals() methods of Object.

HashCode () and equals ()

  • If the objects are equal, then the Hashcode must also be the same. Hashcode in the Object class defaults to an int value calculated based on the memory address of the Object.
  • Two objects are equal. Return true for two equals methods
  • Two objects have the same Hashcode value, and they are not necessarily equal
  • If the equals method is overridden, the hashCode method must also be overridden
  • The default behavior of hashCode() is to generate unique values for objects on the heap. If hashCode() is not overridden, the two objects of the class will not be equal in any way (even if the two objects point to the same data).

The difference between Set and List

  • List and Set are inherited from the Collection interface.
  • List features: an ordered (elements are stored and retrieved in the same order) container, elements can be repeated, you can insert multiple NULL elements, elements have an index. Common implementation classes are ArrayList, LinkedList, and Vector.
  • Features of Set: an unordered (storage and retrieval order may be inconsistent) container, can not store duplicate elements, only allow to store a null element, must ensure element uniqueness. Common implementation classes for the Set interface are HashSet, LinkedHashSet, and TreeSet. List supports for loops, which are subscripts, iterators, butSet can only be iterated because it is unordered and cannot be subscripted to get the desired value.
  • Set: Retrieving elements is inefficient, while deleting and inserting elements is efficient. Inserting and deleting elements does not change the position of elements.
  • List: Like arrays, lists can grow dynamically (automatically expanding). Finding elements is efficient, but inserting or deleting elements is inefficient because it changes the position of other elements (such as ArrayList, Vector).

The Map interface

Unlike the List and Set interfaces, the Map interface does not inherit Collection. It is a two-column Set. It is a Set composed of a series of key and Value pairs and provides a mapping of key to Value. In the Map interface, the one-to-one mapping relationship between key and value is guaranteed, that is, a key corresponds to a value. It cannot have the same key value (unique) and does not require the keys to be ordered, but the values can be the same. Common Map implementation classes are HashMap, HashTable, and ConcurrentHashMap.

That’s the basic introduction to Java collections. In the next article, we’ll look at the common implementation classes of the List, Set, and Map interfaces, such as ArrayList, LinkedList, HashSet, HashMap, ConcurrentHashMap, and so on. Welcome to pay attention to the following content……..

Phase to recommend

  • Thread pool details
  • Introduction of synchronized
  • ThreadLocal, you got it?
  • Java Exception Mechanism
  • New JDK8 feature Stream
  • Classmate, are you familiar with volatile?