HashMap is a question that you should ask in a job interview. If so, how should you prepare and answer it?
Let’s take a look at these two pictures of the internal storage structure
Speaking of HashMap, we can start from the underlying implementation. HashMap is realized through hash algorithm based on array, linked list and red-black tree. Hash algorithm is an idea, and any algorithm conforming to this idea is hash algorithm. For example is when we want to store a key for a string of a set of data, then we can through the hash key can be converted to digital, as the index of an array, then the value stored in the index of the space, if our array length is 16, so when there are 20 key for the hash, certainly there is a conflict, H (key1) = h(key2). In this case, the solution is to make the index point to a linked list, so that different keys can correspond to the same H (key). When obtaining the key, we can determine an index through the key, and then traverse the linked list. Therefore, red-black tree appears. When the list elements are greater than or equal to 8, red-black tree is used to store, and the time complexity is directly reduced from O(n) to O(logn).
That’s about the core idea of HashMap, which most people probably know. Now, to highlight this, you can say that HashMap threads are not safe, and then give him this example. Create three threads and access the PUT method at the same time
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class TestHashMap implements Runnable {
static Map<String,Object> map = new HashMap();
//static Map<String,Object> map = new ConcurrentHashMap<>();
@Override
public void run(a) {
for (int i = 0; i < 100; i ++) {
map.put(i + ""."hello"); }}public static void main(String[] args){
Thread thread1 = new Thread(new TestHashMap());
Thread thread2 = new Thread(new TestHashMap());
Thread thread3 = new Thread(new TestHashMap());
thread1.start();
thread2.start();
thread3.start();
Thread currentThread = Thread.currentThread();
try {
currentThread.sleep(2000);
} catch(Exception e) { System.out.println(e.getMessage()); } System.out.println(map.size()); }}Copy the codeThe normal output should be 100, but instead of 204, the output is 204
You can lock the put method with synchronized
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class TestHashMap implements Runnable {
static Map<String,Object> map = new HashMap();
//static Map<String,Object> map = new ConcurrentHashMap<>();
@Override
public void run(a) {
for (int i = 0; i < 100; i ++) {
synchronized (TestHashMap.class) { // here!!
map.put(i + ""."hello"); }}}public static void main(String[] args){
Thread thread1 = new Thread(new TestHashMap());
Thread thread2 = new Thread(new TestHashMap());
Thread thread3 = new Thread(new TestHashMap());
thread1.start();
thread2.start();
thread3.start();
Thread currentThread = Thread.currentThread();
try {
currentThread.sleep(2000);
} catch(Exception e) { System.out.println(e.getMessage()); } System.out.println(map.size()); }}Copy the codeThat would solve the threading problem, but you’re getting a little violent, locking the entire put method. Look at how much code there is in the put method. It’s a little bit too much to Hash Map put source code
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeConcurrentHashMap is thread safe, so let’s see how it works
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { / / in this!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if(e.hash == hash && ((ek = e.key) == key || (ek ! =null && key.equals(ek)))) {
oldVal = e.val;
if(! onlyIfAbsent) e.val = value;break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break; }}}else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! =null) {
oldVal = p.val;
if(! onlyIfAbsent) p.val = value; }}}}if(binCount ! =0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if(oldVal ! =null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
Copy the codeIn this way, the lock is less, the efficiency is of course high, to tell the truth, it is also convenient to use, the following to show the high-end operation
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class TestHashMap implements Runnable {
//static Map<String,Object> map = new HashMap();
static Map<String,Object> map = new ConcurrentHashMap<>();
@Override
public void run(a) {
for (int i = 0; i < 100; i ++) {
map.put(i + ""."hello"); }}public static void main(String[] args){
Thread thread1 = new Thread(new TestHashMap());
Thread thread2 = new Thread(new TestHashMap());
Thread thread3 = new Thread(new TestHashMap());
thread1.start();
thread2.start();
thread3.start();
Thread currentThread = Thread.currentThread();
try {
currentThread.sleep(2000);
} catch(Exception e) { System.out.println(e.getMessage()); } System.out.println(map.size()); }}Copy the code
Finally, for thread safety, ConcurrentHashMap.
