Nine Java collections

Be reasonable. Let's study this chapter by type in the future. Now let's have a general look

Collections are divided into two systems: Collection and Map

Collection interface

​ List interface: elements are orderly and repeatable

​ ArrayList, LinkedList and Vector are the main implementation classes

​ Set interface: elements are out of order and cannot be repeated

​ HashSet，LinkedHashSet，TreeSet

Map interface: key value

​ HashMap, LinkedHashMap, TreeMap, Hashtable, Properties implementation class

1. Collection

​ Seriously, let's look at the documents...

1.1 methods in the interface

Collection coll=new ArrayList();
Collection coll1=Arrays.asList(1,2,3);

coll.add(123);
coll.add(new Person("jerry"));//When adding obj to the object of the Collectioin interface implementation class, the obj class needs to override the equals method
coll.add(new String("sdf"));
coll.add(false);
coll.remove(123);
coll.addAll(coll1);//Add all the elements in the collection coll1
coll.removeAll(coll1);//The intersection is deleted

coll.retaiAll(coll1);//For what? Check the documents
coll.equals(coll1);//Whether the contents are equal, rewritten
coll.toArray();
coll.iterator();//Returns the iterator interface traversed

2. Map

Map interface implementation relationship:

​ |------ The main implementation class of HashMap is thread unsafe. Both key and value can be null

​ |------ LinkedHashMap: On the basis of HashMap, a two-way pointer is added to point to the context of add

​ |----- Hashtable: too old. key and value cannot be null

​ |------ Properties are commonly used to process configuration files Both key and value are String types,

​ |------ TreeMap: sort according to a certain order of key s to realize sorting traversal

New structure: CurrentHashMap

2.1 bottom layer:

​ Key: unordered and non repeatable. Set storage is used. The class where the key is located should override the equals() method and hashcode() method

​ value: unordered, repeatable, stored using Collection

​ The key value is symmetric as an Entry: unordered and non repeatable. Set storage is used

2.2 underlying implementation principle

2.2. 1 in JDK7

HashMap map=new HashMap();
//After instantiation, the bottom layer creates a one-dimensional array Entry[] table with a length of 16

map.put(keyn,valuen);
//One of them:
//First, call the hashCode() method of the class where Key1 is located to calculate the hash value, and get the storage location in the Entry array through the hash function
//If the location data is empty, the key value is added successfully
//If it is not empty, compare the hash values of one or more data (linked list) existing in this location,
		//If the hash values are different, add at this location
		//If it is the same, compare the equals method of the class where the key is located,
				//If it is the same, the addition fails (the key already exists), but the values should be updated
				//If not, continue to compare other data at this location

//Capacity expansion will be involved in the process of adding. By default, the capacity will be doubled, the original data will be copied, and then the old data will be discarded

2.2. 2 in jdk8

new HashMap();//The bottom layer does not create an array, and it is no longer called Entry. It is renamed Node[] table
m.put(key1,value1);
//When the put method is called for the first time, the underlying layer creates a Node[] table with a length of 16

//The bottom layer in jdk7: array + linked list
//The bottom layer in jdk8: array + linked list + red black tree
	//When the length of the linked list of elements at an index position of the array is > 8 and the length of the current array is > 64, the linked list at this index position is changed to red black tree storage

//The critical factor is involved in capacity expansion. The default is 0.75, such as 16 * 0.75 = 12. When the array is filled with 12, capacity expansion begins

2.3 LinkedHashMap

2.4 TreMap

​ Add element: the Key must be an object created by the same class

2.5 Properties

//You need to throw an exception or try
Properties pros = new Properties();
FileInputStream fis = new FileInputStream(jdbc.properties);
pros.load(fis);
String name = pros.getProperty("name");
String pws= pros.getProperty("password");

3. Iterator iterator interface

3.1 iterator mode

Provides a method to access each element of a container object without exposing the internal details of the object

Every time the iterator() method is called, a new iterator will be returned!!!

Iterator iter= coll.iterator();//The default cursor precedes the first element
iter.hasNext();//Determine if there are any elements

iter.next();//Returns the next element in the iteration.
tier.remove();//It is different from the remove method in the collection, but the effect is almost the same..
//Note that the next method must be called before the remove method of the iterator is called every time. You can't remove continuously for many times, and an error will be reported

3.2 foreach

The bottom layer is an iterator

for(object obj:coll){
    
}
for(double d:Array){
    
}

4. Collection sub interface: List

​ List s are often used instead of arrays

​ List: elements are ordered, repeatable, indexed, and automatically expanded

​ Implementation classes of List interface: ArrayList, LinkedList, Vector

4.1 ArrayList

