HashMap 및 ConcurrentHashMap 분석

HashMap
 
hashmap 본질 데이터 체인 테이블.키에서hash값을 얻어서 수조 하표를 계산하고 여러 키가 같은 하표에 대응하면 체인 테이블로 꿰어 새로 삽입합니다.
중요 코드 요약 3절 보기:
a:

    public HashMap(int initialCapacity, float loadFactor) {
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

세 가지 관건적인 파라미터가 있습니다:capacity: 용량, 바로 그룹 크기loadFactor: 비례,threshold 확장에 사용: =capacity*loadFactor가 가장 많이 수용하는 Entry 수, 현재 요소 개수가 이것보다 많으면 확장합니다 (capacity가 원래의 2배로 확대)
b:

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

키에 따라hash값을 계산하고hash값에 따라수조하표를 얻어 수조하표를 통해 체인표를 꺼내고 체인표를 옮겨다니며 equals로 키에 대한value를 꺼낸다.
c:   

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

그룹 (hash 값을 통해)에서 체인 헤더를 얻은 다음 equals를 통해 키를 비교합니다. 같으면 오래된 값을 덮어쓰고 오래된 값을 되돌려줍니다.(이 키는 hashmap에 이미 존재함)
그렇지 않으면 entry를 추가해서null로 돌아갑니다.새로 추가된 원소는 체인 헤더로 이전에 같은 그룹의 위치가 뒤에 걸려 있었다.
또한:modCount는 한 무더기의 데이터를 읽을 때 순환적으로 읽는 과정에서 수정이 발생하면 이상을 던지는 것을 피하기 위한 것이다
  if (modCount != expectedModCount)                 throw new ConcurrentModificationException();          
다음은 맵 요소를 추가하는 것을 보십시오

    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

새로 추가된 후,size가threshold보다 크다는 것을 발견하면,resize는 원래의 2배로

    void resize(int newCapacity) {

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

새 그룹을 만들고 원래 데이터를 옮깁니다

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

원래 그룹의 체인 테이블을 하나씩 꺼내서 체인 테이블의 모든 요소를 훑어보고 index를 다시 계산해서 새 그룹에 넣습니다.모든 처리된 것도 체인 헤드를 넣는다.
원래의 그룹 체인 테이블을 꺼낸 후, 원래의 그룹을 비웁니다. (빅데이터 양을 복제할 때 더 빨리 쓰레기로 회수됩니까?)
그리고 두 가지 주의사항은 다음과 같다.
static class Entry implements Map.Entry는hashmap의 정적 내부 클래스,iterator 같은 내부 클래스입니다. 모든 요소가 맵의this 포인터를 가지고 있어야 하는 것은 아니기 때문입니다.
HashMap은transient Entry[] table;등 변수를transient로 설정한 다음에override는readObject와writeObject를 서열화하였습니다.
ConcurrentHashMap:
hashMap을 토대로ConcurrentHashMap은 데이터를 여러 개의segment, 기본 16개(concurrency level)로 나누고 매번 조작할 때마다segment에 자물쇠를 채워 다중 노드 자물쇠의 확률을 피하고 병발 효율을 높인다.

  public V get(Object key) {
        int hash = hash(key.hashCode());
        return segmentFor(hash).get(key, hash);
    }

   final Segment segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }

 
in class Segment:

   V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

        /**
         * Reads value field of an entry under lock. Called if value
         * field ever appears to be null. This is possible only if a
         * compiler happens to reorder a HashEntry initialization with
         * its table assignment, which is legal under memory model
         * but is not known to ever occur.
         */   
        V readValueUnderLock(HashEntry e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

 
주의, 여기에서 동시에 읽을 때 키에 대응하는value가null인 것을 제외하고는 자물쇠를 사용하지 않았습니다. 어떻게 하면 문제가 없을 수 있습니까? 다음과 같은 3가지가 있습니다. 1.       HashEntry getFirst(int hash) {             HashEntry[] tab = table;             return tab[hash & (tab.length - 1)]; }여기서 읽을 때 그룹 크기 (tab.length) 가 바뀌면 데이터가 잘못될 수 있지만,transientvolatile HashEntry [] table;volatile입니다. 그룹의 크기 변화를 바로 알 수 있습니다.
2. static final class Hash Entry {final K key;final int hash;volatile V value;final Hash Entry next;여기서 next는final이면 Hash Entry가 꺼내면 전체 체인 테이블이 정확하다는 것을 보장합니다.
3.value는volatile입니다.put 덮어쓰기가 있으면 바로 볼 수 있습니다.
 
 

public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
    }

 V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry first = tab[index];
                HashEntry e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

여기에는 잠금 작업 외에는 일반 해시맵과 원리적으로 큰 차이가 없다.
 
 
아직 이해가 안 가는 점이 하나 더 있다.
get과put/remove가 동시에 발생할 때 get의HashEntry e = getFirst(hash);체인 시계는 이미 꺼냈습니다. 이때put에 entry를 체인 시계 헤드에 넣습니다. 마침 필요한 키라면 꺼낼 수 없습니까?
리모브를 할 때 리모브가 필요한 키를 먼저 제거한 다음에 리모브의 키 앞에 있는 요소를 하나씩 체인 헤더에 연결한다. 마찬가지로 리모브가 존재한 후에 이전의 헤드가 중간에 이르면 읽는 요소도 빠진다.

   ++modCount;
                        HashEntry newFirst = e.next;
                        for (HashEntry p = first; p != e; p = p.next)
                            newFirst = new HashEntry(p.key, p.hash,
                                                          newFirst, p.value);
                        tab[index] = newFirst;
                        count = c; // write-volatile