HashMap 소스 코드 분석 (Android & Java)

HashMap 소스 코드 분석 (Android & Java)
전재 출처 chendong
http://blog.csdn.net/chendong_/article/details/49834325
앞 에 쓰다
기본 적 인 데이터 구 조 는 배열, 링크, 트 리, 그림 이 있다.
배열 의 특징 은 길이 가 고정 되 고 공간 이 연속 되 며 메모리 사용량 이 많 으 며 공간 복잡 도 는 O (n) 이지 만 주소 찾기 가 쉽 고 시간 복잡 도 O (1) 이다.
요약: 주소 찾기 가 쉽 고 삽입 삭제 가 어렵 습 니 다.
링크 의 특징 은 길이 가 가 변 적 이 고 저장 공간 이 분 산 된 것 이 며 차지 하 는 메모리 가 적 으 며 공간 복잡 도 는 O (1) 이지 만 주소 찾기 가 어렵 고 시간 복잡 도 는 O (n) 이다.
요약: 주소 찾기 가 어렵 고 삽입 삭제 가 쉽 습 니 다.
해시 표 는 배열 구 조 를 바탕 으로 키 값 으로 데 이 터 를 저장 합 니 다. 삽입 삭제 가 쉽 습 니 다. 주 소 는 키 값 에 따라 데 이 터 를 직접 찾 습 니 다. 시간 복잡 도 는 O (1) 이지 만 해시 값 으로 데 이 터 를 저장 하면 해시 충돌 이 발생 합 니 다. 해시 충돌 을 해결 하 는 방법 은 주로 주소 법 (재 산열), 재 해시 법, 체인 주소 법 (지퍼 법) 이 있 습 니 다.공공 넘 침 구역 을 만들다.
단점: 저장 공간 을 채 울 때 다른 더 큰 배열 구조 로 복사 하고 재 하 쉬 계산 을 해 야 한다. 이것 은 하 쉬 표 메모리 가 차지 하 는 폭등 점 이다. 이것 은 배열 구 조 를 바탕 으로 하 는 단점 이다.
해시 표 는 데이터 구조 에 있 는 모든 데 이 터 를 특정한 순서 로 옮 겨 다 닐 수 없습니다. 순서대로 저장 해 야 한다 면 해시 표를 사용 하 는 것 은 적절 하지 않 습 니 다.
그림 한 장 붙 이 고,
시작 하 다
1. HashMap 은 라인 이 안전 하지 않 은 HashTable 입 니 다. 라인 이 안전 합 니 다.
2. HashMap 은 체인 주소 법 을 바탕 으로 하 는 데이터 저장 이다.바로 링크 의 배열 이다.
3. HashMap 은 키 값 을 null 로 허용 합 니 다.Hash Table 은 허용 되 지 않 습 니 다.
4. 안 드 로 이 드 와 자바 에서 HashMap 의 실현 에 대해 조금 다르다. 처음에 나 는 나의 jdk 에 문제 가 있 는 줄 알 았 다.
5. HashMap 의 기초 배열 에서 모든 배열 항목 을 하나의 통 이 라 고 부 르 는데 HashMap 은 바로 이런 통 + 링크 의 구 조 를 바탕 으로 한다.
6. 저장 방식 은 key 값 으로 하 시 를 가 져 옵 니 다. 일반적인 알고리즘 은 hash (key) / len 이 저장 위치 에 있 는 아래 표 시 를 가 져 오 면 key 를 아래 표 와 대응 합 니 다.
이해 하 다.
원본 코드:private transient Set<Entry<K, V>> entrySet; transient HashMapEntry<K, V>[] table;
요약 하면 HashMap 은 배열 + 내부 류 (Entry) 가 실현 되 고 Entry 에서 다음 Entry 의 인용 을 가지 기 때문에 링크 의 구 조 를 구성 했다.전에 봤 는데 Set + 정적 내부 류 라 고 소 개 했 는데 사실은 아니에요.첫 번 째 줄 의 코드 는 HashMap 을 조작 할 때 사용 하 는 변수 입 니 다. 예 를 들 어 HashMap 의 모든 하위 항목 을 교체 하고 Entry Set 을 HashMap 에 추가 하여 삭제 하고 수정 합 니 다.
1.HashMapEntry
HashMap 에는 매우 중요 한 저장 구조 인 HashMapEntry 가 있 습 니 다. 키 값 쌍 을 저장 하고 다음 Entry 와 의 인용 을 저장 하 는 데 사 용 됩 니 다. 이것 은 하나의 링크 구 조 를 형성 합 니 다.
자바 에서 이 정적 내부 클래스 를 Entry 라 고 합 니 다.

