[TOC]
Java provides three types of collections:
List: a Set of ordered lists Set: a Set that is guaranteed to have no duplicate elements Map: a Set of maps that are searched by key-value
Java has always accessed collections in a uniform way, iterators, whose most obvious benefit is that you don’t need to know how the elements inside the collection are stored. Typical usage is as follows:
Iterator it = collection.iterator(); While (it.hasNext()) {Objectobj it= it.next(); // Get the next element}Copy the codeA List.
There are two kinds of lists: the basic ArrayList, which has the advantage of randomly accessing elements, and the more powerful LinkedList, which is not designed for fast random access. Common classes that implement the List interface are LinkedList, ArrayList, Vector, and Stack.
LinkedList class:
LinkedList implements the List interface, allowing null elements. Sequential access is optimized so that inserts and deletions into the middle of the List are inexpensive, and random access is relatively slow. It also has the following methods: The addFirst(), addLast(), getFirst(), getLast(), removeFirst(), and removeLast() methods (not defined in any interface or base class) enable the LinkedList to be used as a stack, A queue or deque.
Note: There is no synchronization method for LinkedList. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronization when creating a List of the List: a List List = Collections. SynchronizedList (newLinkedList (…). );
ArrayList class:
Like LinkedList, ArrayList is unsynchronized.
import java.util.*; public class Test{ public static void main(String[] args) { List<String> list=new ArrayList<String>(); list.add("Hello"); list.add("World"); list.add("HAHAHAHA"); For (int I =0; For (int I =0; i<list.size(); I++) of the form system.out.println (STR); String[] strArray=new String[list.size()]; list.toArray(strArray); for(int i=0; i<strArray.length; For (String STR :strArray) {system.out.println (strArray[I]); Iterator<String> ite=list.iterator(); While (ite.hasnext ())// determine the value after the next element {system.out.println (ite.next()); }}}Copy the codeThe Vector class:
Vector is very similar to ArrayList, but Vector is synchronous. The Iterator created by Vector is the same interface as the Iterator created by ArrayList. However, because Vector is synchronized, when an Iterator is created and being used, another thread changes the state of the Vector (for example, adding or removing elements), Then call Iterator methods will throw ConcurrentModificationException, so you must catch the exception.
The Stack class
Stack inherits from Vector and implements a last-in, first-out Stack. Stack provides five additional methods that allow a Vector to be used as a Stack. The basic push and POP methods, as well as peek to get the element at the top of the stack, empty to see if the stack is empty, and search to see where an element is in the stack. The Stack is empty right after it is created.
List to array
Integer[] array = list.toArray(new Integer[list.size()]); Integer[] array = list.toArray(Integer[]::new);
An array is converted to a List
Arrays.aslist (T…) Method converts an array to a List.
List object comparison
Instead of checking whether two elements are equal internally by ==, the equals() method is used to check whether two elements are equal.
When looking up elements in a List, the implementation class of the List uses the equals() method to compare whether two elements are equal. Therefore, the inserted elements must properly override equals(). Strings, integers, and so on provided by the Java standard library already override equals().
Write equals() to check with objects.equals ().
If you are not looking for elements in the List, you do not need to override the equals() method
public class ListCompare { @Test public void test() { List<Person> list = Arrays.asList( new Person("Xiao", "Ming", 18), new Person("Xiao", "Hong", 25), new Person("Bob", "Smith", 20) ); boolean exist = list.contains(new Person("Bob", "Smith", 20)); System.out.println(exist ? "Test successful!" : "Test failed! ); } class Person { String firstName; String lastName; int age; public Person(String firstName, String lastName, int age) { this.firstName = firstName; this.lastName = lastName; this.age = age; } public boolean equals(Object o) { if (o instanceof Person) { Person p = (Person) o; return this.age == p.age && Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName); } return false; }}}Copy the code2. Map interface
Note that Map does not inherit the Collection interface; Map provides key-to-value mapping. A Map cannot contain the same key, and each key can Map only one value. The Map interface provides views of three collections. The contents of a Map can be thought of as a set of keys, a set of values, or a set of key-value mappings.
The put(Object key, Object value) method adds a “value “(what you want) and a” key “associated with the” value “(use it to find). The get(Object key) method returns the “value” associated with the given “key”. ContainsKey () and containsValue() can be used to test whether a Map contains a “key” or “value”.
HashTable class
Hashtable inherits the Map interface and implements a key-value mapping Hashtable. Any non-null object can be used as a key or value. Hashtable is synchronous and thread-safe. Put (key, value) is used to add data, and Get (key) is used to retrieve data. These two basic operations are implemented using Java hashCode, and the time cost is constant.
Since an object serving as a key determines the position of its corresponding value by evaluating its hash function, any object serving as a key must implement the hashCode and equals methods. The hashCode and equals methods inherit from the root Object class. Be careful if you use a custom class as the key. According to the definition of the hash function, if two objects are the same, i.e. obj1.equals(obj2)=true, then their hashCode must be the same. However, if two objects are different, their hashcodes may not be different. If the hashcodes of two different objects are the same, this phenomenon is called conflict, which will lead to an increase in the time cost of operating the hash table. Therefore, try to define hashCode() method to speed up the operation of the hash table.
To avoid the unexpected result of manipulating the hash table if the same object has different Hashcodes (expect the GET method to return NULL), keep in mind that you should overwrite both equals and hashCode methods, not just one.
public class MapCompare { @Test public void test() { Map<Person, String> map = new HashMap<>(); map.put(new Person("xiao", "Ming", 18), "nice"); map.put(new Person("xiao", "hong", 20), "hong"); System.out.println("get:"+map.get(new Person("xiao", "hong", 20))); } class Person { String firstName; String lastName; int age; public Person(String firstName, String lastName, int age) { this.firstName = firstName; this.lastName = lastName; this.age = age; } @Override public boolean equals(Object o) { if (o instanceof Person) { Person p = (Person) o; return this.age == p.age && Objects.equals(this.firstName, p.firstName) && Objects.equals(this.lastName, p.lastName); } return false; } @Override public int hashCode() { return Objects.hash(firstName, lastName, age); }}}Copy the codeA HashMap class
HashMap is similar to Hashtable except that HashMap is asynchronous and allows NULL, that is, null value and NULL key. But when a HashMap is treated as a Collection (the values() method returns a Collection), its iteration suboperation time is proportional to the capacity of the HashMap. Therefore, do not set the initialization capacity of the HashMap too high or the load factor too low if the performance of iterative operations is important.
import java.util.*; public class Test{ public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>(); map.put("1", "value1"); map.put("2", "value2"); map.put("3", "value3"); Println (" Map. KeySet traverses key and value: "); for (String key : map.keySet()) { System.out.println("key= "+ key + " and value= " + map.get(key)); } // The second system.out.println (" iterator over keys and values via map.entryset: "); Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<String, String> entry = it.next(); System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); } system.out.println (" traversal key and value through map.entrySet "); for (Map.Entry<String, String> entry : map.entrySet()) { System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue()); } // system.out.println (" Map. Values () traverses all values but not keys "); for (String v : map.values()) { System.out.println("value= " + v); }}}Copy the codeIf the key object is of type enum, you can use the Java Collection library’s EnumMap, which stores the value in a very compact array and locates the index of the internal array directly based on the enum key. It does not need to calculate hashCode(). And no extra space to waste.
Let’s take the enumeration type DayOfWeek as an example and make a “translation” for it:
public class Main { public static void main(String[] args) { Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class); Map. put(dayofweek. MONDAY, "MONDAY "); Map. Put (DayOfWeek.TUESDAY, "TUESDAY "); Map. put(Dayofweek. WEDNESDAY, "WEDNESDAY "); Map. Put (DayOfWeek.THURSDAY, "THURSDAY "); Map. Put (DayOfWeek.FRIDAY, "FRIDAY "); Map. Put (DayOfWeek.SATURDAY, "SATURDAY "); Map. Put (DayOfWeek.SUNDAY, "SUNDAY "); System.out.println(map); System.out.println(map.get(DayOfWeek.MONDAY)); }}Copy the codeTreeMap class
Based on red-black tree data results. When a “key” or “key-value pair” is viewed, they are sorted (the order is determined by the Comparabel or Comparator). The nice thing about TreeMap is that you get sorted results. TreeMap is the only Map with a subMap() method that returns a subtree.
SortedMap traverses in strict accordance with the order of Key. The most commonly used implementation class is TreeMap. The Key that is a SortedMap must implement the Comparable interface or be passed in as a Comparator; The comparison logic must be implemented strictly according to the compare() specification, or TreeMap will not work properly.
public class TreeMapTest { @Test public void test() { // Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() { // public int compare(Student p1, Student p2) { //// if (p1.score == p2.score) { //// return 0; //// } //// return p1.score > p2.score ? 1:1; // return -Integer.compare(p1.score, p2.score); / / / /}}); Map<Student, Integer> map = new TreeMap<>(); map.put(new Student("Tom", 77), 1); map.put(new Student("Bob", 66), 2); map.put(new Student("Lily", 99), 3); for (Student key : map.keySet()) { System.out.println(key); } System.out.println(map.get(new Student("Bob", 66))); // null? } static class Student implements Comparable { public String name; public int score; Student(String name, int score) { this.name = name; this.score = score; } public String toString() { return String.format("{%s: score=%d}", name, score); } @Override public int compareTo(Object o) { Student student = (Student) o; return -Integer.compare(this.score, student.score); }}}Copy the codeWeakHashMap class
WeakHashMap is an improved HashMap that implements “weak references” to keys so that if a key is no longer referenced externally, it can be reclaimed by GC.
3. Set interface
A Set is a Collection that contains no duplicate elements, i.e. any two elements E1 and e2 have E1.equals (e2) = false, so a Set has at most one null element.
Obviously, the constructor of a Set has a constraint that the Collection argument passed in cannot contain duplicate elements.
Note that Mutable objects must be manipulated carefully. This can cause problems if mutable elements in a Set change their state causing object.equals (Object)=true.
public class Main {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("pear");
set.add("orange");
for (String s : set) {
System.out.println(s);
}
}
}
banana
orange
apple
pear
Copy the codeHashSet class:
The implementation of HashSet is based on HashMap, which is used to store all elements in the underlying HashSet. Sets designed for quick lookup. Objects stored in a HashSet must define hashCode(). HashCode and equal() are used by HashMap, and since sorting is not required, only positioning and uniqueness are concerned. HashCode is used to calculate hash values. Hash values are used to determine hash table indexes. An index in a hash table stores a linked list.
When put is used, an Entry is added to the list if the hash table does not contain an Entry. If the hash table contains an Entry, the value in the Entry is replaced and the old value is returned.
When overwriting key hashCode() and equal(), be careful not to associate them with mutable attributes, otherwise the attribute will change hashCode and equal will be false, and you won’t be able to find it in the Map and such objects can’t be freed because they can’t find it, This becomes an invalid reference (equivalent to a memory leak).
LinkedHashSet class
A subclass of the HashSet class that has the speed of a HashSet query and internally maintains the order of elements (insertion order) using a linked list. Thus, when iterators are used to traverse a Set, the results are displayed in the order in which the elements were inserted.
The TreeSet class
TreeSet is implemented by TreeMap. The TreeSet collection class is an ordered collection whose elements are sorted in ascending order, with the default being natural order. That is, object elements in TreeSet need to implement the Comparable interface. TreeSet, like the HashSet class, does not have a get() method to retrieve the elements in the list, so it can only be retrieved through iterator methods.
Comparable. The Comparator can be specified when TreeMap is created. The Comparator.compare is used when TreeMap is created. If a Comparator is not specified when created, the key.compareTo() method is used, which requires the key to implement the Comparable interface.
TreeMap is implemented using the Tree data structure, so using the Compare interface does the job.
/** * In chat software, when the sender sends a message, it will automatically resend the message after the network timeout occurs. Therefore, the receiver may receive a duplicate message and needs to resend the message before displaying it to the user. Practice using Set to remove duplicate messages: * */ public class TreeSetText { @Test public void test() { List<Message> received = Arrays.asList( new Message(1, "Hello!" ), new Message(2, "Did you get paid?" ), new Message(2, "Did you get paid?" ), new Message(3, "Where to eat?" ), new Message(3, "Where to eat?" ), new Message(4, "Bye") ); List<Message> displayMessages = process(received); for (Message message : displayMessages) { System.out.println(message.text); } } static List<Message> process(List<Message> received) { Set messageSet = new TreeSet<>(new Comparator<Message>() { @Override public int compare(Message o1, Message o2) { return Integer.compare(o1.sequence, o2.sequence); }}); messageSet.addAll(received); return new ArrayList<>(messageSet); } static class Message { public final int sequence; public final String text; public Message(int sequence, String text) { this.sequence = sequence; this.text = text; }}}Copy the codeThe Queue interface
The Queue interface is at the same level as the List and Set interface, which inherit from the Collection interface. LinkedList implements the Queue interface. The Queue interface narrow access to the methods of the LinkedList (that is, if the argument type in the method is Queue, only the methods defined by the Queue interface can be accessed, not the non-queue methods of the LinkedList) so that only appropriate methods can be used. Avoid adding NULL to the queue.
| methods | instructions | note |
|---|---|---|
| add | Add an element | Queue is full, IIIegaISlabEepeplian is thrown |
| remove | Removes and returns the queue header element | If the queue is empty, oSuchElementException is thrown |
| element | Returns the element at the head of the queue | If the queue is empty, NoSuchElementException is thrown |
| offer | Add an element and return true | If the queue is full, return false |
| poll | Removes and returns the queue header element | If the queue is empty, null is returned |
| peek | Returns the element at the head of the queue | If the queue is empty, null is returned |
| put | Add an element | If the queue is full, it is blocked |
| take | Removes and returns the queue header element | If the queue is empty, it blocks |
Remove, Element, Offer, poll, peek are actually Queue interfaces.
Note that queues cannot be instantiated directly. In Java programming, queues were originally implemented as linkedLists. Queue QE = new LinkedList();
LinkedList implements both the List interface and the Queue interface, but when we use it, we get a reference to the List if we think of it as a List, we get a reference to the Queue if we think of it as a Queue, always writing code for abstract programming, You can greatly improve the quality of your code.
List<String> List = new LinkedList<>(); // This is a Queue: Queue<String> Queue = new LinkedList<>();Copy the codeNote: This implementation is not synchronous. If multiple threads access a linked list at the same time, and at least one of them structurally modifies the list, it must guarantee external synchronization. (Structural modification is any operation that adds or removes one or more elements; Setting the value of an element alone is not a structural change. This is typically done by synchronizing objects that naturally encapsulate the list.
Deque If the conditions are relaxed to allow both ends to enter and both ends to exit, this kind of Queue is called a Double Ended Queue, or Deque.
Java collections provide an interface Deque to implement a double-endian queue.
- Add an element to the end or head of a team: addLast()/offerLast()/addFirst()/offerFirst();
- Get elements from the head/tail of the queue and remove them: removeFirst()/pollFirst()/removeLast()/pollLast();
- GetFirst ()/peekFirst()/getLast()/peekLast();
- Always call xxxFirst()/xxxLast() to distinguish it from the Queue method;
- Avoid adding NULL to the queue.
public class Main { public static void main(String[] args) { Deque<String> deque = new LinkedList<>(); deque.offerLast("A"); // A deque.offerLast("B"); // A <- B deque.offerFirst("C"); // C <- A <- B System.out.println(deque.pollFirst()); // A < -b system.out.println (deque.polllast ()); // B, A system.out.println (deque.pollfirst ()); // A System.out.println(deque.pollFirst()); // null } }Copy the codeStack
In Java, we can use a Deque to implement the function of Stack:
- Push (E)/addFirst(E);
- Pop ()/removeFirst();
- Fetching top element without popping: peek()/peekFirst().
When using the Deque as a Stack, be careful to call only the push()/pop()/peek() methods, not addFirst()/removeFirst()/peekFirst() methods, so the code is clearer.
ArrayBlockingQueue class
A bounded queue supported by arrays. An array-based blocking loop queue that sorts elements on a first-in, first-out basis.
LinkedBlockingQueue class
An optional bounded queue supported by linked nodes. A linked list-based queue that sorts elements first in, first out.
PriorityBlockingQueue class
An unbounded priority queue supported by a priority heap. PriorityBlockingQueue is a repackaging of PriorityQueue, based on the heap data structure, and PriorityQueue has no capacity limit, like ArrayList, so it is not blocked when put on a preferentially blocking queue. But since the resource is exhausted, an attempt to perform the add operation may result in an OutOfMemoryError), but if the queue is empty, the fetch operation take will block, so its retrieve operation take is blocked. In addition, the elements entering the queue must be comparative.
DelayQueue
A time-based scheduling queue supported by a priority heap. (implemented based on PriorityQueue) is an unbounded blocking queue that holds Delayed elements, which can only be retrieved when the delay expires. The head of the queue is the Delayed element that has been Delayed the longest after the delay expires. If neither delay has expired, the queue has no head and poll returns NULL. An expiration occurs when the getDelay(timeUnit.nanoseconds) method of an element returns a value less than or equal to zero, and poll removes the element. This queue does not allow null elements.
SynchronousQueue
A simple rendezvous mechanism utilizing the BlockingQueue interface. The SynchronousQueue class is the simplest. It has no internal capacity. It’s like a hand-to-hand mechanism between threads. A producer that adds an element to the queue waits for a consumer in another thread. When the consumer is present, the element is passed directly between the consumer and the producer and is never added to the blocking queue.
conclusion
What is the difference between a List/Set and a Map in Java?
A List, like an array, can grow dynamically, depending on the size of the data actually stored. Find the elements with high efficiency, low insert removing efficiency, because can lead to other elements position change < ArrayList implementation class, LinkedList, the Vector >.
The Set interface instance stores unordered, non-repeating data. The List interface instance stores ordered, repeatable elements. Set retrieval is inefficient, and deletion and insertion are efficient, and insertion and deletion do not cause element positions to change.
The Map also keeps a copy of each element, but this is based on keys. The Map also has a built-in sort, so it doesn’t care about the order in which elements are added. If the order in which elements are added is important to the program design, use LinkedHashSet or LinkedHashMap.
How to choose a collection class?
1. To be thread-safe, use Vector and Hashtable
2. Do not require thread safety, use ArrayList, LinkedList, HashMap
3. To obtain key and value values, use HashMap and Hashtable
4. If the data volume is large and thread safe, use Vector
If you’re dealing with stacks, queues, etc., you should use a List, you should use a LinkedList for quickly inserting and deleting elements, and you should use an ArrayList for quickly randomly accessing elements.
If the program is in a single-threaded environment, or access occurs only in a single thread, consider asynchronous classes, which are more efficient, and use synchronized classes if multiple threads may be working on a class at the same time.
Pay special attention to the operation on the hash table, and the object as the key overwrites the equals and hashCode methods properly.
Try to return the interface rather than the actual type, such as a List rather than an ArrayList, so that if you need to change the ArrayList to a LinkedList later, the client code doesn’t change. This is for abstract programming.
Solution processing of data structures and algorithms (array, linked list, stack tree, tree, graph)
Sparse arrays (keys are integers) can be used for data sizes up to a thousand levels, and ArrayMaps (keys are objects) are less efficient than HashMaps but less memory-saving. An ArrayMap uses arrays and arrays. One array stores the hash value of a key and one array stores the value. Therefore, if the data is large, the efficiency is relatively low. A HashMap takes the form of an array, a linked list, or a red-black tree. The array stores the hash value of the key, the linked list stores the value, and if the number of values exceeds 8, the value is converted to a red-black tree.
Why is SparseArray recommended instead of HashMap?
SparseArray three features of even group, delete O(1), binary search why save? In order to avoid excessive hash collisions, the HashMap introduces a load factor. For example, the load factor uses the default value of 0.75, which means that when capacity reaches 75%, it starts to expand, meaning that 25% of the space must be wasted without storing data. SparseArray uses the array to the last space. Why is the complexity so low? SparseArray makes two optimizations: 1. Introduce the DELETE flag since the underlying use of arrays, what are the disadvantages of arrays? Deleting data requires moving elements. SparseArray does no data migration for array deletion and introduces the DELETE flag to achieve O(1) time complexity during deletion. The DELETE flag is cleaned only when size() and PUT () calls need to be expanded. 2. Optimize the append element SparseArray provides an append() method to optimize the append. This method determines whether the append key is greater than the largest value in the array. If so, it appends to the end of the array. Otherwise, put() is used to insert the mKey array.
Because sparseArray avoids automatic boxing of keys (int to INTEGER), it is implemented internally with two arrays; One store keys and one store values; Relatively speaking, the performance is faster, internal use of compression to save memory space; SparseArray instead of HashMap is best stored in quantities of less than 1000. The key must be an int to replace a HashMap
SparseArray traversal method 1.
SparseArray<UserBean> mUserArray = new SparseArray<>(); //SparseArrayr for (int I = 0; i < mUserArray.size(); i++) { int key = mUserArray.keyAt(i); UserBean user = mUserArray.get(key); Log.e("key = " + key, user.toString()); }Copy the codeMethod 2. No key value required:
SparseArray<UserBean> mUserArray = new SparseArray<>(); For (int I = 0; i < mUserArray.size(); i++) { UserBean user = mUserArray.valueAt(i); Log.e(" no key ", user.tostring ()); }Copy the codeSparseArray has some useful methods similar to those found in HashMap, such as:
put(int key, E value) get(int key) get(int key, E valueIfKeyNotFound) Delete (int key) removeAt(int index) keyAt(int Index) valueAt(int index) etc.Copy the codeAndroid to encapsulate SparseIntArray SparseBooleanArray, SparseLongArray, etc., using method and SparseArray are the same, as long as you will use the Map, you will use SparseArray.
ArrayMap
ArrayMap is a <key,value> mapped data structure. It is designed with more memory optimization in mind. It uses two arrays to store data, one for the hash value of the key and the other for the value. Dichotomy is also used to sort keys from small to large. When adding, deleting and searching data, the dichotomy search method is first used to obtain the corresponding index, and then the operations such as adding, searching and deleting are carried out through index. Therefore, the application scenario is the same as SparseArray. Then its performance degrades by at least 50%.
Add data: public V put(K key, V value) Obtain data: public V get(Object key) Delete data: Public V Remove (Object Key) special method which is the same as SparseArray but also has two more convenient methods to get data:
public K keyAt(int index) public V valueAt(int index)
Summary: SparseArray and ArrayMap are similar, which one to use? Assume that the amount of data is within 1000:
1. If the key is already of type int, use SparseArray because it avoids automatic boxing. If the key is of type long, it also provides a LongSparseArray to ensure that the key is of type long
2. If the key type is any other type, ArrayMap is used
CopyOnWriteArrayList:
A CopyOnWrite container is a container for copying while writing. The common understanding is that when we add elements to a container, we do not directly add to the current container, but first Copy the current container, Copy the new container, then add elements to the new container, after adding elements, the original container reference to the new container. The advantage of this is that we can do concurrent reads to the CopyOnWrite container without locking, since no elements are being added to the current container. So the CopyOnWrite container is also an idea of read-write separation, reading and writing different containers. The CopyOnWrite concurrent container is used in concurrent scenarios where more reads and less writes are required. Such as whitelist, blacklist and other scenarios. CopyOnWrite has two drawbacks: memory footprint. Because CopyOnWrite write replication mechanism, so at the time of writing, in the memory will be stationed at the same time two objects of memory, the old and new writing object (note: just copy the reference in the container when copy, just at the time of writing will create a new object is added to the new container, the old container object is still in use, So there are two pieces of object memory. Data consistency issues. The CopyOnWrite container only guarantees final data consistency, not real-time data consistency. So if you want to write data that is immediately readable, don’t use the CopyOnWrite container. When the add or remove operation is not complete, get still retrieves the elements of the old array.
Summary of concurrent queue ConcurrentLinkedQueue and blocking queue LinkedBlockingQueue usage scenarios
The JDK provides two sets of implementations for concurrent queues: a high-performance queue represented by ConcurrentLinkedQueue and a BlockingQueue represented by the BlockingQueue interface. Both inherit from Queue and are thread-safe, allowing concurrent programming. Benefits of applying blocking queues: Multiple threads operating on a common queue require no additional synchronization, and the queue automatically balances the load, so that fast processing is blocked, reducing the speed gap between the two. When many threads share access to a common collection, ConcurrentLinkedQueue is an appropriate choice. LinkedBlockingQueue is used for task queues and provides a waiting method for BlockingQueue. BlockingQueue is basically implemented based on locks. ConcurrentLinkedQueue is used for message queues. The cas-based lock-free technology does not need to use locks for every operation, so the scalability performance is better.
Single producer, single consumer LinkedBlockingqueue Multiple producers, single consumer LinkedBlockingqueue ConcurrentLinkedQueue multiple producers, ConcurrentLinkedQueue leeeyou.gitbooks. IO /java-36/con…
ConcurrentLinkedQueue use:
Blog.csdn.net/liyantianmi… Poll () takes the element and removes it from the queue, and returns null size if the queue is empty: returns the number of elements in the queue. Integer.max_value is returned if the number of elements in this queue is greater than integer.max_value. Be careful that, unlike most collections, this method is not a fixed-time operation. Due to the asynchronous nature of these queues, determining the current number of elements requires a traversal that takes O(n) time. Note 1: the.size() of ConcurrentLinkedQueue traverses the collection slowly, so avoid using size as much as possible. If the queue isEmpty, use isEmpty() instead of size. Q1: Does using the ConcurrentLinkedQueue class mean we don’t need to do any synchronization or locking ourselves? If you use the functions provided directly, such as queue.add(obj); Or queue. Poll (obj); So we don’t have to do any synchronization ourselves. But if the operation is non-atomic, for example:
if(! queue.isEmpty()) { queue.poll(obj); } It is difficult to guarantee that this queue has not been modified by another thread after isEmpty() was called and before poll(). So in this case, we still need to synchronize ourselves: see
ConcurrentHashMap indicates the ConcurrentHashMap
ConcurrentHashMap is a two-level hash table. Under a total hash table, there are several subhash tables.
Put method: 1. Hash the input Key to obtain the Hash value. Locate the Segment object using the hash value. 3. Obtain the reentrant lock. Locate the array in the Segment using the hash value. 5. Insert or overwrite the HashEntry object. 6. Release the lock.
ConcurrentHashMap size, how to solve the consistency problem? The ConcurrentHashMap Size method is a nested loop with the following logic: 1. Iterate through all segments. 2. Add the Segment elements together. 3. Add up the number of Segment changes. 4. Check whether the total number of changes of all segments is greater than the total number of changes of the last Segment. If yes, it indicates that the number of attempts is changed during the statistics process. If not. If no modification is made, the statistics end. 5. If the number of Segment attempts exceeds the threshold, lock each Segment and collect statistics again. 6. Check again whether the total number of changes of all segments is greater than the total number of changes of the previous Segment. Since it’s locked, the number must be the same as last time. 7. Release the lock. The statistics collection is complete.
public int size() { // Try a few times to get accurate count. On failure due to // continuous async changes in table, resort to locking. final Segment<K,V>[] segments = this.segments; int size; boolean overflow; // true if size overflows 32 bits long sum; // sum of modCounts long last = 0L; // previous sum int retries = -1; // first iteration isn't retry try { for (;;) { if (retries++ == RETRIES_BEFORE_LOCK) { for (int j = 0; j < segments.length; ++j) ensureSegment(j).lock(); // force creation } sum = 0L; size = 0; overflow = false; for (int j = 0; j < segments.length; ++j) { Segment<K,V> seg = segmentAt(segments, j); if (seg ! = null) { sum += seg.modCount; int c = seg.count; if (c < 0 || (size += c) < 0) overflow = true; } } if (sum == last) break; last = sum; } } finally { if (retries > RETRIES_BEFORE_LOCK) { for (int j = 0; j < segments.length; ++j) segmentAt(segments, j).unlock(); } } return overflow ? Integer.MAX_VALUE : size; }Copy the codeWhy is it designed this way? This kind of thinking is the same as optimistic lock pessimistic lock idea. To try not to lock all segments, first assume optimistically that there will be no modification during the Size process. When a certain number of attempts are made, a pessimistic lock is used to lock all segments to ensure strong consistency.
Mp.weixin.qq.com/s?__biz=MzI…
HashMap? ConcurrentHashMap? I believe no one will be stumped after reading this article
ArrayList, and linkedlist
1.ArrayList is a data structure based on dynamic array, while LinkedList is a data structure based on LinkedList.
2. ArrayList is definitely better than LinkedList for random access to GET and set because LinkedList moves the pointer.
3. LinkedList is superior to add and remove because ArrayList moves data. It depends on the actual situation. If you insert or delete a single piece of data, ArrayList is faster than LinkedList. But when data is randomly inserted and deleted in bulk, LinkedList is much faster than ArrayList. That’s because each time an ArrayList inserts a piece of data, it moves the insertion point and all subsequent data.
Hashtable, Hashmap
1. Historical reasons: Hashtable is based on the old Dictionary class, and HashMap is an implementation of the Map interface introduced in Java1.2.
2. Synchronization: Hashtable is thread-safe, that is, synchronous, and there are methods in this class that ensure that objects in Hashtable are thread-safe. A HashMap, on the other hand, is thread asynchronous, so objects in a HashMap are not thread-safe. Because synchronization requirements affect the efficiency of execution, using HashMap is a good choice if you don’t need thread-safe collections to avoid unnecessary performance overhead due to synchronization, thereby improving efficiency.
3. A HashMap allows you to use null values as keys or values for entries in a table, but a Hashtable cannot contain null values.
A HashMap and TreeMap
1. A HashMap does a quick lookup of its contents using Hashcode, whereas TreeMap elements are all in some fixed order, and you should use TreeMap if you want to get an ordered result (the order of elements in a HashMap is not fixed).
2. HashMap is the best choice for inserting, deleting, and positioning elements into a Map. ** But TreeMap is better if you want to traverse the keys in natural or custom order. ** The key classes required to be added using HashMap explicitly define the implementation of hashCode() and equals(). There is no tuning option for this TreeMap because the tree is always in equilibrium.
HashSet with TreeSet
HashSet is based on the Hash algorithm and performs better than TreeSet. HashSet is usually used, and TreeSet is used only when we need to sort the elements in it.
The use of Iterator
Regardless of the actual type of the Collection, it supports an iterator() method that returns an iterator that can be used to access each element of the Collection one by one.
The Iterator pattern is the standard access method for iterating through collection classes. It abstracts the access logic from the different types of collection classes, thus avoiding exposing the internal structure of the collection to the client.
For example, if you don’t use Iterator, the way to traverse an array is to use an index: for(inti=0; i<array.size(); i++) {.. get(i)… }
A LinkedList must be accessed using a while loop: while((e=e.next())! =null){… e.data()… }
The access code and the collection itself are tightly coupled, and the access logic cannot be separated from the collection class and the client code. Each collection corresponds to a traversal method, and the client code cannot be reused.
To make matters worse, if you ever need to replace the ArrayList with a LinkedList, the original client code will have to be completely rewritten.
To solve these problems, the Iterator pattern always iterates over the collection using the same logic:
for(Iteratorit=c.iterater(); it.hasNext();) { ...}
Each collection class may return a different type of Iterator. Array may return an ArrayIterator, Set may return a SetIterator, and Tree may return a TreeIterator. But they all implement the Iterator interface. The client doesn’t care what kind of Iterator it is, it just needs to get the Iterator interface, and that’s the power of object orientation.
The contents of the collection (except for Iterator’s remove() method) must not be changed in order for the traversal process to complete smoothly, so the principle of reliable traversal is to use the collection in only one thread, or to synchronize the traversal code across multiple threads.
Collection c=new ArrayList(); c.add("abc"); c.add("xyz"); for(Iterator it=c.iterator(); it.hasNext();) { Strings=(String)it.next(); System.out.println(s); }Copy the codeIf you replace the ArrayList with a LinkedList or Vector in the first line of code, the rest of the code can compile without changing a single line and still function the same way. This is the principle for abstract programming: the least dependence on concrete classes.
The use of the Collections
Collections can sort a List. Because sorting directly changes the position of the List elements, we must pass in the mutable List:
public class Main { public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("apple"); list.add("pear"); list.add("orange"); // Sort before: system.out.println (list); Collections.sort(list); // Sort: system.out.println (list); }}Copy the codeCollections provides the shuffling algorithm, which passes in an ordered List that randomly shuffles the order of the elements inside the List, the equivalent of asking a computer to shuffle cards:
public class Main { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i=0; i<10; i++) { list.add(i); } // before: system.out.println (list); Collections.shuffle(list); System.out.println(list); }}Copy the codeCollections also provides a set of methods for encapsulating mutable Collections into immutable Collections:
List unmodifiableList(List<? Extends T> list) encapsulates an immutable Set: Set unmodifiableSet(Set<? Extends T> set) encapsulates an immutable Map: Map<K, V> unmodifiableMap(Map<? extends K, ? Extends V> m) this encapsulation is actually achieved by creating a proxy object that intercepts all modification methods. Let’s look at the results:
public class Main { public static void main(String[] args) { List<String> mutable = new ArrayList<>(); mutable.add("apple"); mutable.add("pear"); / / into the immutable collection: a List < String > immutable = Collections. UnmodifiableList (mutable); immutable.add("orange"); // UnsupportedOperationException! }}Copy the codeCollective learning links (check them out sometime) : geek-docs.com/java/java-c…