HashMap 의 6 가지 지식

7328 단어 자바 기반
HashMap 의 6 가지 지식 포인트:
1.    HashMap 개요:
   HashMap 은 key - value 데이터 구조 로 해시 표 의 Map 인터페이스 에 기반 한 비 동기 화 실현 입 니 다.이 는 선택 할 수 있 는 모든 맵 작업 을 제공 하고 key 와 value 를 null 로 허용 합 니 다.비 치 는 순 서 를 보장 하지 않 습 니 다. 특히 이 순 서 는 영원히 변 하지 않 습 니 다.
 
2.    HashMap 의 데이터 구조:
   HashMap 은 실제 적 으로 '산 목록' 의 데이터 구조, 즉 배열 과 링크 의 결합 체 이다.JDK 8 에서 HashMap 의 밑 층 은 배열 + 링크 + 빨 간 검 은 나무 입 니 다.
주: HashMap 에 데 이 터 를 저장 하 는 Entry 배열 의 한 통 의 링크 가 8 개의 요소 가 있 을 때 빨간색 과 검은색 나무 가 될 수 있 습 니 다. 산 목록 의 총 용량 이 64 보다 클 때 빨간색 과 검은색 나무 로 변 할 수 있 습 니 다.
3.    HashMap 읽 기 구현:
HashMap 에 데 이 터 를 저장 하 는 데 put () 방법 을 사용 합 니 다. 이 방법 은 먼저 String 을 호출 하 는 hashCode () 방법 으로 hashCode 값 을 얻 을 수 있 습 니 다. 자바 대상 마다 hashCode () 방법 이 있 습 니 다. 이 방법 을 통 해 hashCode 값 을 얻 을 수 있 습 니 다.이 대상 의 hashCode 값 을 얻 으 면 시스템 은 이 hashCode 값 에 따라 이 요소 의 저장 위 치 를 결정 합 니 다.이 위치 에 키 값 이 존재 한다 면, 해시 충돌 이 발생 합 니 다.
How: HashMap 은 해시 충돌 을 어떻게 해결 합 니까?
체인 주소 법: 충돌 하 는 위치 에 링크 를 새로 만 든 다음 에 충돌 하 는 요 소 를 링크 끝 에 삽입 하 는 것 입 니 다.
HashMap 에서 get () 방법 으로 value 를 가 져 올 때 먼저 key 의 hashcode () 값 에 따라 해당 하 는 Entry 배열 위치 로 이동 한 다음 에 하나의 key 만 있 으 면 value 로 돌아 갑 니 다. 이 배열 위치 에 링크 가 여러 개의 key 를 유지 하고 있다 면 equals (key) 를 사용 하여 해당 하 는 value 값 을 가 져 옵 니 다.HashMap 의 4 가지 스 트 리밍 방식
4.    HashMap 의 resize (rehash):
   HashMap 의 요소 가 점점 많아 질 때 hash 충돌 확률 도 점점 높 아 집 니 다. 배열 의 길이 가 고정 되 어 있 기 때 문 입 니 다.따라서 조회 의 효율 을 높이 기 위해 HashMap 의 배열 을 확대 해 야 한다. 배열 확장 이라는 작업 도 Array List 에 나타 날 것 이다. 이것 은 자주 사용 하 는 작업 이다. HashMap 배열 이 확 대 된 후에 가장 성능 을 소모 하 는 점 이 나 타 났 다. 원래 배열 의 데 이 터 는 반드시 새로운 배열 에 있 는 위 치 를 다시 계산 하고 넣 어야 한다. 이것 이 바로 resize 이다.
 What:  그럼 HashMap 은 언제 확장 되 나 요?
