[위 에] [소스 코드] HashMap 소스 코드 분석

//-----------------------------------------------------------------------------------
전재 하려 면 출처 를 밝 혀 야 합 니 다:http://blog.csdn.net/chdjj
//-----------------------------------------------------------------------------------
주: 아래 소스 코드 는 jdk 1.7.0 기반11

이전의 몇 편의 글 은 List 집합 에서 비교적 흔히 볼 수 있 는 유형, 예 를 들 어 Array List, LinkedList, Vector 등 을 소개 했다.이 글 은 집합 프레임 의 또 다른 내용 인 맵 집합 을 소개 한다.본 고 는 주로 HashMap 을 소개 한다.
먼저 해시 표를 돌 이 켜 보 자.
해시 표 정의: 설 정 된 hash 함수 와 충돌 을 처리 하 는 방식 (주소 지정, 공공 넘 침 구역, 체인 주소, 재 해시...) 에 따라 한 그룹의 키 워드 를 유한 한 연속 주소 집합 (즉 bucket 배열 또는 통 배열) 에 표시 하고 키워드 가 주소 에 집 중 된 '상' 을 표 에 기록 하 는 저장 위치 로 합 니 다. 이 표 는 hash 표 라 고 합 니 다.이 매 핑 과정 은 해시 라 고 부 르 며, 소득 저장 위 치 는 해시 주소 나 해시 주소 라 고 부른다.hash 표 는 좋 은 검색 성능 을 가지 고 충돌 확률 이 적은 상황 에서 시간 복잡 도 는 O (1) 입 니 다.
적재 인자:
loadfactor = 표 에 기 록 된 기록 수 / 해시 표 의 길이 입 니 다. 그래서 loadfactor 는 해시 표 의 가득 찬 정 도 를 표시 합 니 다.
직관 적 으로 볼 때 적재 인자 가 작 을 수록 충돌 이 발생 할 확률 이 적다 (통 에 몇 개의 데 이 터 를 담 지 않 았 기 때문에 확장 이 필요 하 다). 즉, 성능 을 찾 을 수록 좋 지만 낭비 하 는 공간 이 커진다 는 것 이다.반면에 적재 인자 가 클 수록 충돌 이 발생 할 확률 이 높다 (통 이 빨리 채 워 질 때 까지 기 다 려 야 확대 할 수 있다. 예 를 들 어 링크 법 으로 충돌 을 처리 할 때 이런 상황 에서 링크 가 너무 길 어 질 수 있다). 검색 성능 이 떨 어 질 수록 낭비 하 는 공간 이 줄어든다.
뒤에 저희 가 볼 수 있 는데...
HashMap 의 기본 적재 인 자 는 0.75 입 니 다.
다음은 여전히 위 에서 아래로 분석 하고,
우선 맵 인터페이스 보기:

public interface Map<K,V> {//Map         
    // Query Operations
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);//       
    boolean containsValue(Object value);//       
    V get(Object key);
    // Modification Operations
    V put(K key, V value);
    V remove(Object key);
    // Bulk Operations
    void putAll(Map<? extends K, ? extends V> m);//      
    void clear();
    // Views
   //    
    Set<K> keySet();//    
    Collection<V> values();//    
    Set<Map.Entry<K, V>> entrySet();//      

    interface Entry<K,V> {//Map     ，       
        K getKey();//   
        V getValue(); //   
        V setValue(V value);//   
        boolean equals(Object o);
        int hashCode();
    }

    // Comparison and hashing
    boolean equals(Object o);
    int hashCode();
}

Map 인 터 페 이 스 는 Map 집합 의 조작 규범 을 정의 하고 구체 적 으로 실현 은 실현 류 에 의 해 이 루어 집 니 다. 그 내부 에 인터페이스 Entry 가 있 는데 키 값 쌍 을 대표 합 니 다.
AbstractMap 은 추상 적 인 클래스 로 Map 인터페이스 의 대부분 함 수 를 실현 합 니 다.

public abstract class AbstractMap<K,V> implements Map<K,V>

다음은 몇 가지 방법 을 살 펴 보 겠 습 니 다.

public boolean containsKey(Object key) {
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();//     
        if (key==null) {//  key    ,    
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)//          
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))//       equals    
                    return true;
            }
        }
        return false;
    }
    public boolean containsValue(Object value) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        if (value==null) {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getValue()==null)
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (value.equals(e.getValue()))
                    return true;
            }
        }
        return false;
    }

우선 contains Key 와 contains Value 방법 입 니 다. 주의해 야 할 것 은 이 키 와 value 가 비어 있 는 것 입 니 다. 즉, 하위 클래스 는 기본적으로 null 키 와 값 을 지원 합 니 다.이곳 의 entry Set 방법 은 추상 적 인 방법 이다.

public abstract Set<Entry<K,V>> entrySet();

abstractMap 은 put 방법 을 실현 하지 않 고 간단하게 이상 을 던 졌 습 니 다. 하위 클래스 를 구 하려 면 이 방법 을 복사 해 야 합 니 다.

 public V put(K key, V value) {
        throw new UnsupportedOperationException();
    }

