preface

Recently in view of the Internet company interview asked knowledge points, summed up the Java programmer interview involves most of the interview questions and answers to share with you, I hope to help you review before the interview and find a good job, but also save you on the Internet to search for information time to learn.

Content covers: Java, MyBatis, ZooKeeper, Dubbo, Elasticsearch, Memcached, Redis, MySQL, Spring, SpringBoot, SpringCloud, RabbitMQ, Kafka, Linux and other technology stacks.

Full version Java interview questions address: Java backend questions integration

Hash table structure

The hash table structure is an array + linked list structure

What is a hash?

The basic principle of Hash, also known as Hash, is to convert input of arbitrary length into output of fixed length through the Hash algorithm

The rules of this mapping are the corresponding hash algorithm, and the binary of the original data is the hash value

Java concurrent programming learning notes, concern public number: programmer chase wind, reply 013 to receive 422 pages of PDF document

Different data it corresponds to the hash code value is not the same

The hashing algorithm is very efficient

3. Explain the principle of HashMap

3.1 Inheritance System Diagram

3.2 Analysis of Node data structure

static class Node<K,V> implements Map.Entry<K,V> { final int hash; Final K key; V value; Node<K,V> next; } interface Entry<K, V> { K getKey(); V getValue(); V setValue(V value); Copy the codeCopy the code

3.3. Underlying storage structure

When the list length reaches 8, upgrade to red-black tree structure

3.4 Put data principle analysis

First, a key—-value will be put in and a hash value will be calculated according to the key value. After the perturbation, the data will be more hashed to construct a Node object. Finally, a corresponding index will be obtained through the routing algorithm

3.5. What is hash collision?

When the last four digits of the hash value corresponding to the data key passed in are the same as the last one, the calculated index will be the same, and collisions will occur, causing data to become linked lists. For example: (16-1)——->0000 0000 0000 1111 “Zhang SAN” ——->0100 1101 0001 1011 “Li Si” ——–>1011 1010 0010 1011 The hash values calculated by John and John are converted to the last four digits of the binary, resulting in the calculation of the same index

3.6 why red-black trees are introduced in JDK8?

Hash collisions, you’re going to chain, you’re going to be less efficient

The introduction of red-black tree will improve the search efficiency

3.7 Capacity expansion mechanism

Each expansion is twice the initial capacity

Eg: 16 — — — — — — — > 32

To prevent excessive data from leading to linear query and low efficiency, capacity expansion increases the number of buckets and reduces the data on each chain, resulting in faster query

Four, hand tear source code

4.1 Analysis of core attributes of HashMap

Tree thresholds —–8 and 64

Load factor 0.75

Threshold Capacity expansion threshold. When the number of hash table elements exceeds the threshold, capacity expansion is triggered

LoadFactory Load factor 0.75, to calculate the threshold eg: 16*0.75

Size ——- Number of elements in the current hash table

ModCount ——– Number of current hash table structure changes

4.2 analysis of construction methods

public HashMap(int initialCapacity, Float loadFactor) {if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: " + initialCapacity); If (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; / / load factor can not be less than or equal to 0 if (loadFactor < = 0 | | Float. The isNaN (loadFactor)) throw new IllegalArgumentException (" Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //tableSizeFor method this.threshold = tableSizeFor(initialCapacity); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / into a initial capacity, Default load factor 0.75 public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / no parameters, Public HashMap() {this.loadfactor = DEFAULT_LOAD_FACTOR; / / all other fields defaulted} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / public into a map object HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } Duplicate codeCopy the code

4.3 Put method analysis

Public V put(K key, V value) {// Returns putVal, rehash return putVal(Hash (key), key, value, false, true); } ---------------------------------------------------------- static final int hash(Object key) { Int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ---------------------------------------------------------- final V putVal(int hash, K key, V value, Boolean onlyIfAbsent, Boolean evict) {// TAB: hash reference of the current HashMap //p: hash element of the current HashMap //n: hash array length // I: Node<K,V>[] TAB; Node<K,V> p; int n, i; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / delay initialization logic, when the first call putVal, To initialize the HashMap object's hash table size if ((TAB = table) = = null | | (n = TAB. Length) = = 0) n = (TAB = the resize ()). The length; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / looking for find barrels, and just to null, If ((p = TAB [I = (n-1) & hash]) == null) TAB [I] = newNode(hash, key, value, null); -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- else {/ / e: no is null, find a consistent with the current key - val to insert the key object / / k: A temporary key Node<K,V> e; K k; / / said barrels of the elements, consistent with your current key inserted element, the follow-up will be replace operation if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) e = p; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / tree, else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- else {/ / list, and the head of the list do not agree with what we want to insert the key element for (int binCount = 0; ; ++binCount) { If ((e = p.ext) == null) {p.ext = newNode(hash, key, value, null); If (binCount >= treeify_threshold-1) // -1 for 1st treeifyBin(TAB, hash); break; } / / that find the key, can be replaced, break out of the loop if (e.h ash = = hash && ((k = e.k ey) = = key | | (key! = null && key.equals(k)))) break; p = e; }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - / / e is not equal to null, found a and you insert element completely consistent, to replace the if (e! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / modCount: said hash structure is modified, replacing elements not number + + modCount; If (++size > threshold) resize(); if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } Duplicate codeCopy the code

4.4 resize() method analysis

// In order to resolve hash conflicts and affect hash efficiency, So there will be a capacity mechanism -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the final Node < K, V > [] the resize () {/ / oldTab: OldCap: indicates the array length of the table before capacity expansion. //oldThr: indicates the threshold before capacity expansion. //newCap, newThr: indicates the array length after capacity expansion and the threshold after capacity expansion. int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / conditions, shows a hashmap hash table has been initialized, If (oldCap > 0) {if (oldCap > 0) {if (oldCap > 0) { If (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; if (oldCap >= MAXIMUM_CAPACITY) {threshold = integer.max_value; return oldTab; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / oldCAP left one, to realize numerical doubled, and assigned to newcap, Newcap is less than the maximum value limit and the threshold before expansion >=16 Else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; / / double threshold} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / oldCap = = 0, The hashMap hash table is null //1.new hashmap (inttCap, loadFactor); //2.new HashMap(inttCap); //3.new HashMap(map); Else if (oldThr > 0) // Initial capacity was placed in threshold newCap = oldThr; / / must be a power of 2 number -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / oldCap = = 0, oldThr = = 0 / / new HashMap (); else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } ---------------------------------------------------------- if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; ---------------------------------------------------------- ---------------------------------------------------------- // Create a longer and larger array @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; Before the expansion, the table is not null if (oldTab! = null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; If ((e = oldTab[j])! // oldTab[j] = null; If (e.next == null) newTab[e.hash & (newcap-1)] = e; if (e.next == null) newTab[e.hash & (newcap-1)] = e; Else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); LoHead =null, loTail=null; loHead <K,V> loHead =null; loTail=null; Node<K,V> hiHead =null, hiTail=null; ---------------------------------------------------------- Node<K,V> next; do { next = e.next; / / hash -... 1, 1111 / / hash -... 0 1111 //0b 10000 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); // if (loTail ! = null) { loTail.next = null; newTab[j] = loHead; } // if (hiTail ! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } Duplicate codeCopy the code

4.5. Get method

public V get(Object key) { Node<K,V> e; return (e = getNode(key)) == null ? null : e.value; } ---------------------------------------------------------- final Node<K,V> getNode(Object key) { Node<K,V>[] tab; // TAB: references the hash table of the current hashmap Node<K,V> first, e; //first: the head element in the bucket, e: the temporary node element int n, hash; //n: table array length K K; --------------------------------------------------------- if ((tab = table) ! = null && (n = tab.length) > 0 && (first = tab[(n - 1) & (hash = hash(key))]) ! = null) {/ / positioning of barrel element, is the element we want to get the if (first. The hash = = hash && / / always check first node ((k = first. Key) = = key | | (key! = null && key.equals(k)))) return first; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / the current barrel of more than one element, is likely to be a tree or list the if ((e = first. Next! = null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / list of do {the if (e.h ash = = hash && ((k = e.k ey) = = key | | (key ! = null && key.equals(k)))) return e; } while ((e = e.next) ! = null); } } return null; } Duplicate codeCopy the code

4.6 remove method analysis

public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } ---------------------------------------------------------- final Node<K,V> removeNode(int hash, Object key, Object Value, Boolean matchValue, Boolean movable) {// TAB: hash that references the current HashMap //p: the element of the current hash //n: the length of the hash array //index: Node<K,V>[] TAB; Node<K,V> p; int n, index; ---------------------------------------------------------- if ((tab = table) ! = null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) ! = null) {/ / barrels of routing is a data, to find operations, and delete -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / node: search results, to e: The next element of the current node node <K,V> node = null, e; K k; V v; / / barrels of current is to delete the elements of the elements of the if (p.h ash = = hash && ((k = p.k ey) = = key | | (key! = null && key.equals(k)))) node = p; -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / barrels of current element for red and black tree else if ((e = p.n ext)! = null) { if (p instanceof TreeNode) node=((TreeNode<K,V>)p).getTreeNode(hash, key); -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / for the list of the current barrel else {do {the if (e.h ash = = hash && ((k = e.k ey) = = key || (key ! = null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) ! = null); }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / / node is empty, no instructions according to the key data if found to be deleted (node! = null && (! matchValue || (v = node.value) == value ||(value ! = null&&value.equals(v)))) {// result is red black tree if (node instanceof TreeNode) ((TreeNode<K, v >)node).removeTreenode (this, TAB, movable); Else if (node == p) TAB [index] = node.next; // Result is linked list else p.ext = node.next; ++modCount; // Change the number of times --size; // In my room, I visted deremoval (node); return node; } } return null; } Duplicate codeCopy the code

4.7 analysis of replace method

@Override public boolean replace(K key, V oldValue, V newValue) { Node<K,V> e; V v; if ((e = getNode(key)) ! = null && ((v = e.value) == oldValue || (v ! = null && v.equals(oldValue)))) { e.value = newValue; afterNodeAccess(e); return true; } return false; } ---------------------------------------------------------- @Override public V replace(K key, V value) { Node<K,V> e; if ((e = getNode(key)) ! = null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; } ll && v.equals(oldValue)))) { e.value = newValue; afterNodeAccess(e); return true; } return false; } ---------------------------------------------------------- @Override public V replace(K key, V value) { Node<K,V> e; if ((e = getNode(key)) ! = null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; }Copy the code

Full version Java interview questions address: Java backend questions integration