static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;
    HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }
    public final K getKey() {
        return key;
    }
    public final V getValue() {
        return value;
    }
    public final V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    @Override public final boolean equals(Object o) {
        if (!(o instanceof Entry)) {
            return false;
        }
        Entry<?, ?> e = (Entry<?, ?>) o;
        return Objects.equal(e.getKey(), key)
                && Objects.equal(e.getValue(), value);
    }
    @Override public final int hashCode() {
        return (key == null ? 0 : key.hashCode()) ^
                (value == null ? 0 : value.hashCode());
    }

    @Override public final String toString() {
        return key + "=" + value;
    }
}

2. 해시 값 의 계산
저장 데 이 터 는 key 의 해시 값 에 따라 저 장 됩 니 다. 이러한 방법 hash (key. hashcode ()) 와 유사 합 니 다.
자바 와 안 드 로 이 드 에 서 는 해시 값 을 구 하 는 동작 이 비슷 하지만 해시 알고리즘 이 다 르 기 때문에 액세스 작업 을 할 때 key 는 이 알고리즘 을 사용 하여 중 전 됩 니 다.
Android 에 서 는 Collections 클래스 의 정적 방법 과 해시 계산 을 사용 합 니 다. 그러나 여기 서 h 는 key 의 hashcode () 입 니 다. 주석 을 보면 Wang / Jenkins 해시 알고리즘 의 변형, 소스 코드 를 사용 합 니 다.

private static int secondaryHash(int h) {
    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

자바 에서 해시 알고리즘 은 이러한 종류 에서 이 루어 집 니 다. 안 드 로 이 드 보다 훨씬 간결 합 니 다. 비록 저 는 아직 잘 모 르 겠 지만.

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

3. puut 방법
키 가 비어 있 는 지 확인 하 십시오. null 은 forNullEntry 가 있 는 링크 에 저 장 됩 니 다.
해시 값 을 가 져 온 후에 아래 표 시 된 색인 을 얻 습 니 다. key 가 이미 존재 하 는 지 확인 하고 바 꿉 니 다. 그렇지 않 으 면 현재 링크 에 추가 합 니 다. 기본 사상 은 이 렇 습 니 다. 몇 가지 다른 점 입 니 다.
puutForNullKey (value) 방법 은 Android 와 자바 에서 모두 실 현 됩 니 다. 키 값 이 null 일 때 한 배열 의 하 나 를 할당 합 니 다. 이 배열 은 key = = null 의 Entry 를 가리 키 고 있 습 니 다.
자바 에 서 는 Entry 를 추가 한 후 용량 을 다시 계산 하 는 것 이 고, 안 드 로 이 드 는 AddNewEntry 이전에 진행 된다.
용량 을 늘 리 는 방법 은 모두 원래 의 두 배로 확대 하 는 것 이다.
자바 에서 의 구현 코드:

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

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

Android 에서 의 실현 은 기본적으로 유사 합 니 다. Collections 정적 방법 으로 2 차 해시 계산 을 하고 표 색인 을 계산 합 니 다.

@Override 
public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }
    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
        if (e.hash == hash && key.equals(e.key)) {
            preModify(e);
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // No entry for (non-null) key is present; create one
    modCount++;
    //                
    if (size++ > threshold) {
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);
    return null;
}
//Android         ，       ，   java     。      // ，     ，     InputStream is = new FileInputStream("path")is = new BufferedInputStream(is)`
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

