catalogue
Singleton set implementation class
Capacity expansion mechanism of ArrayList
Find the location of the element
Judge whether the list is empty
Double instance collection implementation class
Capacity expansion mechanism of HashMap
Returns the Set collection of keys
Returns the Set set of key value pair mappings
The element itself implements comparison rules
Comparison rules are implemented through comparators
Foregoing
In life, we generally use containers to store objects. In Java, we also use "containers" to hold management data. The array we learned earlier is a container that can be used to store objects or basic types of data. However, array based inflexibility means that its capacity should be defined in advance and cannot be expanded with the change of demand. Therefore, we need to strengthen large and flexible containers with expandable capacity at any time to store data. The content of this blog post is the container we want to learn today, and it also becomes a collection.
Structure of container
Singleton set
That is, a single data is stored as a unit
Collection is the root interface of a singleton collection, and its parent interface is iteratable (iterator interface, used to traverse data). There are two subclasses, List and Set. The data stored in List is ordered and repeatable, while the data stored in Set is disordered and non repeatable.
Double case set
That is, data is stored based on the structure of Key and Value
The elements of the container in the Map exist in pairs. Each element consists of a key and a value. The corresponding value can be found through the key. The collection in the Map cannot contain duplicate keys, and the values can be repeated. Each key can only correspond to one value.
The following only explains the commonly used implementation classes
Singleton set implementation class
List--ArrayList
The bottom layer of ArrayList is the storage implemented by array. It is characterized by high query efficiency, low addition and deletion efficiency and unsafe thread.
Capacity expansion mechanism of ArrayList
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}Comment on the third paragraph, shared empty array instance used for default sized empty instances We
distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. It shows that when an ArrayList is created in a parameterless construction mode, an empty array is actually initialized and assigned. The capacity is allocated only when the element is added to the array. That is, when the first element is added to the array, the capacity of the array is expanded to 10.
When it is judged that the capacity needs to be expanded again, the growth () method will be called, and the new capacity is 1.5 times of the old capacity
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //The value of the new capacity is defined here
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}Add element
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//The return value of calling this method is true
/*The first method is to add directly, which is to store the data in the location of the next index
The second method is to add at a selectable location, but the data is continuously connected, that is, there will be no empty data in the middle
ArrayList The index of starts at 0 */
public class Demo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("I");
System.out.println(list.toString());
}
}
/*The result of the compiler is: [i]
The result shows square brackets, which also confirms that the bottom layer of ArrayList is array */
public class Demo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("I");
list.add(1,"you");
System.out.println(list.toString());
}
}
/*The result of the compiler is: [I, you]
If you put the list Add (1, "you") is replaced by list The result of add (0, "you") compiler is: [you, me]
ArrayList The index of starts at 0
But if you change to list Add (2, "you"), the compiler will report an error
That proves that the data is connected continuously, that is, there can be no empty data in the middle */
Get element
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}Returns the element at the specified location in the ArrayList. If the index exceeds the range (index < 0 | index > = size ()), an IndexOutOfBoundsException exception will be reported
Replace element
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}Replace the element at the specified position with the element specified in this list. If the index exceeds the range (index < 0 | index > = size ()), an IndexOutOfBoundsException exception will be reported
Delete element
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}Delete the element at the specified position in this list, shift any subsequent element to the left (subtract an element from the index), and return the deleted element. If the index exceeds the range (index < 0 | index > = size ()), an IndexOutOfBoundsException exception will be reported.
Find the location of the element
Find the location where the element first appears: public int indexOf (Object o)
Returns the index of the specified element that appears for the first time in this list, or - 1 if the list does not contain the element.
Find the location where the element last appeared: public int lastIndexOf (Object o)
Returns the index of the last occurrence of the specified element in this list, or - 1 if the list does not contain the element.
Find element exists
public boolean contains(Object o)
Returns true if the list contains the specified element, otherwise false.
List size
public int size()
Returns the number of elements in this list.
Judge whether the list is empty
public boolean isEmpty()
Returns true if the list does not contain any elements, otherwise false.
Convert to array
public Object[] toArray()
Returns an array containing all the elements in this list in the appropriate order (from the first element to the last element). The returned array will be "safe" because this method allocates a new array, so the caller is free to modify the returned array.
clear list
public void clear()
Remove all elements from this list. When this call returns, the list will be empty.
Get list iterator
public Iterator<E> iterator()
Returns iterators for the elements in this list in the appropriate order.
//Iterator common usage
public class Demo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("I");
list.add(0,"you");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}List--Vector
The bottom layer of Vector is also implemented by array. The related methods are added with synchronized synchronization check, so it is thread safe, but the efficiency is low. The use of Vector is the same as that of ArrayList, so I won't explain it here.
List--LinkedList
The underlying layer of LinkedList is the storage realized by two-way linked list. It is characterized by low query efficiency, high addition and deletion efficiency and unsafe thread. There are more queue and stack methods than ArrayList. Please check them yourself.
The Set method is similar to the List method, but there is no index method, so I won't repeat it one by one below.
Set--HashSet
The underlying HashSet uses HashMap to store elements. The bottom layer of HashMap uses array and linked list to store elements. When elements are stored in the array, they are not stored orderly or randomly, but operate the hash value of elements to determine the position in the array.
When the hash values of the two elements are calculated to obtain the same position in the array, the equals() method of the element will be called to judge whether the two elements are the same. If the elements are the same, the element will not be added. If not, the element will be saved using a one-way linked list.
Set--TreeSet
TreeSet is a container that can sort elements. The bottom layer is actually implemented with TreeMap. A simplified version of TreeMap is maintained internally. Set elements are stored through keys. The stored elements need to be sorted internally in TreeSet. The sorting rules are explained in the TreeMap below.
Double instance collection implementation class
Map--HashMap
Hash table is used to store data at the bottom of HashMap. It is required that the key cannot be repeated. In case of repetition, the new value will replace the old value. It is characterized by high efficiency in addition, deletion, modification and query.
Capacity expansion mechanism of HashMap
To make a long story short, the array size is 16 by default. When the number of elements in HashMap exceeds 16 * 0.75 = 12 (threshold or boundary value), expand the size of the array to 2 * 16 = 32, and then recalculate the position of each element in the array.
Add element
public V put(K key, V value)
Associates the specified value with the specified key in this mapping, and replaces the old value if the mapping previously contained a key.
Delete element
public V remove(Object key)
Delete the mapping of the specified key from this mapping and return the value corresponding to the key (if any).
Does it contain a key
public boolean containsKey(Object key)
Returns true if the mapping contains a mapping for the specified key.
Does it contain a value
public boolean containsValue(Object value)
Returns true if the mapping maps one or more keys to the specified value.
Returns the Set collection of keys
public Set<K> keySet()
Returns the set view of the keys contained in this map. The set is supported by maps, so changes to the map are reflected in the set and vice versa. If the mapping is modified while iterating over the collection (except through the iterator's own remove operation), the result of the iteration is undefined. This group supports component removal, that is, the corresponding mapping from the mapping, via the iterator remove ， Set.remove, removeAll, retainAll, and clear operations. It does not support add or addAll operations.
Empty collection
public void clear()
Remove all mappings from this mapping. When this call returns, the mapping will be empty.
Returns the Set set of key value pair mappings
public Set<Map.Entry<K,V>> entrySet()
Returns the set view of the mappings contained in this mapping. The set is supported by maps, so changes to the map are reflected in the set and vice versa. If the mapping is modified during the iteration of the collection (except through the iterator's own remove operation or through the setValue operation on the mapping entry returned by the iterator), the result of the iteration is undefined. This group supports component removal, that is, the corresponding mapping from the mapping, via the iterator remove ， Set.remove, removeAll, retainAll, and clear operations. It does not support add or addAll operations. (this can be iterated through the foreach loop)
Map--TreeMap
The bottom layer of TreeMap is implemented based on red black tree, which is no different from HashMap in method. TreeMap can sort keys.
When using TreeMap, you need to give a collation:
- The element itself implements comparison rules
- Comparison rules are implemented through comparators
The element itself implements comparison rules
public class Person implements Comparable<Person>{
String name;
int age;
public Person() {
}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public int compareTo(Person o) {
if (this.age>o.age){
return 1;
}
if (this.age == o.age){
return this.name.compareTo(o.name);
}
return -1;
}
}
public class Test {
public static void main(String[] args) {
Map<Person,String> map=new TreeMap<>();
Person person1=new Person("datou",18);
Person person2=new Person("atou",18);
map.put(person1,person1.getName());
map.put(person2,person2.getName());
Set<Person> people = map.keySet();
for (Person person: people) {
System.out.print(person.name+"---"+person.age);
System.out.print("\t");
}
}
}
//The output result is atou --- 18 Datou --- 18
//If Person person2=new Person("atou",18) is replaced by Person person2=new Person("xtou",18);
//The output result is datou---18 xtou---18
Comparison rules are implemented through comparators
public class Person{
String name;
int age;
public Person() {
}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}public class PersonComparator implements Comparator<Person> {
@Override
public int compare(Person o1, Person o2) {
if (o1.getAge()>o2.getAge()){
return 1;
}
if (o1.getAge()==o2.getAge()){
return o1.getName().compareTo(o2.getName());
}
return -1;
}
}
public class Test {
public static void main(String[] args) {
Map<Person,String> map=new TreeMap<>(new PersonComparator());
Person person1=new Person("datou",18);
Person person2=new Person("atou",18);
map.put(person1,person1.getName());
map.put(person2,person2.getName());
Set<Person> people = map.keySet();
for (Person person: people) {
System.out.print(person.name+"---"+person.age);
System.out.print("\t");
}
}
}
//The output result is atou --- 18 Datou --- 18
//If Person person2=new Person("atou",18) is replaced by Person person2=new Person("xtou",18);
//The output result is datou---18 xtou---18