자바 HashMap 내부 실현 원리 상세 설명

HashMap 내부 실현 원리 상세 설명
내부 데이터 구조

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

위의 데이터 구조 정 의 를 통 해 알 수 있 듯 이 HashMap 저장 요 소 는 키 가 맞 는 링크 입 니 다.어떤 형식 으로 저장 합 니까?

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

이 를 통 해 알 수 있 듯 이 배열 로 저장 되 어 있 습 니 다.좋 습 니 다.지금 우 리 는 HashMap 은 배열 로 저장 되 어 있 습 니 다.각 배열 에는 키 쌍 이 있 습 니 다.이 키 쌍 은 다음 키 쌍 으로 연결 할 수 있 습 니 다.다음 그림 에서 보 듯 이:

hashmap 추가

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
      inflateTable(threshold);
    }
    if (key == null)
      return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> 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;
  }

여기 서 알 수 있 듯 이 hashmap 의 추 가 는 먼저 하나의 entry 의 hash 속성 에 따라 해당 하 는 table 요소 i 를 찾 은 다음 에 이 위치 에 요소 가 존재 하 는 지 확인 하고 없 으 면 직접 넣 습 니 다.있 으 면 이번 링크 를 옮 겨 다 니 며 표 끝 에 추가 합 니 다.
삭제

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
      return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    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;
  }

삭제 하면 hash 에 따라 table 배열 에서 찾 은 다음 equals 에 따라 링크 에서 찾 습 니 다.이것 도 hashmap 과 hashset 등 hash 방식 으로 저 장 된 데이터 구조 가 두 가지 방법 으로 hashcode 와 equalsd 를 실현 하 는 이유 입 니 다.
hash 를 배 운 사람 은 모두 알 고 있 습 니 다.hash 표 의 성능 은 hash 충돌 발생 횟수 와 매우 큰 관계 가 있 지만 너무 긴 table 표를 신청 하여 공간 을 낭비 할 수 없 기 때문에 여기 에는 우리 의 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];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  }

이 방법 은 put 에서 호출 됩 니 다.위 put 에서 addEntry(hash,key,value,i)를 먼저 호출 합 니 다.방법,그리고 addEntry 방법 보기

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);
  }

위 에서 알 수 있 듯 이 HashMap 은 HashMap 의 요소 개수 가 배열 크기*loadFactor 를 초과 할 때 배열 확장 을 진행 합 니 다.loadFactor 의 기본 값 은 0.75 이 고 이것 은 절 충 된 수치 입 니 다.즉,기본 적 인 상황 에서 배열 의 크기 는 16 이다.그러면 HashMap 에서 요소 의 개수 가 16*0.75=12 를 초과 할 때 배열 의 크기 를 2*16=32,즉 배로 확대 한 다음 에 모든 요소 가 배열 에 있 는 위 치 를 다시 계산한다.이것 은 매우 소모 적 인 작업 이기 때문에 만약 에 우리 가 HashMap 에서 요소 의 개 수 를 미리 알 았 다 면그러면 미리 설 정 된 요소 의 개 수 는 HashMap 의 성능 을 효과적으로 향상 시 킬 수 있 습 니 다.
읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!