Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>
1. Interface inheritance and Implementation
Set class stored in Java.util In bag , There are mainly 3 Kind of ：set( Set ）、list( List contains Queue） and map( mapping ).
1. Collection：Collection Is a collection List、Set、Queue The most basic interface of .
2. Iterator： iterator , You can traverse the data in a collection through an iterator
3. Map： Is the basic interface of mapping table
Java Of List Is a very common data type .List Is ordered Collection.Java List There are three implementation classes ：
Namely ArrayList、Vector and LinkedList.
2.1. ArrayList （ Array ）
ArrayList Is the most commonly used List Implementation class , The interior is implemented by array , It allows quick random access to elements . Count The disadvantage of a group is that there can be no interval between each element , Storage capacity needs to be increased when the array size is not enough , It's going to be clear Group data is copied to the new storage space . When from ArrayList When an element is inserted or deleted in the middle of , It's a logarithmic progression Row copy 、 Move 、 The cost is relatively high . therefore , It is suitable for random search and traversal , Not suitable for insertion and deletion .
2.2. Vector （ Array implementation 、 Thread synchronization ）
Vector And ArrayList equally , It's also implemented through arrays , The difference is It supports thread synchronization , That is, there is only one moment Threads can write Vector , Avoid inconsistency caused by multithreading writing at the same time , But synchronization is expensive , therefore , To visit it is better than to visit ArrayList slow .
2.3. LinkList （ Linked list ）
LinkedList It uses linked list structure to store data , Very suitable for dynamic data insertion and deletion , Random access and traversal speed comparison slow . in addition , It also provides List Method not defined in interface , Special for operation of header and footer elements , It can be used as a heap Stack 、 Queue and two way queue usage .
Set Focus on uniqueness , The system set is used to store unordered ( The order of storage and retrieval is not necessarily the same ) Elements , It can't be heavy complex . The essence of equality of objects is objects hashCode value （java Is the sequence number calculated based on the memory address of the object ） Judge Of , If you want two different objects to be considered equal , It must be covered Object Of hashCode Methods and equals Fang Law .
3.1.1. HashSet （ Hash surface ）
Hash table holds hashvalue .HashSet The order in which the elements are stored is not the order in which they were stored （ and List Obviously not Same as ）, It's stored in hash terms , So the data is also obtained by hash value . The hash value of an element is passed through the element's hashcode Method to get , HashSet First determine the hash value of two elements , If the hash value is the same , Then we'll compare equals Method , If equls The result is true ,HashSet As the same element . If equals by false It's not The same element .
Same hash value equals by false How are the elements of ？ That is, it is postponed under the same hash value （ We can think of hash values as The same element is placed in a hash bucket ）. That is, to store a column like a hash . Pictured 1 Express hashCode Different values condition ; chart 2 Express hashCode Same value , but equals Different situations .
HashSet adopt hashCode Value to determine the location of the element in memory . One hashCode Multiple elements can be stored in the location plain .
3.1.2. TreeSet （ Binary tree ）
1. TreeSet() Using the principle of binary tree add() Objects in the specified order （ Ascending 、 Descending ）, Every increase Adding an object will sort , Insert the object into the location specified by the binary tree .
2. Integer and String Objects can be defaulted TreeSet Sort , The object of custom class is not allowed , since The class you defined must implement Comparable Interface , And override the corresponding compareTo() function , Only when it can be made normally use .
3. Over writing compare() Function time , To return the corresponding value TreeSet Sort by certain rules
4. Compare the order of this object with the specified object . If the object is less than 、 Equal to or greater than the specified object , Then, the negative integer is returned Count 、 Zero or positive integer .
3.1.3. LinkHashSet （ HashSet+LinkedHashMap ）
about LinkedHashSet for , It is inherited from HashSet、 And based on LinkedHashMap To achieve . LinkedHashSet Bottom use LinkedHashMap To save all elements , It is inherited from HashSet, All of its methods In operation, it is related to HashSet identical , therefore LinkedHashSet The implementation of is very simple , Only four construction methods are provided , and By passing an identification parameter , Call the constructor of the parent class , Bottom structure a LinkedHashMap To achieve , In the related exercises Make up with the parent class HashSet Same operation for , Call the parent class directly HashSet It's a good way to do it .
4.1. HashMap （ Array + Linked list + Red and black trees ）
HashMap According to the hashCode Value store data , In most cases, you can navigate directly to its value , So it has a very fast Access speed of , But the order of traversal is uncertain . HashMap Only one record can have a key of null, Allow multiple entries The recorded value is null.HashMap Non-thread safety , That is, multiple threads can write at any time HashMap, It may lead to Inconsistent data . If thread safety needs to be met , It can be used Collections Of synchronizedMap Method makes HashMap Thread safe capability , Or use ConcurrentHashMap. You can use the following figure to introduce
HashMap Structure .
4.1.1. JAVA7 Realization
In the general direction ,HashMap It's an array , Then each element in the array is a one-way linked list . Above picture , Every green The entity of is nested class Entry Example ,Entry Contains four properties ： key, value, hash Value and for one-way list Of next.
1. capacity： Current array capacity , Always keep 2^n, Capacity expansion , The size of the expanded array is the current 2 times .
2. loadFactor： Load factor , The default is 0.75.
3. threshold： Threshold of capacity enlargement , be equal to capacity * loadFactor
4.1.2. JAVA8 Realization
Java8 Yes HashMap Some changes have been made , The biggest difference is the use of red and black trees , So it is made up of arrays + Linked list + Red and black Tree composition . according to Java7 HashMap Introduction to , You can know , When searching , according to hash Values can be quickly located in arrays Specific subscript , But later on , It needs to be compared one by one along the list to find what you need , Time complexity depends on Length of the list , by O(n) . To reduce this part of the cost , stay Java8 in , When the elements in the list exceed 8 After , Will convert the linked list to a red black tree , The time complexity can be reduced to O(logN).
4.2.1. Segment paragraph
ConcurrentHashMap and HashMap The idea is similar , But because it supports concurrent operations , So it's complicated some . Whole ConcurrentHashMap One by one Segment form ,Segment representative ” part “ or ” a section “ Of Meaning , So a lot of places describe it as a segment lock . Be careful , In writing , A lot of places are used “ Slot ” To represent a segment.
4.2.2. Thread safety （ Segment Inherit ReentrantLock Lock ）
The simple understanding is ,ConcurrentHashMap It's a Segment Array ,Segment By inheritance ReentrantLock To do the locking , So every time you need to lock it is one segment, So just make sure that every individual Segment It's thread safe , Global thread safety is achieved .
4.2.3. Parallelism （ Default 16 ）
concurrencyLevel： Parallel level 、 Concurrency number 、Segment Count , How to translate is not important , Understand it . The default is 16, in other words ConcurrentHashMap Yes 16 individual Segments , So theoretically , This is the time , At most, it can be supported at the same time a 16 Two threads write concurrently , As long as their operations are distributed separately Segment On . This value can be initialized at Wait to set to other values , But once it's initialized , It cannot be expanded . I'm going to go into each one Segment Inside , Actually Every Segment It's like HashMap, But it has to be thread safe , So it's going to be a little tricky to deal with .
4.2.4. Java8 Realization （ Red black tree introduced ）
Java8 Yes ConcurrentHashMap A lot of changes have been made ,Java8 Red black tree introduced .
4.3. HashTable （ Thread safety ）
Hashtable Is a legacy class , Common functions of many maps HashMap similar , The difference is that it inherits from Dictionary class , And it's thread safe , Only one thread can write at any time Hashtable, Less concurrent ConcurrentHashMap, because ConcurrentHashMap Section lock is introduced .Hashtable Not recommended in new code , No thread safety is required You can use HashMap Replace , It can be used when thread safety is required ConcurrentHashMap Replace .
4.4. TreeMap （ Sortable ）
TreeMap Realization SortedMap Interface , It can sort its saved records by key , The default is to sort keys in ascending order , You can also specify a comparator for sorting , When used Iterator Traverse TreeMap when , The records are sorted . If you use a sorted map , It is recommended to use TreeMap. In the use of TreeMap when ,key Must be realized Comparable Interface or under construction TreeMap Incoming custom
Comparator, Otherwise, it will be thrown at runtime java.lang.ClassCastException Exception of type .
Reference resources ： https://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html
4.5. LinkHashMap （ Record insertion order ）
LinkedHashMap yes HashMap A subclass of , Saved the insertion order of records , In use Iterator Traverse LinkedHashMap when , The first records must have been inserted first , It can also be constructed with parameters , Sort by access order .