​ Threads are unsafe and efficient, so they are used a lot

​ What if ArrayList happens to be a critical resource one day? The Collections tool class provides a synchronizedlisti (List) method, which returns a thread safe List

​ Don't ask, just don't use Vetor

In JDK7

​ The bottom layer is an Object[] elementDate storage. Note that this is a fixed length array. The expansion is automatically completed by java. By default, the expansion is 1.5 times. Each time, the old one is discarded and a new one is created

​ It is recommended to use a constructor with parameters in development

ArrayList L= new ArrayList(initialCapacity=50)

In JDK8

​ No space is opened up when declaring. The first time the add method is used, the underlying array is created

​ The others are similar

4.2 LinkedList

​ The main difference from the above ArryList is the underlying implementation:

​ Using bidirectional linked list storage, the bottom layer implements a structure class similar to the linked list, which records the beginning and end positions of the linked list

​ For frequent insert and delete operations, the efficiency is super high

​ Just look directly at the in JDK8

LinkedList L = new LinkedList();

Each time add is placed at the end (the underlying layer calls the linkLast() method)

4.3 List interface method:

Pay attention to how the bottom is written.

List, as a sub interface of Collection, has more methods about index

For example, add, addAll, remove, subList, set, get, lastindexOf, indexOf

void add(int index,Object ele);//Insert element ele at index position
boolean addAll(int index,Collection eles);//Start from the index position and add the elements in eles one by one
Object get(int index);
int indexOf(Object odj);//Returns the position where the element first appears, not - 1
int lastIndexOf(Object obj);//Returns the last occurrence of obj in the collection
Object remove(int index);//Delete element
Object remove(Obejct obj);
Object set(int index,Obejct ele);//Sets the element at the specified location to ele
List subList(int fromIndex,int toIndex);//Returns the subset left open and right closed
int size();

Note that if an int type list is encountered or there is an int type in the list

Then remove(2) deletes index=2 by default

If you want to delete an element, you need to manually boxing, remove(new Integer(2));

Traversal:

//1
Iterator iter=list.iterator();
while(iter.hasNext()){
    sout(iter.next());
}
//2
for(Object: list){
    sout(obj);
}
//3
for(int i=0;i<list.size();i++){
    sout(list.get(i));
}

5. Collection sub interface: Set

​ The set interface has no additional methods

​ Duplicate elements are not allowed in the Set. To judge whether the quantity objects are the same, use the equals() method,

​ Common implementation classes: HashSet, LinkedHashSet, TreeSet

5.1 HashSet

​ The most common implementation classes basically use this

​ Unordered, non repeatable

​ If I new two identical objects, Set also thinks that they are not repeated because their hash es are different (although it is also judged by the equals method in the object class)

​ Thread unsafe, can store null value

​ What is the bottom layer of HashSet... It's a HashMap... Yes, the new HashMap in the construction method, and then value=null, which xx came up with

What does the bottom layer look like? The hash linked list in the data structure is a hash table. After each collision, the elements are directly linked below the conflict position of the table (after JDK8, J7 is inserted into the hash table, and then the previous elements are linked later)

5.1. 1 disordered and repeated interpretation

​ Take HashSet as an example:

​ 1. Disorder

​ Disorder= Random, at least every traversal can be the same

​ When adding, the hash hit is calculated according to the specific hash value of the data

​ 2. Repeat

​ For example, a HashSet add s two objects, both of which are new and have the same attributes. Set thinks these are two elements because the hash values are different

​ However, repeated judgment cannot be made by hash value, because the same location may be hit after hash calculation

​ If you override the equals() and hashcode methods, the two objects are one, and add succeeds only once

​ 3. add process

​ When adding, the duplicate is judged. Instead of comparing one by one, the hash value is calculated through the hashcode() method, and then the collision is detected. After each collision is detected, the equals method is used to judge whether the attributes are the same

​ Until a blank position is encountered, it can be inserted, or collide and return add failure with the same properties

5.2 LinkedHashSet

​ As a subclass of LinkedHashSet

​ So that the traversal can be in the order of addition (still unordered!!!)

What about the bottom layer? Based on the HashSet, each element has a pair of two-way pointers to indicate the location of the added element

5.3 TreeSets

​ Use red black tree (a kind of binary tree) to store

​ You can sort by the specified attribute of the added object

​ so, the element type is required to be consistent

​ Custom object classes: Requirements

​ a. Sort naturally, inherit the Comparable interface, rewrite the compare method, and compare whether the two elements are the same through the compare method (equals is no longer used)

​ b. Customize sorting, implement the Comparator interface, rewrite the compare method, and then TreeSet ts = new TreeSet(comparator object);