HashMap - 내부 저장 소

번역 하 다http://coding-geek.com/how-do...원문 에 기초 하여 수정 과 보충 을 하 였 다
자바 HashMap 류 는 Map 인 터 페 이 스 를 실현 했다. 이 인터페이스의 몇 가지 주요 방법 은 다음 과 같다.단 방향 무질서 링크 와 유사 합 니 다.hash 값 입 니 다. 이것 은 K 에 대응 하 는 hash 값 입 니 다. HashMap 을 사용 할 때마다 다시 계산 하지 않도록 합 니 다.JDK 7 에서 Entry 의 부분 은 다음 과 같다.

static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;
        int hash;
}

HashMap 은 데 이 터 를 여러 개의 Entry 링크 에 저장 한 다음 에 모든 링크 는 Entry 배열 에 등록 하여 하나의 bucket 에 대응 합 니 다.이 초기 배열 의 크기 는 16 (DEFAULT INITIAL CAPACITY) 입 니 다.
HashMap 에 통 (bucket) 이라는 개념 이 있 습 니 다. 사실 이 통 은 entry 배열 (HashMap 초기 화 시 고정 크기 의 배열 을 만 듭 니 다) 의 요소 입 니 다. 다음 과 같 습 니 다.

 /**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

같은 hash value 가 있 는 key 는 같은 통 에 넣 고 entry 사이 에 포인터 로 연결 되 어 링크 를 구성 합 니 다.HashMap 의 put 또는 get 방법 을 호출 할 때 방법 은 먼저 key 의 hash 값 을 계산 한 다음 에 어떤 bucket 에 속 해 야 하 는 지 계산 합 니 다.통 을 찾 은 후 bucket 에 대응 하 는 entry 링크 를 옮 겨 다 니 며 해당 하 는 key 값 을 찾 습 니 다. 링크 안의 검 사 는 key 의 equals 방법 을 통 해 이 루어 집 니 다.이 단계 의 코드 는 다음 과 같 습 니 다 (JDK 7): 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;
}

map 생 성 통 은 다음 세 단 계 를 거 쳐 야 합 니 다.

 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
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);
}  

주석 에 따 르 면 HashMap 은 이러한 보충 함 수 를 제공 합 니 다. HashCode 에 작용 하 는 것 은 불안정 한 hash 함수 로 인 한 충돌 을 방지 하기 위해 서 입 니 다. 이 함 수 는 '스 포 일 러 함수' 라 고 합 니 다.

 /**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

왜 hash 를 다시 계산 해 야 합 니까? 밤 을 들 어 보 세 요. shinadata 문자열 의 Hash Code 의 binary 는 1000011100010011001001 입 니 다. 상기 코드 의 length 는 배열 (Entry [] table) 의 길이 입 니 다.(length – 1) = 15, 15 의 바 이 너 리 는 1111 입 니 다. rehash 작업 을 하지 않 으 면 1111 고위 보 0, 100001101000110010001 과 비트 와 & 연산 을 합 니 다. 그러면 shinadata 의 Hash Code 는 계산 과정 에서 마지막 몇 자리 만 작용 할 수 있 습 니 다. 높 은 자리 가 얼마 든 낮은 자리 만 같 으 면 마지막 결 과 는 같 습 니 다. 이렇게 index For 방법 으로 계산 합 니 다.의 index 값 은 충돌 하기 쉽다. 교란 함수 의 작용 은 이 방면 의 영향 을 없 애기 위 한 것 이다.
왜 내부 배열 의 크기 는 2 의 멱 입 니까? 배열 의 크기 가 17 이 라 고 가정 하면 마스크 값 은 16 (size - 1) 입 니 다.이 진 은 0... 010000 입 니 다. 현재 모든 해시 값 h, h & 16 에서 색인 을 얻 으 면 16 이 아니면 0 입 니 다. 그러면 배열 크기 17, 사용 하 는 통 은 2 개 에 불과 합 니 다. 그러나 2 의 멱 값 을 사용 하면 다 릅 니 다. 예 를 들 어 16, size - 1 = 15, 2 진 제 는 0.. 001111, h & 15 에서 얻 은 색인 값 은 0 ~ 15 입 니 다. 이 부분 에서 JDK 7 의 소스 코드 를 볼 수 있 습 니 다.。http://hg.openjdk.java.net/jd...참고:https://blog.csdn.net/wenyiqi...https://www.zhihu.com/questio...번역 하 다http://coding-geek.com/how-do...원문 에 기초 하여 수정 과 보충 을 하 였 다