원본, JDK 부터.

HashMap
JDK 1.8
HashMap 은 Map 실현 에서 데이터 구 조 를 가장 자주 사용 합 니 다.다음은 HashMap 의 구체 적 인 실현 에 착안 하여 내부 원 리 를 탐구 하고 주로 다음 과 같은 몇 가지 측면 에서 출발 할 것 이다.

내부 저장 구조;

초기 화 과정;

요소 의 삽입;

원소 의 획득;

내부 구조
내부 의 저장 구 조 는 Node 배열 이 고 설명 을 보면 배열 은 HashMap 이 처음 사용 할 때 초기 화 됩 니 다.배열 은 필요 할 때 확장 을 한다.배열 길 이 는 2 의 미터 로 유 지 됩 니 다.

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node[] table;

Node 는 Map. Entry 인 터 페 이 스 를 실 현 했 습 니 다. 데이터 필드:

hash hash (key) 키 의 hash 값, 주소 찾기

key 키

value 값

next 충돌 해결 시 인용

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

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry,?> e = (Map.Entry,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

초기 화 과정
무 참 구조 함수

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

구조 함수 에서 위 에서 언급 한 Node[] table 을 초기 화하 지 않 고 기본 부하 인자 만 설정 한 것 을 발견 했다.
put()
실제로 HashMap 의 초기 화 는 처음 사용 할 때 (첫 번 째 호출 put() 발생 했 고 다음은 put() 의 실현 이다.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hash(key)
실제 호출 된 putVal(...) 이 방법 은 건 한 hash 값 을 계산 해 야 합 니 다. 이 hash 값 은 후속 요소 가 배열 의 위치 에 있 는 계산 에 사 용 될 것 입 니 다. 이것 은 HashMap 의 키 로 서 의 클래스 가 반드시 hashcode() 함 수 를 다시 써 야 하 는 이유 입 니 다.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash 값 의 알고리즘 (h = key.hashCode()) ^ (h >>> 16) 은 주로 배열 길이 가 2 인 n 차 멱 을 고려 하여 충돌 을 줄 이기 위해 서 입 니 다.
putVal(...) putVal(...) 에서 데 이 터 를 삽입 할 때 비로소 초기 화 를 시작 합 니 다.

(1): 첫 번 째 호출, table 이 비어 있 기 때문에 resize 단계

에 들 어 갑 니 다.

(2): resize() 의 과정 이 야 말로 진정한 초기 화 과정

(3): 밸브 값 을 초과 해도 수조 크기 를 다시 계산한다

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; 
    Node p; 
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0) // (1)
        n = (tab = resize()).length;                    // (2)
    //   ...
    if (++size > threshold)         // (3)
        resize();
    //   ...
    
}

resize()

(0): threshold 는 초기 화 지정 한 용량 에 따라 계 산 된 것 으로 구체 적 인 계산 과정 은 참고 tableSizeFor(initCapacity) 이 고 구조 함수 가 없 는 크기 는 16 이다.

(1): 처음 초기 화 했 을 때 new Cap 이 이 값 이 었 습 니 다.

(2): 새로운 밸브 값 계산 방식 은 부하 인 자 를 통 해 계산 할 수 있다.

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold; // (0)
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // ...
    }
    else if (oldThr > 0) // (1) initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) { // (2)
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    // ...
    return newTab;
}

tableSizeFor(initCapacity)
앞에서 알 았 듯 이 인자 가 없 는 구조 함 수 는 HashMap 의 크기 한도 값 threshold 을 기본 값 16 으로 설정 합 니 다.그러나 파 라 메 터 를 가 진 구조 함수 에서 HashMap 은 이 한도 값 을 계산 하여 HashMap 의 크기 가 2 인 정수 차 멱 을 확보 해 야 합 니 다.

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

n. 세 가지 상황 으로 나 뉜 다.

n < 0: 계 산 된 값 은 1 이다.

n = 0: 계 산 된 값 은 1 이다.

n > 0: 위의 계산 방법 은 모든 위 치 를 낮은 것 에서 높 은 것 으로 연속 적 인 1 로 설정 하고 마지막 n+1 은 capacity 크기 가 2 인 정수 차 멱 을 확보한다.

