Difference between a List and a Set
List and Set are inherited from Collection interface List: elements are placed in order, elements can be repeated,
The Set features: Elements are not placed in an order, and repeated elements are overwritten. (The position of the elements in a set is determined by the element’s HashCode. The position of the elements in a set is fixed. In addition, list supports for loop, that is, traversal by subscript, can also use iterators, but set can only use iteration, because it is unordered, can not use subscript to get the desired value. Set and List comparison Set: Inefficient to retrieve elements, efficient to delete and insert, insert and delete will not cause the element position change.
List: Like an array, a List can grow dynamically. It is efficient to find elements, but inefficient to insert and delete elements, because it causes other elements to change positions
How is a HashSet guaranteed not to repeat itself
When adding () elements to a HashSet, the existence of elements is determined not only by comparing hash values, but also by comparing them with the EQules method. The add () method in a HashSet uses the Add () method in a HashMap. HashSet HashSet HashSet
The key of a HashMap is unique, and as you can see from the code above, the value added to the HashSet is the key of the HashMap. So there is no duplication (HashMap compares keys to equals first by HashCode).
Is HashMap thread safe, and why not?
Not thread-safe;
If you have two threads, A and B, both inserting data, the hash code for these two different data is the same, and there is no other data in this bit. So both of these threads are going to go into the code that I marked 1 above. Assume A situation in which, thread A pass if judgment, this position does not have the hash conflict, entered the if statement, not insert data, then CPU resources to the thread B, thread A stop in the if statement, thread B judging the location without hash conflict (thread A haven’t insert), also entered the if statement, After thread B completes, thread A takes over, and now thread A inserts directly at that location without having to judge. At this point, you will notice that thread A overwrites the data inserted by thread B. An unsafe line condition has occurred. In a HashMap, hash collisions can be resolved using linked lists or red-black trees, but in multithreading, they can be overridden.
The above is a diagram to explain which may be more intuitive. As shown below, both threads add data in the same place, and the data added later overwrites the data added earlier.
If the above inserts are inserted into the linked list, such as two threads traversing to the last node, each adding data at the end of the list, then the next adding data thread will overwrite the previous adding data. the
Data inconsistencies can also occur during capacity expansion because capacity expansion is copying from one array to another.
Expansion process of HashMap
When adding elements to a container, the number of elements in the current container is judged to be greater than or equal to the threshold (know how to pronounce the threshold word). If you multiply the length of the current array by the value of the loading factor, you will automatically expand the array.
Resize is the process of adding more and more elements to a HashMap. When the array inside a HashMap cannot hold any more elements, the object needs to increase the array size to accommodate more elements. Of course, arrays in Java cannot be automatically expanded by replacing a small array with a new one, just as we use a small bucket of water to hold more water, so we have to replace it with a larger bucket.
HashMap hashMap=new HashMap(cap);
Cap =3, the capacity of hashMap is 4;
Cap =4, the capacity of hashMap is 4;
Cap =5, the capacity of hashMap is 8;
Cap =9, the capacity of hashMap is 16;
If cap is 2 to the n, the capacity is cap, otherwise it is greater than the first 2 to the n of cap.
What is the difference between HashMap 1.7 and 1.8?
A HashMap structure
In JDK1.7 and earlier, a HashMap is also called a hash list: based on an array and implementations of multiple lists, nodes are stored as linked lists when hash values conflict.
In JDK1.8, when the number of linked list nodes in the same hash value (Table element) is not less than 8, it will no longer be stored as a single linked list and will be adjusted to a red-black tree. This is the biggest difference between JDK7 and the HashMap implementation in JDK8.
The following analysis is based on JDk1.7.0_80 and JDK1.8.0_66
In the JDK1.7
Use an array of entries to store data, and use the hashcode module of the key to determine where the key will be placed in the array. If the HashCode is identical, or the result of the hashcode module is the same (Hash collision), Then these keys will be located in the same cell as the Entry array, and these keys will form a linked list.
In the case of a particularly bad Hashcode, for example, where all keys have the same Hashcode and the list can be very long, put/get operations may need to traverse the list, which means that the time complexity degrades to O(n) in the worst case.
In the JDK1.8
An array of nodes is used to store data, but this Node can be either a linked list or a red-black tree
- If the inserted keys have the same Hashcode, they will also be located in the same cell in the Node array.
- If there are no more than 8 keys in a cell, use the linked list structure to store them.
- If there are more than eight, the treeifyBin function is called to convert the list to a red-black tree.
So even if hashCode is exactly the same, because of the nature of red-black trees, it only takes order log n overhead to find a particular element
That is to say, the worst time complexity of put/get operations is O(log n) sounds great, but there is a limitation to really taking advantage of JDK1.8: If the Compare interface is not implemented, or implemented incorrectly (for example, all Compare methods return 0), then JDK1.8’s HashMap is actually slower than JDK1.7’s
The simple test data is as follows:
Put /get 1W pieces of the same hashcode object JDK1.7 to HashMap: Put 0.26s, get 0.55s JDK1.8 However, if the Compare interface is implemented correctly, the performance of HashMap in JDK1.8 is greatly improved. This time put/get 100W hashcode objects JDK1.8 (correctly implementing Compare interface) : put/get costs around 320 ms
final finally finalize final
- You can modify classes, variables, and methods. A modifier class indicates that the class cannot be inherited, a modifier method indicates that the method cannot be overridden, and a modifier variable table indicates that the variable is a constant and cannot be reassigned.
- Finally is usually used ina try-catch block. When handling an exception, the method finally is always executed, indicating that the block will be executed regardless of whether an exception occurs. It is used to store code that closes a resource.
- Finalize is a method of Object class, which is the parent of all classes. This method is generally called by garbage collector, when we call System.gc(), finalize() is called by garbage collector to collect garbage. The final determination of whether an object is recyclable.
Thank you for reading the article…
Focus on the author, I will occasionally share Java, Spring, MyBatis, Redis, Netty source code analysis, high concurrency, high performance, distributed, microservice architecture principle, JVM performance optimization, distributed architecture, BATJ interviews and other information…