4. get 방법
같은 hashcode 를 가 져 오고 해시 값 을 계산 하여 아래 표 시 된 색인 을 얻 고 해당 하 는 링크 를 얻 으 며 링크 를 옮 겨 다 니 며 결 과 를 얻 으 며 자바 와 안 드 로 이 드 에서 대동소이 함 을 실현 합 니 다.
자바 의 실현

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        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.equals(k)))
                return e.value ;
        }
        return null;
    }

Android 의 실현

public V get(Object key) {
    if (key == null) {
        HashMapEntry<K, V> e = entryForNullKey;
        return e == null ? null : e.value;
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
            e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return e.value;
        }
    }
    return null;
}

5. 초기 화
자바 와 안 드 로 이 드 에서 HashMap 의 초기 화 는 약간 다 릅 니 다. 아버 지 를 너무 괴 롭 혔 습 니 다.
안 드 로 이 드 의 초기 용량 은 2 이 고 자바 의 초기 용량 은 16 이다.
자바 의 초기 용량 과 부하 인 자 는 자바 가 비교적 전형 적 인 내용 을 배 우 는 것 입 니 다. 자바 에서 HashMap 의 기본 구조 방법 을 보 세 요.

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
//                16，    0.75 HashMap,threshold      ，             ,              。
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int )(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR );
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

매개 변수 가 있 는 구조 방법 실현

//                            ，              -》          -》   2  （      7--》8   9--》16）
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
//    ：capacity   1， capacity  initialCapacity     ，  *2,                2  
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int )(capacity * loadFactor);
table = new Entry[capacity];
init();
}
//    ，transfer(newTable);                
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];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

Android 에서 의 실현

//          4，                      1 ，   2，     ，         table,          （ Forces first put invocation to replace EMPTY_TABLE），        put            ，       -1，          ，        Android                   。。 put              ，      doubleCapacity()     ，         

private static final int MINIMUM_CAPACITY = 4;
private static final Entry[] EMPTY_TABLE
        = new HashMapEntry[MINIMUM_CAPACITY >>> 1];
public HashMap() {
    table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
    threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
//               ，    ， Java    ，        3/4     ，Java          ， Math.min(  ，)
private HashMapEntry<K, V>[] doubleCapacity() {
    HashMapEntry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        return oldTable;
    }
    int newCapacity = oldCapacity * 2;
    HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
    if (size == 0) {
        return newTable;
    }

    for (int j = 0; j < oldCapacity; j++) {
        /* * Rehash the bucket using the minimum number of field writes. * This is the most subtle and delicate code in the class. */
        HashMapEntry<K, V> e = oldTable[j];
        if (e == null) {
            continue;
        }
        int highBit = e.hash & oldCapacity;
        HashMapEntry<K, V> broken = null;
        newTable[j | highBit] = e;
        for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
            int nextHighBit = n.hash & oldCapacity;
            if (nextHighBit != highBit) {
                if (broken == null)
                    newTable[j | nextHighBit] = n;
                else
                    broken.next = n;
                broken = e;
                highBit = nextHighBit;
            }
        }
        if (broken != null)
            broken.next = null;
    }
    return newTable;
}
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
    @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
            = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
    table = newTable;
    //       3/4,      
    threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
    return newTable;
}
//       ，         ，  Collections     Collections.roundUpToPowerOfTwo(capacity);，      ，                2  。         ，        。
public HashMap(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("Capacity: " + capacity);
    }

    if (capacity == 0) {
        @SuppressWarnings("unchecked")
        HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
        table = tab;
        threshold = -1; // Forces first put() to replace EMPTY_TABLE
        return;
    }

    if (capacity < MINIMUM_CAPACITY) {
        capacity = MINIMUM_CAPACITY;
    } else if (capacity > MAXIMUM_CAPACITY) {
        capacity = MAXIMUM_CAPACITY;
    } else {
        capacity = Collections.roundUpToPowerOfTwo(capacity);
    }
    makeTable(capacity);
}

