ConcurrentHashMap<>

김영한님의 스프링강의를 듣게되면 ConcurrentHashMap<>이란 것을 듣게 됩니다.
concurrentHashMap을 사용하여 강의를 하시지는 않지만, 이게 뭐지?라는 궁금증이 생겨 한 번 적어봅니다.
ConcurrentHashMap 중 putVal() 이라는 함수에 대해서 작성하겠습니다.

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; K fk; V fv;
            if (tab == null || (n = tab.length) == 0) 
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 1
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) // 2
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else if (onlyIfAbsent // check first node without acquiring lock
                     && fh == hash
                     && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                     && (fv = f.val) != null)
                return fv;
            else {
                V oldVal = null;
                synchronized (f) { // 3
                    if (tabAt(tab, i) == f) { // 4
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash && // 5
                                    ((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) { // 6
                                    pred.next = new Node<K,V>(hash, key, value);
                                    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;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) { // 7
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

// 1

• (n-1) & hash ← hash % n 의 이유
  해싱 결과 값은 n보다 작은 값이 나와야한다.
  putVal 함수에서 사용한 해싱은 비트연산자를 사용하여 속도를 높임.
  &연산시, n-1의 가장 왼쪽에 위치한 1 보다 왼쪽들은 다 0 이므로, hash와 &시, 나올 수 있는 값은 n-1보다 클수가 없게 된다.

• getObjectVolatile로 volatile변수로 리턴되는것 같다.
  volatile은 main memory에서 값을 read한다.

// 2

casTabAt
null과 같다면, 새 노드를 삽입한다.
이때 비어있으므로, lock하지 않을 수 있다.
casTabAt함수에서 compareAndSetObject를 사용하며, compareAndSet은 JNI (다른언어를 사용 할 수 있게 해준다.) 을 사용하여 cpu명령을 수행하여 atomic하게 set하므로 lock이 필요없다.

// 3

synchronized block 방식으로 f 에 대해서만 잠그게 된다.
현재 쓰레드이외의 쓰레드는 blocking 된다.
해당 쓰레드의 작업이 끝난 뒤 다른 쓰레드가 blocking이 해제되어 작업을 시작 할 때,

// 4

다시 tabAt(tab,i) == f 로 체크하는 이유는, 이전 작업에서 f노드가 새로운 노드로 교체되었을 수도 있으므로, 교체 된 경우 탈출하기 위함이다.

// 5

⇒ 새로운 노드로 교체

// 6

⇒ Separate Chaining에 추가

// 7

⇒ 트리에 추가

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
    }

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

//Fetches a reference value from a given Java variable, with volatile load semantics.
// Otherwise identical to getObject(Object, long)
@HotSpotIntrinsicCandidate
    public final Object getObjectAcquire(Object o, long offset) {
        return getObjectVolatile(o, offset);
    }

//Fetches a reference value from a given Java variable, with volatile load semantics.
// Otherwise identical to getObject(Object, long)
@HotSpotIntrinsicCandidate
    public final Object getObjectAcquire(Object o, long offset) {
        return getObjectVolatile(o, offset);
    }