1. A hashmap, concurrenthashmap evolution process
A brief description (think of which to say which, specific need we search to add) :
A hashMap is an array and a linked list. Hash hash hash hash hash hash hash hash hash hash hash hash hash hash hash There is a flag that if your list length reaches 8, the data structure will become a red black tree. Of course, if the list length goes back to 8, the data structure will not immediately become a linked list, which will cause a waste of resources. It’s like 6. It’s a linked list. Key points:
The length of the array must exceed the default length of 64. If it does not exceed the default length of 64, expand the array first. At most times, the length of the array will exceed 64 and the node size will be larger than 8 before it becomes a red-black tree structure.
Interview questions (recall)
Q0: How does HashMap locate subscripts?
A: Get the Key, hash the Key, get A hash value, and then use the hash value to mod the capacity of the HashMap (not actually mod, but bitwise and, see Q6 for reasons), and finally get the subscript.
Q1: What does a HashMap consist of?
When the number of linked list nodes exceeds 8 (m default value), we start to use red black tree. Using red black tree is an optimal choice. Compared with other data structures, red black tree has higher query and insert efficiency. When the number of nodes in a red-black tree is less than 6 (the default value), the linked list is used again. Why are these two thresholds different? Mainly in order to prevent frequent nodes in the same numerical switching back and forth, an extreme example, singly linked list of nodes is 9 now, started to become red and black tree, then the red-black tree nodes into 8, will again become a singly linked list, then nodes into 9, will again become a red-black tree, it consumes waste, So simply stagger the two thresholds so that it’s “not so easy” to go back to a single-linked list after becoming a red-black tree, and it’s also “not so easy” to go back to a red-black tree.
Q2: Why doesn’t a Java HashMap store data in residuals?
A: In fact, the indexFor method of A HashMap uses bitwise summing with the capacity -1 of the HashMap, not %. (There is a hard requirement here, the capacity must be an exponential of 2, for the reason of Q6)
Q3: How does a HashMap insert a node into a list?
A: In jdK1.7, there is A header interpolation method, in jdK1.8, there is A tail interpolation method, in jdK1.7, there is A tail interpolation method, in jdK1.8, there is A tail interpolation method, in jdK1.7, there is A head interpolation method, in JDK1.8, there is A tail interpolation method. It is also because of the tail insertion method that the HashMap can determine whether there are duplicate nodes when inserting nodes.
Q4: What is the default capacity and load factor size for HashMap?
A: Before JDK1.7, the default capacity was 16 and the load factor was 0.75.
Q5: What is the actual size of a HashMap if you specify a capacity size of 10 when it is initialized?
A: 16, since the initialization function of HashMap specifies that the capacity is an exponential multiple of 2, namely, 2, 4, 8, 16, so when the specified capacity is 10, the actual capacity is 16.
A: Two reasons: 1. First of all, the effect of remainder and bit operation is the same, which will not exceed the set length to improve the calculation efficiency: because the binary of exponential times 2 has only one 1, while the binary of exponential times -1 of 2 has all 0s on the left and all 1s on the right. So if you do the bitwise sum with (2^n – 1), you’re going to get something in the range 0, (2^n – 1), and that’s going to be just right for the size of the hash table, because when you insert something into the hash table, you’re going to mod it to get the index. So if we use 2^n as the capacity size, we can replace the mod operation with bitwise and operation to improve computing efficiency. 2. It is convenient to distribute elements evenly when recalculating hash position after dynamic expansion: Since dynamic expansion is still an exponential of 2, the change in bitwise and operation values is the binary high +1, for example, from 16 to 32, the binary change is 0000 1111 (15) to 0001 1111 (31). Then this change will make the hash value of the elements of the expansion and need again after the bitwise and operator under the coordinate values or the same, or + 16 (i.e., move the location of the expansion after half capacity), so you can make the elements of the uniform on the same list (half) separated by expansion after the capacity of the distribution to the new hash table. (Note: Reason 2 (also known as advantage 2) was discovered and used after JDK1.8)
Q7: How to calculate the size of HashMap that meets expansion conditions (namely, expansion threshold)?
A: Capacity expansion threshold =min(capacity x load factor,MAXIMUM_CAPACITY+1). MAXIMUM_CAPACITY is very large, so the capacity x load factor is usually used.
Q8: Does HashMap support null elements?
A: Yes.
In the hash(obejject k) method of the HashMap, why not just mod the hash directly after calling k.hashcode (), but shift the hash right and xor?
A: If the HashMap capacity is small and the hash value is large, hash conflicts tend to increase. The underlying design of hashMap-based indexFor, assuming a capacity of 16, is to perform bitwise and bitwise operations on binary 0000 1111 (i.e., 15), so that the higher 28 bits of the hash binary are meaningless because they will be 0&, 0 and 0. So it’s easy to get more hash collisions. So h^=(h>>>20)^(h>>>12) in the hash(Obeject k) method after calling k.hashcode () to get the hash value; What’s the use? First, h>>>20 and H >>>12 shift the high binary of H to the low binary. The second xOR operation is to make use of the characteristics: the same as 0 different 1 principle, as far as possible to make H >>>20 and H >>>12 in the future do mod (bitwise and operation mode) to participate in the operation. To sum up, simply put, h^=(h>>>20)^(h>>>12); To reduce hash conflicts by making the higher bits of the binary hash value obtained by the k.hashcode () method participate in bitwise and operations as much as possible.
Q10: The same hash value, must the object be the same? Does the hash value have to be the same if the object is the same?
A: Not necessarily. A certain.
Q11: HashMap expansion and insert elements in order?
A: Before JDK1.7, you need to expand capacity and then insert capacity. After JDK1.8, you need to expand capacity and then insert capacity.
Q12: Why is HashMap expanded?
A: Improve the efficiency of get, PUT and other methods of HashMap, because if you do not expand the list, the linked list will become longer and longer, resulting in low efficiency of insert and query.
Q13: jdk1.8 introduces red-black tree, if the number of single-linked list nodes exceeds 8, will it be tree-like?
A: Not necessarily. It determines whether the current number of nodes is greater than the threshold for capacity expansion. If the capacity expansion condition is met, the system directly expands the capacity.
HashMap 1.7 based on head insertion will be flipped sequentially during expansion (there will be two Pointers head tail during expansion mainly because the two Pointers are pointing incorrectly), resulting in errors in multi-threaded situations. Not if you add on the tail, it’s basically the order flipped. After 1.8 comes tail insertion
Below to give you affixed part of my analysis of the source annotated
Determines whether the current array needs to be initialized. If key is null, put a null value into it. Calculate the Hashcode based on the key. Locate the bucket based on the calculated HashCode. If the bucket is a linked list, we need to traverse to determine whether the hashcode and key in the bucket are equal to the incoming key. If they are equal, we overwrite them and return the original value. If the bucket is empty, no data is stored in the current location. Add an Entry object to the current location. public V put(K key, V value) { 2 if (table == EMPTY_TABLE) { 3 inflateTable(threshold); 4 } 5 if (key == null) 6 return putForNullKey(value); 7 int hash = hash(key); 8 int i = indexFor(hash, table.length); 9 for (Entry<K,V> e = table[i]; e ! = null; e = e.next) { 10 Object k; 11 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 12 V oldValue = e.value; 13 e.value = value; 14 e.recordAccess(this); 15 return oldValue; 16 } 17 } 18 19 modCount++; 20 addEntry(hash, key, value, i); 21 return null; 22} When calling addEntry to write Entry, you need to determine whether expansion is required. Double the size if necessary, and rehash the current key and position it. CreateEntry passes the bucket with the current location to the new bucket, and if the bucket has a value, it forms a linked list of locations. void addEntry(int hash, K key, V value, int bucketIndex) { 2 if ((size >= threshold) && (null ! = table[bucketIndex])) { 3 resize(2 * table.length); 4 hash = (null ! = key) ? hash(key) : 0; 5 bucketIndex = indexFor(hash, table.length); 6 } 7 8 createEntry(hash, key, value, bucketIndex); 9 } 10 11 void createEntry(int hash, K key, V value, int bucketIndex) { 12 Entry<K,V> e = table[bucketIndex]; 13 table[bucketIndex] = new Entry<>(hash, key, value, e); 14 size++; Let's look at the get function: first, calculate the hashcode based on the key, and then locate the specific bucket. Determines whether the location is a linked list. Returns values based on keys and whether their hashcode is equal if they are not linked. For a linked list, you iterate until the key and hashcode are equal and return the value. Return null without retrieving anything. 1 public V get(Object key) { 2 if (key == null) 3 return getForNullKey(); 4 Entry<K,V> entry = getEntry(key); 5 6 return null == entry ? null : entry.getValue(); 7 } 8 9 final Entry<K,V> getEntry(Object key) { 10 if (size == 0) { 11 return null; 12 } 13 14 int hash = (key == null) ? 0 : hash(key); 15 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 16 e ! = null; 17 e = e.next) { 18 Object k; 19 if (e.hash == hash && 20 ((k = e.key) == key || (key ! = null && key.equals(k)))) 21 return e; 22 } 23 return null; 24} Base 1.8 does not know the implementation of 1.7 do you see the need for optimization? One obvious thing is that when Hash conflicts are severe, the linked list formed on the bucket becomes longer and longer, which makes the query less and less efficient. Time complexity is O(N). So 1.8 focuses on optimizing this query efficiency. 1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 2 3 /** 4 * The maximum capacity, used if a higher value is implicitly specified 5 * by either of the constructors with arguments. 6 * MUST be a power of two <= 1<<30. 7 */ 8 static final int MAXIMUM_CAPACITY = 1 << 30; 9 10 /** 11 * The load factor used when none specified in constructor. 12 */ 13 static final float DEFAULT_LOAD_FACTOR = 0.75 f; 14 15 static final int TREEIFY_THRESHOLD = 8; 16 17 transient Node<K,V>[] table; 18 19 /** 20 * Holds cached entrySet(). Note that AbstractMap fields are used 21 * for keySet() and values(). 22 */ 23 transient Set<Map.Entry<K,V>> entrySet; 24 25 /** 26 * The number of key-value mappings contained in this map. 27 */ 28 transient int size; Much the same as 1.7, with a few important differences: TREEIFY_THRESHOLD Specifies the threshold used to determine whether a linked list needs to be converted to a red-black tree. Change HashEntry to Node. In fact, the core composition of Node is the same as HashEntry in 1.7, which stores key value, Hashcode next and other data. Now look at the core method. The put method seems to be more complex than 1.7, so we break it down step by step: determine whether the bucket is empty, and initialize it if it is empty (resize will determine whether to initialize it). Locate the bucket according to the hashcode of the current key and check whether it is empty. If it is empty, it indicates that there is no Hash conflict. Create a new bucket at the current location. If the current bucket has a value (Hash conflict), the key in the current bucket is compared, and the hashcode of the key is equal to the written key. If the key is equal, the value is assigned to E. At step 8, the assignment and return are performed uniformly. If the current bucket is a red-black tree, write data in red-black tree fashion. If it is a linked list, encapsulate the current key and value into a new node and write it to the end of the bucket (form a linked list). Then determine whether the size of the current list is greater than the preset threshold, and if so, convert to a red-black tree. If the same key is found during the traversal, exit the traversal directly. If e! = null equals the existence of the same key, which needs to be overwritten. Determine whether capacity expansion is required. 1 public V get(Object key) {2 Node<K,V> e; 3 return (e = getNode(hash(key), key)) == null ? null : e.value; 4 } 5 6 final Node<K,V> getNode(int hash, Object key) { 7 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 8 if ((tab = table) ! = null && (n = tab.length) > 0 && 9 (first = tab[(n - 1) & hash]) ! = null) { 10 if (first.hash == hash && // always check first node 11 ((k = first.key) == key || (key ! = null && key.equals(k)))) 12 return first; 13 if ((e = first.next) ! = null) { 14 if (first instanceof TreeNode) 15 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 16 do { 17 if (e.hash == hash && 18 ((k = e.key) == key || (key ! = null && key.equals(k)))) 19 return e; 20 } while ((e = e.next) ! = null); 21 } 22 } 23 return null; 24} The get method looks much simpler. The key is first hash and the bucket is retrieved. If the bucket is empty, null is returned. Otherwise, it checks whether the key in the first position of the bucket (such as a linked list or red-black tree) is the query key and returns value directly. If the first one does not match, it is determined whether the next one is a red-black tree or a linked list. The red-black tree returns the value as the tree looks up. Otherwise, the match returns are iterated through in a linked list. From these two core methods (get/ PUT), we can see that the large linked list is optimized in 1.8, and the query efficiency is directly improved to O(logn) after the modification to red-black tree. However, the original problems of HashMap also exist, such as the tendency for an infinite loop when used in concurrent scenarios. 1final HashMap<String, String> map = new HashMap<String, String>(); 2for (int i = 0; i < 1000; i++) { 3 new Thread(new Runnable() { 4 @Override 5 public void run() { 6 map.put(UUID.randomUUID().toString(), ""); 7 } 8 }).start(); 9} When a HashMap is put and the number of inserted elements exceeds its capacity (as determined by the load factor), a rehash operation is triggered, which rehashes the contents of the original array into the new array. In a multi-threaded environment, other elements are put at the same time. If the hash value is the same, it can be represented in a linked list under the same array, resulting in a closed loop, resulting in an infinite loop during get, so a HashMap is thread unsafe.Copy the code
Here is a brief introduction to ConcurrenthashMap, which I have a general grasp, because it involves a lot of things, and I can’t finish it here. I also have a conceptual understanding of some things, and I remember I said a lot of points from this set at the beginning
1.7 1.8 Distinguish segmental locking, SYNC Weight locking (no bias – Light weight – weight) conversion CAS mechanism and ABA issues
AtomicInteger
Unsafe Tool class. AQS synchronized queue (both exclusive and shared)
The implementation of ReentrantLock is based on AQS
)
LockSuport pack unpack and Object.wait
The above sets are introduced
Let’s start by introducing MYSQL to the following sections, which are all important, so far I can only think of these
1. Mysql execution process
2. Log files of mysql
Mysql > select * from ‘mysql’;
4. Different storage engines cause different indexes
5. There are underlying file formats and data structures in the index. Why did they evolve
Mysql lock (MVVC + lock)
7. Mysql transaction problem
8. Explain the implementation plan
Now let’s talk about redis, this is very important in the interview of the Internet, a basic concept, Redis clustering has done data is basically not lost, so only not important data, business will consider caching.
1. Must understand LRU
2. Redis structure type redisObject structure is how, do not understand the redis data structure [not refers to the string, list,set, etc.] What is the underlying structure of redis String?
3. Redis IO model, or I saw in a certain video that redis data acquisition fast part of the reason is because of the data structure of the hopping table, fart, hopping table only exists in zset data length beyond the structure change is
4. Redis Aof RDB delete strategy, elimination strategy and sentinel, cluster, profile optimization distributed lock, and ZK distributed lock difference
Here are some common redis questions
Question:
How do I make an original slave node the master node?
Redis distributed lock and Zookeeper distributed lock implementation scheme and comparison
The traditional LRU is based on linked list +HashMap, how to solve redis how to find the lowest heat data?
Common Redis data loss
- Program bug or human error
- A large number of keys are eliminated by LRU due to large client buffer memory usage
- If the primary database is faulty, it automatically restarts, which may cause data loss
- A network partition problem may cause the loss of written data for a short time
- The primary and secondary replication data is inconsistent, and data is lost after failover occurs
- A large number of expired keys are eliminated at the same time
To be continued, micro service project knowledge, distributed environment project caused by the problem, transaction problems, lock failure and so on, we had better put mybatis spirng source code again, they apply a different design mode, I am currently looking at Mybatis lovely