tableSizeFor(-1) = 1
tableSizeFor(0) = 1
tableSizeFor(1) = 1
tableSizeFor(3) = 4
tableSizeFor(4) = 4
tableSizeFor(5) = 8
tableSizeFor(10) = 16
tableSizeFor(30) = 32
tableSizeFor(1048576) = 1048576

여기 서 기본적으로 HashMap 의 초기 화 과정 을 알 게 되 었 습 니 다. 매개 변수 와 매개 변수 가 없 는 구조 함수 의 차 이 를 알 게 되 었 습 니 다. 다음은 HashMap 의 put(...) 과정 이 어떤 지 살 펴 보 겠 습 니 다.
put (...) 조작
앞에서 언급 한 HashMap 은 사실 첫 번 째 put (...) 작업 을 할 때 초기 화 된 작업 입 니 다. put () 방법 은 실제 puutVal () 방법 을 호출 했 습 니 다.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab;    //    table     
    Node p;        // p:    table[i]   
    int n, i;           // n:    table    ；i:      value           
    if ((tab = table) == null || (n = tab.length) == 0)     // (1)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)              // (2)
        tab[i] = newNode(hash, key, value, null);
    else {                                                  // (3)
        Node e; 
        K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

(1) table 배열 이 비어 있 는 지 (즉, 이 방법 을 처음 호출 하 는 지) 판단 합 니 다. 여기 서도 tab 와 n 임시 변수 에 값 을 부여 합 니 다.

true: 배열 을 초기 화 하 는 작업, 즉 앞에서 우리 가 언급 한 내용

false: 배열 이 초기 화 되 었 음 을 나타 낸다

(2) 알고리즘 (n-1)&hash(key) 을 통 해 현재 넣 을 value 의 위 치 를 확인 하고 이 위치의 값 을 얻어 비어 있 는 지 판단 한다.

= null: 이 위치 에 값 을 넣 은 적 이 없다 는 뜻 으로, 새로 만 든 노드 대상 을 직접 넣 습 니 다

!= null: 이 위치 에 값 을 넣 었 음 을 나타 내 며 충돌 처리 가 필요 합 니 다

(3) 충돌 처리

IF 만족 p.hash == hash & & p.key == key || (key != null && key.equals(p.key)) 즉, 삽입 요소 가 충돌 위치 에 있 는 요소 hash (key) 와 같 고 key 도 같은 요소 라 고 생각 하 는 것 이다.사용자 정의 대상 을 HashMap 키 로 사용 할 때 hashCode () 함 수 를 다시 쓰 고 hashCode 와 같은 두 대상 equlas () 도 true 가 되 어야 합 니 다.

IF 는 위의 조건 을 만족 시 키 지 못 하고 부 딪 히 는 위치의 요 소 는 하나의 TreeNode 로 나무 에 요 소 를 삽입 합 니 다.(일반적으로 우 리 는 HashMap 이 충돌 을 처리 하 는 방식 이 링크 라 는 것 을 알 고 있 지만 충돌 요소 가 너무 많 을 때 HashMap 은 나무의 방식 으로 처리 합 니 다)

ELSE 는 충돌 링크 를 옮 겨 다 니 며 첫 번 째 단계 와 판단 방식 이 같 지만 링크 요소 가 TREEIFY_THRESHOLD 를 초과 하면 트 리 의 저장 방식 으로 충돌 을 처리 하 는데 이것 이 두 번 째 IF 조건 이 존재 하 는 이유 이다.

HashMap 의 나무 부분 에 대해 서 는 소스 코드 를 계속 추적 할 수 있 습 니 다. 여 기 는 깊이 연구 하지 않 습 니 다.
get (...) 동작
get 작업 은 상대 적 으로 간단 합 니 다. 실제 호출 된 것 은 getNode(...) 방법 입 니 다.

final Node getNode(int hash, Object key) {
    Node[] tab; 
    Node first, e; 
    int n; 
    K k;
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

원본, JDK 부터. - HashMap.

좋은 웹페이지 즐겨찾기