HashMap 의 요소 개수 가 배열 크기 * loadFactor 를 초과 할 때 배열 확장 을 진행 합 니 다. loadFactor 의 기본 값 은 0.75 입 니 다. 이것 은 절 충 된 값 입 니 다.즉, 기본 적 인 상황 에서 배열 의 크기 는 16 이다. 그러면 HashMap 에서 요소 의 개수 가 16 * 0.75 = 12 를 초과 할 때 배열 의 크기 를 2 * 16 = 32, 즉 배로 확대 한 다음 에 모든 요소 가 배열 에 있 는 위 치 를 다시 계산한다. 이것 은 매우 소모 적 인 작업 이기 때문에 만약 에 우리 가 HashMap 에서 요소 의 개 수 를 미리 알 았 다 면그러면 미리 설 정 된 요소 의 개 수 는 HashMap 의 성능 을 효과적으로 향상 시 킬 수 있 습 니 다.
5.    HashMap 의 성능 매개 변수:
   HashMap 에는 다음 과 같은 4 개의 구조 기 가 포함 되 어 있 습 니 다.
   HashMap (): 초기 용량 이 16 이 고 부하 인자 가 0.75 인 HashMap 을 구축 합 니 다.
   HashMap (int initialCapacity): 초기 용량 이 initialCapacity 이 고 부하 인자 가 0.75 인 HashMap 을 구축 합 니 다.
   HashMap (int initialCapacity, float loadFactor): 초기 용량 을 지정 하고 지정 한 부하 인자 로 HashMap 을 만 듭 니 다.
   HashMap (Map m): 같은 맵 으로 새로운 HashMap 을 구성 하여 HashMap 기본 부하 인자 (0.75) 와 충분 한 초기 용량 을 지정 한 맵 에 저장 합 니 다.
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

   HashMap 의 기본 구조 기 HashMap (int initial Capacity, float loadFactor) 은 두 개의 인 자 를 가지 고 있 으 며, 초기 용량 initial Capacity 와 로드 인자 loadFactor 입 니 다.
   initial Capacity: HashMap 의 최대 용량, 즉 바 텀 배열 의 길이 입 니 다.
   loadfactor: 부하 인자 loadfactor 는 산 목록 의 실제 요소 수 (n) / 산 목록 의 용량 (m) 으로 정의 합 니 다.
   부하 인 자 는 산 목록 의 공간의 사용 정 도 를 평가 하고 부하 인자 가 클 수록 산 목록 의 충전 정도 가 높 고 반대로 작 음 을 나타 낸다.링크 법의 산 목록 을 사용 할 때 하나의 요 소 를 찾 는 평균 시간 은 O (1 + a) 이기 때문에 부하 인자 가 클 수록 공간 에 대한 이용 이 더욱 충분 하지만 결 과 는 검색 효율 이 떨어진다.부하 인자 가 너무 작 으 면 산 목록 의 데이터 가 너무 적어 공간 에 심각 한 낭 비 를 초래 할 것 이다.
6.    Fail - Fast 메커니즘:
   자바 util. HashMap 은 스 레 드 가 안전 하지 않다 는 것 을 알 고 있 습 니 다. 따라서 교체 기 를 사용 하 는 과정 에서 다른 스 레 드 가 map 를 수정 하면 Concurrent ModificationException 을 던 집 니 다. 이것 이 바로 fail - fast 전략 입 니 다.
   이 정책 은 원본 코드 에서 modCount 역 을 통 해 이 루어 집 니 다. modCount 는 말 그대로 횟수 를 수정 하 는 것 입 니 다. HashMap 내용 에 대한 수정 은 이 값 을 증가 시 킵 니 다. 그러면 교체 기 초기 화 과정 에서 이 값 을 교체 기의 expected ModCount 에 부여 합 니 다.
모든 HashMap 류 의 "collection 보기 방법" 에서 되 돌아 오 는 교체 기 는 빠 른 속도 로 실 패 했 습 니 다. 교체 기 를 만 든 후에 구조 적 으로 맵 을 수정 하면 교체 기 자체 의 reove 방법 을 통 해 다른 모든 방식 으로 수정 되 지 않 는 한 교체 기 는 Concurrent ModificationException 을 던 집 니 다.따라서 동시 다발 적 인 수정 에 직면 하여 교체 기 는 곧 완전히 실패 할 것 이 며 앞으로 불확실 한 시간 에 임 의적 으로 불확실 한 행위 가 발생 할 위험 을 무릅 쓰 지 않 을 것 이다.
   주의: 교체 기의 빠 른 실패 행 위 는 보장 되 지 않 습 니 다. 일반적으로 동기 화 되 지 않 은 병행 수정 이 존재 할 때 어떠한 단호 한 보증 도 할 수 없습니다.빠 른 실패 교체 기 는 Concurrent ModificationException 을 던 지기 위해 최선 을 다 합 니 다.따라서 이 이상 한 프로그램 에 의존 하 는 방법 은 잘못 되 었 습 니 다. 정확 한 방법 은 교체 기의 빠 른 실패 행 위 는 프로그램 오 류 를 검사 하 는 데 만 사용 되 어야 합 니 다.
나의 좌우명: 아니 야, 배 울 수 있어.뒤떨어 지면 나 는 따라 잡 을 수 있다.넘 어 지면 나 는 일어 설 수 있다.나 는 반드시 할 수 있다.

좋은 웹페이지 즐겨찾기