//    ，              ，          
public static int roundUpToPowerOfTwo(int i) {
    i--; // If input is a power of two, shift its high-order bit right.

    // "Smear" the high-order bit all the way to the right.
    i |= i >>>  1;
    i |= i >>>  2;
    i |= i >>>  4;
    i |= i >>>  8;
    i |= i >>> 16;

    return i + 1;
}

6. JDK 1.8 은 용량 이 너무 클 때 레 드 블랙 트 리 로 데 이 터 를 저장 하 는데 사건 의 복잡 도 O (logn) 는 레 드 블랙 트 리 에 대해 잘 모 르 고 알고리즘 이 좋 지 않 으 니 잠시 두 세 요.
7. 한도 값 = 용량 * 부하 인 자 는 용량 이 한도 값 을 초과 할 때 확장 과 재 산열 을 한다. 이때 hashmap 의 메모리 가 차지 하 는 성장 점 이 고 확장 은 용량 을 원래 의 두 배로 확대 한 다음 에 데 이 터 를 새로운 구역 으로 복사 하여 재 산열 한다.그러나 여기 서 잘 모 르 는 문제 가 있 습 니 다. HashMap 확장 은 하나의 요소 size + 를 추가 할 때마다 size > 한도 값 (용량 * 부하 인자) 을 추가 할 때 확장 합 니 다. 그러나 HashMap 은 배열 + 링크 를 바탕 으로 하 는 것 이기 때문에 추 가 된 요 소 는 하나의 배열 항목 에 집중 되 지 않 습 니 다.예 를 들 어 하나의 hashmap 용량 이 16 이 고 한도 값 은 12 이다. 이때 추 가 된 요 소 는 12 개가 있 지만 특정한 배열 항목 이 있 는 링크 에 만 집중 된다 면 이때 확대 하 는 것 이 적당 합 니까?일시 적 으로 합 리 적 인 해석 은 hash () 알고리즘 이 모든 배열 항목 에 데 이 터 를 잘 분산 시 킬 수 있다 는 것 이다. 그러면 이런 비교 도 비교적 합 리 적 이다.
8. 왜 초기 용량 을 이 용량 보다 작은 2 의 멱 으로 계산 해 야 합 니까?우 리 는 이 코드 int index = hash & (tab.length - 1); 가 자바 에서 같은 디자인 을 가지 고 있 는 것 을 볼 수 있 습 니 다. 하나의 함수 indexfor(int hash) 가 hashcode 에 대응 하 는 배열 아래 표 시 를 계산 할 때 hash & len - 1 을 사용 하여 hash% len 을 대 체 했 습 니 다. len 이 2 의 멱 일 때 만 이 두 가지 방법 은 등가 가 같 지 않 습 니 다.이해 하기 어 려 울 수도 있 습 니 다. 예 를 들 어 len 은 16 시, 2 진법 10000, len - 1 은 01111 입 니 다. 만약 에 얻 은 hash 가 16 보다 적 으 면 예 를 들 어 3 이 죠? 진행 & 연산 01111 & 00011 이 얻 은 결 과 는 3 입 니 다. 즉, 그 자체 입 니 다.확실히 3% 16 과 같 습 니 다. 예 를 들 어 16 보다 크 면 19 입 니 다. 아무리 크 더 라 도 하나의 뜻 입 니 다. 즉, 01111 & 10011 이 얻 은 결 과 는 3 입 니 다. 등가 가 19% 16 이 고 오른쪽 5 위 이상 의 1 이 모두 걸 러 졌 습 니 다. 이렇게 많은 것 은 hash & len - 1 등가 가 hash% len 이라는 것 을 설명 하 는 것 일 뿐 입 니 다. 그러나 사용 비트 연산 효율 이 크게 향상 되 고 소스 코드 에서 비트 연산 을 곳곳에서 볼 수 있 습 니 다.ps: 저 는 항상 다른 역할 이 있다 고 생각 하지만 알 지 못 했 어 요.
종합 적 으로 HashMap 소스 코드 의 읽 기 입 니 다. 저 와 토론 하 시 는 것 을 환영 합 니 다.