그러나 get 방법 을 실현 했다.

 public V get(Object key) {
        Iterator<Entry<K,V>> i = entrySet().iterator();
        if (key==null) {//          null     
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    return e.getValue();
            }
        } else {
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    return e.getValue();
            }
        }
        return null;
    }

하 쉬 맵 을 살 펴 보 겠 습 니 다.

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap 은 AbstractMap 류 를 계승 하여 Map 인터페이스 와 Cloneable, Serializable 인 터 페 이 스 를 실현 했다.
그 구성원 변 수 는 다음 과 같다.

 static final int DEFAULT_INITIAL_CAPACITY = 16;//      
    static final int MAXIMUM_CAPACITY = 1 << 30;//     2 30  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//       0.75
    transient Entry<K,V>[] table;//   ，     
    transient int size;//          
    int threshold;//HashMap   ，          HashMap   （threshold =   *    ）
    final float loadFactor;//    
    transient int modCount;//hashmap      
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

여기 서 우 리 는 다음 과 같은 정 보 를 얻 었 다.
1. HashMap 의 기본 크기 는 16 입 니 다. 즉, 통 배열 의 기본 길 이 는 16 입 니 다.2. HashMap 의 기본 적재 인 자 는 0.75 입 니 다.3. HashMap 내부 의 통 배열 은 Entry 대상, 즉 키 쌍 대상 을 저장 합 니 다.
구조 기 다시 보기:

 public HashMap(int initialCapacity, float loadFactor) {//                  
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // Find a power of 2 >= initialCapacity
        //  “  initialCapacity”    2  
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //      
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();//      ，      
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {//                   HashMap
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }
    // internal utilities

    void init() {
    }

주의해 야 할 점:
1. 구조 기 는 초기 용량 과 적재 인 자 를 지정 하 는 것 을 지원 합 니 다. 배열 의 확장 에 따 른 성능 문 제 를 피하 기 위해 수요 에 따라 초기 용량 을 지정 하 는 것 을 권장 합 니 다.적재 인 자 는 가능 한 한 수정 하지 마 세 요. 0.75 는 비교적 믿 을 만 한 값 입 니 다.
2. 실제 용량 capacity 는 일반적으로 우리 가 들 어 오 는 initialCapacity 보다 크다. 내부 에서 하나의 순환 을 통 해 initialCapacity 보다 크 고 2 인 정수 차 멱 의 한 수 를 실제 용량 으로 찾 을 수 있 기 때문이다.들 어 가 는 숫자 가 2 인 정수 제곱 (capacity 에서 2 의 정수 차 멱 을 취하 지 않 는 한 서로 다른 hash 값 이 충돌 할 확률 이 적 게 발생 하도록 하기 위해 서 입 니 다. 그러면 요 소 를 해시 표 에서 고 르 게 분산 시 킬 수 있 습 니 다.)
앞의 분석 을 통 해 우 리 는 HashMap 내부 에서 Entry 배열 을 통 해 키 값 을 저장 하 는 것 을 알 게 되 었 습 니 다. 그러면 이 Entry 는 어떻게 실현 되 었 습 니까?
이제 저희 가 볼 게 요.
Entry 의 실현:

 static class Entry<K,V> implements Map.Entry<K,V> {//  Map.Entry  
        final K key;// ,final  ，    /
        V value;// 
        Entry<K,V> next;//HashMap         ，   next          
        int hash;//hash 
        /**
         * Creates new entry.
         */
        //              ,             
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        public final K getKey() {
            return key;
        }
        public final V getValue() {
            return value;
        }
        //    value
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            //       
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }
        public final int hashCode() {//    hash  0，      hashcode  
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }
        public final String toString() {
            return getKey() + "=" + getValue();
        }
        /**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }
        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

주의해 야 할 점:
1. HashMap 내부 배열 은 키 쌍, 즉 Entry 대상 을 저장 합 니 다.
2. Entry 대상 은 키, 값 을 저장 하고 next 포인터 로 다음 Entry 대상 을 가리 키 고 있 습 니 다 (HashMap 은 링크 를 통 해 충돌 을 해결 합 니 다).
3. Entry 는 setValue 를 통 해 값 을 설정 할 수 있 지만 설정 키 는 허용 되 지 않 습 니 다.
HashMap 에서 중요 한 방법 을 연구 해 보 겠 습 니 다.put 부터:

  public V put(K key, V value) {//           
        if (key == null)//     ，   putForNullKey
            return putForNullKey(value);
        int hash = hash(key);//    key    hash   
        int i = indexFor(hash, table.length);//            
      //         Entry  ，               Entry，             ,      
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //hash       
            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;
    }

put 방법 은 hashMap 에 키 값 을 추가 하 는 것 입 니 다. 이 방법 은 다음 과 같 습 니 다.
1. 허용 키 는 null 입 니 다.put 방법 은 null 키 에 해당 하 는 처 리 를 하고 pulforNullKey 방법 을 호출 합 니 다.

  private V putForNullKey(V value) {
     //  ， hash  0，        0     。
//      0   entry  ，       null  ，      
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
//   ，   
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

2. 두 키 가 같 을 수 없습니다. 키 가 같 으 면 삽입 한 키 에 해당 하 는 값 이 이전 값 을 덮어 씁 니 다.
3. HashMap 은 hash () 방법 을 호출 하여 키 의 hash 값 을 얻 고 index For 방법 으로 실제 삽입 위 치 를 찾 습 니 다. 구체 적 인 코드 는 다음 과 같 습 니 다.

  final int hash(Object k) {//     hash 
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
//  hash           
    static int indexFor(int h, int length) {
        return h & (length-1);// put    ，  length      ，               2     ，    &        h%length       ,           .
    }

4. put 방법 은 addEntry 방법 을 통 해 키 값 을 적당 한 위치 에 삽입 합 니 다:
5. 용량 이 한도 값 (threshold) 을 초과 할 때 확장 이 발생 하고 확장 후의 배열 은 원래 배열 의 두 배 이다.

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {//      
            resize(2 * table.length);//          
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];//          Entry  
        table[bucketIndex] = new Entry<>(hash, key, value, e);//           ，          。 next       Entry
        size++;
    }

이 resize 방법 은 바로 확장 방법 입 니 다.

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];//     
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);//                
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {//     Entry,  
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

6. 확장 작업 은 새로운 배열 을 열 어야 하고 원래 배열 의 모든 키 값 을 다시 해시 시 켜 야 합 니 다. 시간 이 많이 걸 립 니 다.우 리 는 가능 한 한 HashMap 의 확장 을 피해 야 한다.
get 방법 다시 보기:

public V get(Object key) {
        if (key == null)//    
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);//  Entry  
//      null，          
        return null == entry ? null : entry.getValue();
    }

이 getForNullKey 방법 은 배열 0 색인 위치 에 있 는 링크 에서 null 키 를 찾 는 것 입 니 다.

 private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

이 getEntry 방법 은 키 를 통 해 hash 값 을 생 성 한 다음 에 배열 의 색인 위 치 를 얻 고 이 위치의 링크 를 찾 아 첫 번 째 만 족 스 러 운 키 를 찾 아 Entry 대상 으로 돌아 가 는 것 입 니 다.

final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

remove 방법 다시 보기:

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key);//   hash 
        int i = indexFor(hash, table.length);//     
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        while (e != null) {//        ，           
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

마지막 으로 clear 방법 을 보 겠 습 니 다.

 public void clear() {
        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)//    
            tab[i] = null;//  
        size = 0;
    }

요약:
1. HashMap 의 기본 크기 는 16 입 니 다. 즉, 통 배열 의 기본 길 이 는 16 입 니 다.
2. HashMap 의 기본 적재 인 자 는 0.75 입 니 다.
3. HashMap 내부 의 통 배열 은 Entry 대상, 즉 키 쌍 대상 을 저장 합 니 다.
4. 구조 기 는 초기 용량 과 적재 인 자 를 지정 하 는 것 을 지원 하고 배열 의 확장 에 따 른 성능 문 제 를 피하 기 위해 수요 에 따라 초기 용량 을 지정 하 는 것 을 권장 합 니 다.적재 인 자 는 가능 한 한 수정 하지 마 세 요. 0.75 는 비교적 믿 을 만 한 값 입 니 다.
5. 통 배열 의 길 이 는 항상 2 의 정수 제곱 (지정 한 초기 용량 보다 크다) 이다. 이렇게 하면 충돌 확률 을 줄 이 고 검색 효율 을 높 일 수 있다.(indexfor 함수 에서 볼 수 있 듯 이 h & (length - 1), length 가 홀수 라면 length - 1 이 짝수 라면 h & (length - 1) 결과 의 마지막 자 리 는 반드시 0 이다. 즉, 모든 키 가 배열 의 짝수 아래 표 시 된 위치 로 흩 어 져 절반 에 가 까 운 공간 을 낭비 하 는 것 이다. 또한 length 가 2 인 정수 차방 도 h & (length - 1) 와 h% length 등 효 과 를 보장 한다.)
6. HashMap 에서 null 키 받 기;
7. HashMap 은 키 중복 을 허용 하지 않 지만 값 은 중복 할 수 있 습 니 다.키 가 반복 되면 새 값 은 오래된 값 을 덮어 씁 니 다.
8. HashMap 은 링크 법 을 통 해 충돌 문 제 를 해결 합 니 다. 모든 Entry 는 next 포인터 가 다음 Entry 를 가리 키 고 충돌 요소 (키 가 같 지 않 고 hash 값 이 같 음) 는 링크 를 구성 합 니 다.또한 최근 에 삽 입 된 키 쌍 은 링크 의 첫 부분 에 있 습 니 다.
9. 용량 이 한도 값 (threshold) 을 초과 할 때 확장 이 발생 하고 확장 후의 배열 은 원래 배열 의 두 배 이다.확장 작업 은 새로운 배열 을 열 어야 하 며, 원래 배열 의 모든 키 값 을 다시 분산 시 키 는 데 시간 이 많이 걸린다.우 리 는 가능 한 한 HashMap 의 확장 을 피해 야 한다.
10. HashMap 비 스 레 드 안전.