This is the eighth day of my participation in the August Challenge. For details, see:August is more challenging

A collection of classification

Collection interface (single-column Collection)

  • List interface: The feature inherits from the Collection, which is ordered and repeatable

    • LinkedList interface implementation class: LinkedList implementation, suitable for insert and delete type LinkedList, thread unsafe
    • ArrayList interface implementation class: array implementation, suitable for random access type linked lists, thread unsafe
    • Vector interface implementation class: array implementation, thread safe.

  • Set interface: The feature inherits from collection, and the arrangement is unordered and unrepeatable

    • HashSet interface implementation class: suitable for storing elements in hash tables (arrays).

      • LinkedHashSet inherits HashSet to implement Set, and the list maintains the insertion order of elements.

    • TreeSet interface implementation class: binary tree implementation, elements ordered.

Map interface (dual column set)

  • HashTable interface implementation class, thread safe.

  • HashMap interface implementation class, thread unsafe.

    • LinkedHashMap bidirectional linked list and hash implementation class.
    • WeakHashMap

  • The TreeMap red-black tree sorts all the keys.

  • IdentifyHashMap

conclusion

The difference between Map and List and Set

  • Map is the interface, while List and Set are subinterfaces of Collection
  • Map is a two-column set, while List and set are single-column sets

The difference between List and set

  • A List is an ordered, repeatable collection that can be queried by index.
  • Sets are unordered, unrepeatable, and have no index. Of course, the implementation of a Set, LinkedHshSet, maintains the insertion order through a linked list.

The List collection

Ordered list, allowing duplicate elements; Its implementation classes consist of three:

  • ArrayList: Array implementation, query fast, add and delete slow, lightweight; (Thread unsafe)
  • LinkedList: two-way circular LinkedList implementation, add and delete fast, query slow (thread unsafe)
  • Vector: array implementation, heavyweight (thread-safe, less used)

Four ways to traverse the List

public class ListTest { public static void main(String[] args) { List<Integer> list=new ArrayList<>(); list.add(1); list.add(2); list.add(3); For (int I = 0; int I = 0; i <list.size() ; i++) { System.out.println(list.get(i)); For (Integer elem:list){system.out.println (elem); Iterator<Integer> integerIterator=list.iterator(); while (integerIterator.hasNext()){ Integer elem=integerIterator.next(); System.out.println(elem); Array.foreach ((elem)-> system.out.println (elem)); List. ForEach (system.out ::println); }}Copy the code

Automatic ArrayList expansion mechanism

Source:

private void add(E e, Object[] elementData, Int s) {if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; } private Object[] grow() { return grow(size + 1); } private Object[] grow(int minCapacity) {int oldCapacity = elementData.length; / / if the current capacity greater than 0 or array is not DEFAULTCAPACITY_EMPTY_ELEMENTDATA if (oldCapacity > 0 | | elementData! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity >> 1 /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity); // If the array is DEFAULTCAPACITY_EMPTY_ELEMENTDATA (capacity = 0), } else {return elementData = new Object[math.max (DEFAULT_CAPACITY, minCapacity)]; }}Copy the code

Expansion can be divided into two cases:

In the first case, when the capacity of an ArrayList is 0, the capacity of an element needs to be expanded. The three constructor methods create an ArrayList with a slightly different capacity:

1. No parameter is required. The capacity of an ArrayList is 0 after the first element is added.

If the parameter is 0, the capacity of the created ArrayList is 0. If the first element is added, the capacity of the ArrayList is 1. In this case, the ArrayList is full.

When the list is empty, the capacity of the ArrayList is 0. When the first element is added, the capacity of the ArrayList is 1. In this case, the ArrayList is full.

In the second case, when the capacity of the ArrayList is greater than 0 and the ArrayList is full, add elements in this case and do normal expansion, by 1.5 times each time.

Threadsafe solution for ArrayList

  1. Victor for; List list = new Vector<>();
  1. Use Colections: List the List = Collections. SynchronizedList (new ArrayList);
  1. List list = CopyOnWriteArrayList<>();

LinkedList

Using bidirectional circular list implementation, can be used to implement stack, queue, bidirectional queue, but you need to follow the implementation of the characteristics of the implementation structure, such as the implementation of the stack can not provide the top of the stack element out of the stack method, the implementation of the column needs to follow the first-in, first-out principle.

vector

Similar to ArrayList, but the heavyweight component is thread-safe and suitable for high concurrency scenarios.

List common methods

  • Void add(int index, Object element) : adds the Object element to the position index
  • Boolean addAll(int index, Collection Collection) : Adds all elements in the container Collection after the index position
  • Object get(int index) : Retrieves the element whose subscript is index
  • Int indexOf(Object Element) : finds the first occurrence of an Object element in the List
  • Int lastIndexOf(Object Element) : finds the last position of the Object element in the List
  • Object remove(int index) : deletes the element at the index position
  • ListIterator ListIterator (int startIndex) : Returns a ListIterator that starts at startIndex
  • List subList(int fromIndex, int toIndex) : returns a subList(int fromIndex, int toIndex) : returns an element from fromIndex to toIndex