자바 향상 편(2,3)-HashMap 상세 설명

HashMap 도 우리 가 매우 많이 사용 하 는 Collection 입 니 다.이것 은 해시 표 의 Map 인터페이스의 실현 을 바탕 으로 key-value 형식 으로 존재 합 니 다.HashMap 에서 key-value 는 항상 하나의 전체 로 처리 되 고 시스템 은 hash 알고리즘 에 따라 key-value 의 저장 위 치 를 계산 합 니 다.우 리 는 항상 key 를 통 해 빠 른 속도 로 저장 하고 value 를 얻 을 수 있 습 니 다.HashMap 의 접근 을 분석 해 보 겠 습 니 다.
정의
HashMap 은 Map 인 터 페 이 스 를 실현 하여 AbstractMap 을 계승 하 였 다.그 중에서 Map 인 터 페 이 스 는 키 가 값 에 비 치 는 규칙 을 정 의 했 고 AbstractMap 류 는 Map 인터페이스의 핵심 을 제공 하여 이 인 터 페 이 스 를 실현 하 는 데 필요 한 작업 을 최대한 줄 였 습 니 다.사실은 AbstractMap 류 는 Map 을 실 현 했 습 니 다.여기에 Map LZ 를 표시 하면 더욱 뚜렷 해 질 것 같 습 니 다!

public class HashMap<K,V>
  extends AbstractMap<K,V>
  implements Map<K,V>, Cloneable, Serializable

구조 함수
HashMap 은 세 개의 구조 함 수 를 제공 합 니 다.
HashMap():기본 초기 용량(16)과 기본 로드 인자(0.75)를 가 진 빈 HashMap 을 구성 합 니 다.
HashMap(int initialCapacity):초기 용량 과 기본 로드 인자(0.75)를 지정 한 빈 HashMap 을 구성 합 니 다.
HashMap(int initialCapacity,float loadFactor):초기 용량 과 로드 인 자 를 지정 한 빈 HashMap 을 구성 합 니 다.
여기 서 두 개의 매개 변 수 를 언급 했다.초기 용량,로드 인자.이 두 개의 매개 변 수 는 HashMap 의 성능 에 영향 을 주 는 중요 한 매개 변수 이다.그 중에서 용량 은 해시 표 의 통 수량 을 나타 내 고 초기 용량 은 해시 표를 만 들 때의 용량 이다.로드 인 자 는 해시 표 가 용량 이 자동 으로 증가 하기 전에 얼마나 가득 찬 척도 에 이 를 수 있 는 지 를 나타 낸다.이 는 산 목록 의 공간 사용 정 도 를 평가 하고 부하 인자 가 클 수록 산 목록 의 충전 정도 가 높다 는 것 을 나타 낸다.반대로 작 을 수록링크 법의 산 목록 을 사용 할 때 하나의 요 소 를 찾 는 평균 시간 은 O(1+a)이기 때문에 부하 인자 가 클 수록 공간 에 대한 이용 이 더욱 충분 하지만 결 과 는 검색 효율 이 떨어진다.부하 인자 가 너무 작 으 면 산 목록 의 데이터 가 너무 적어 공간 에 심각 한 낭 비 를 초래 할 것 이다.시스템 의 기본 부하 인 자 는 0.75 이 며,일반적인 상황 에서 우 리 는 수정 할 필요 가 없다.
HashMap 은 빠 른 접근 을 지원 하 는 데이터 구조 로 성능 을 알 기 위해 서 는 데이터 구 조 를 알 아야 합 니 다.
3.데이터 구조
자바 에서 가장 많이 사용 되 는 두 가지 구 조 는 배열 과 시 뮬 레이 션 포인터(참조)라 는 것 을 알 고 있 습 니 다.거의 모든 데이터 구 조 는 이 두 가지 로 조합 하여 실현 할 수 있 습 니 다.HashMap 도 마찬가지 입 니 다.실제로 HashMap 은'링크 해시'로 다음 과 같은 데이터 구조 입 니 다
위의 그림 에서 우 리 는 HashMap 의 밑바닥 이 실현 되 는 지,아니면 수조 가 실현 되 는 지 알 수 있다.단지 수조 의 모든 항목 이 하나의 체인 일 뿐이다.그 중에서 인자 initialCapacity 는 이 배열 의 길 이 를 대표 합 니 다.다음은 HashMap 구조 함수 의 소스 코드 입 니 다.

  public HashMap(int initialCapacity, float loadFactor) {
    //      <0
    if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal initial capacity: "
          + initialCapacity);
    //       >      ，HashMap       2^30
    if (initialCapacity > MAXIMUM_CAPACITY)
      initialCapacity = MAXIMUM_CAPACITY;
    //       < 0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
      throw new IllegalArgumentException("Illegal load factor: "
          + loadFactor);

    //       initialCapacity      2   n    。
    int capacity = 1;
    while (capacity < initialCapacity)
      capacity <<= 1;
    
    this.loadFactor = loadFactor;
    //  HashMap     ， HashMap                 
    threshold = (int) (capacity * loadFactor);
    //   table  
    table = new Entry[capacity];
    init();
  }

원본 코드 에서 볼 수 있 듯 이 HashMap 을 새로 만 들 때마다 table 배열 을 초기 화 합 니 다.table 배열 의 요 소 는 Entry 노드 입 니 다.

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

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
      value = v;
      next = n;
      key = k;
      hash = h;
    }
    .......
  }

그 중에서 Entry 는 HashMap 의 내부 클래스 로 키 키 키,값 value,다음 노드 next,그리고 hash 값 을 포함 합 니 다.이것 은 매우 중요 한 것 입 니 다.바로 Entry 로 인해 table 배열 의 항목 을 링크 로 구성 한 것 입 니 다.
위 에서 HashMap 의 데이터 구 조 를 간단하게 분 석 했 고 HashMap 이 어떻게 빠 른 접근 을 실현 하 는 지 연구 할 것 이다.
4.저장 실현:put(key,vlue)
일단 소스 부터 볼 게 요.

public V put(K key, V value) {
    // key null，  putForNullKey  ，  null table      ，  HashMap   null   
    if (key == null)
      return putForNullKey(value);
    //  key hash 
    int hash = hash(key.hashCode());         ------(1)
    //  key hash    table       
    int i = indexFor(hash, table.length);       ------(2)
    // i      e,   key      
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
      Object k;
      //         hash    (key  )
      //     ，     value，   value
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;  //   =   
        e.value = value;
        e.recordAccess(this);
        return oldValue;   //    
      }
    }
    //      1
    modCount++;
    // key、value   i   
    addEntry(hash, key, value, i);
    return null;
  }

원본 코드 를 통 해 HashMap 이 데 이 터 를 저장 하 는 과정 을 뚜렷하게 볼 수 있 습 니 다.먼저 key 가 null 인지 아 닌 지 를 판단 하고 null 이면 putForNullKey 방법 을 직접 호출 합 니 다.비어 있 지 않 으 면 key 의 hash 값 을 계산 한 다음 hash 값 에 따라 table 배열 에 있 는 색인 위 치 를 검색 합 니 다.table 배열 이 이 위치 에 요소 가 있 으 면 같은 key 가 존재 하 는 지 비교 한 다음 존재 하면 원래 key 의 value 를 덮어 씁 니 다.그렇지 않 으 면 이 요 소 를 체인 헤드 에 저장 합 니 다(가장 먼저 저 장 된 요 소 를 체인 끝 에 놓 습 니 다).table 이 이 곳 에 요소 가 없 으 면 직접 저장 합 니 다.이 과정 은 비교적 간단 해 보이 지만 사실은 내막 이 깊다.다음 과 같은 몇 가지 가 있 습 니 다.
1.교체 처 를 먼저 본다.이 교체 원인 은 같은 key 값 이 존재 하 는 것 을 방지 하기 위해 서 입 니 다.두 개의 hash 값(key)이 동시에 발견 되면 HashMap 의 처리 방식 은 새로운 value 로 오래된 value 를 교체 하 는 것 입 니 다.여기 서 key 를 처리 하지 않 았 습 니 다.이것 은 HashMap 에 같은 key 가 두 개 없다 는 것 을 설명 합 니 다.
 2.보고 있다(1),(2).여 기 는 HashMap 의 에센스 가 있 는 곳 입 니 다.우선 hash 방법 입 니 다.이 방법 은 순수한 수학 계산 으로 h 의 hash 값 을 계산 하 는 것 입 니 다.

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
  }

 우 리 는 HashMap 의 table 에 있어 데이터 분 포 는 균일 해 야 한 다 는 것 을 알 고 있다.hash 값 을 계산 한 후에 어떻게 해야만 table 요소 의 분 포 를 모두 보장 할 수 있 습 니까?우 리 는 모델 링 을 생각 할 것 입 니 다.그러나 모델 링 의 소모 가 비교적 크기 때문에 HashMap 은 이렇게 처리 합 니 다.index For 방법 을 호출 합 니 다.

static int indexFor(int h, int length) {
    return h & (length-1);
  }

HashMap 의 바 텀 배열 길 이 는 항상 2 의 n 제곱 이 고 구조 함수 에 존재 합 니 다:capacity<<=1;이렇게 하면 항상 HashMap 의 바 텀 배열 길이 가 2 인 n 제곱 을 확보 할 수 있다.length 가 2 인 n 제곱 일 때 h&(length-1)는 length 에 대해 모델 을 추출 하 는 것 과 같 고 속도 가 직접 모델 을 추출 하 는 것 보다 훨씬 빠르다.이것 은 HashMap 이 속도 에 있어 서 의 최적화 이다.왜 2 의 n 차방 인지 설명 하 겠 습 니 다.
 우 리 는 index For 방법 으로 돌아 갑 니 다.이 방법 은 h&(length-1)만 있 습 니 다.이 말 은 위의 모델 링 연산 을 제외 하고 매우 중요 한 책임 이 있 습 니 다.table 데 이 터 를 골 고루 분포 하고 공간 을 충분히 이용 합 니 다.
여기 서 우 리 는 length 가 16(2^n)과 15,h 가 5,6,7 이 라 고 가정 합 니 다
n=15 시 에 6 과 7 의 결과 가 똑 같 으 면 그들 이 table 에 저 장 된 위치 가 같다 는 것 을 나타 낸다.즉,충돌 이 발생 하면 6,7 은 한 위치 에서 링크 를 형성 하여 조회 속도 가 떨어진다.물론 여기 서 세 개의 숫자 만 분석 하 는 것 은 그리 많 지 않다.그러면 우 리 는 0-15 를 보 자
  위의 도표 에서 우 리 는 모두 8 개의 충돌 이 발생 한 것 을 보 았 고 낭비 하 는 공간 이 매우 크다 는 것 을 발견 했다.1,3,5,7,9,11,13,15 곳 이 기록 되 지 않 은 것,즉 데 이 터 를 저장 하지 않 은 것 이다.이 는 그들 이 14 와&연산 을 할 때 얻 은 결과 의 마지막 위 치 는 영원히 0,즉 0001,0011,0101,0111,1001,1011,1101,1111 위치 에 데 이 터 를 저장 할 수 없고 공간 이 줄 어 들 며 충돌 확률 을 더욱 높 여 조회 속도 가 느 리 기 때문이다.한편,length=16 시 length C 1=15 즉 1111 이면 낮은 비트&연산 을 할 때 값 은 항상 원래 hash 값 과 같 고 높 은 비트 연산 을 할 때 그 값 은 낮은 비트 값 과 같다.그래서 length=2^n 일 때 서로 다른 hash 값 이 충돌 할 확률 이 비교적 낮 습 니 다.그러면 데이터 가 table 배열 에 고 르 게 분포 되 고 조회 속도 도 빠 릅 니 다.
여기에서 우 리 는 put 의 절 차 를 다시 복습 합 니 다.HashMap 에 key-value 를 추가 하고 싶 을 때 시스템 은 먼저 key 의 hash 값 을 계산 한 다음 hash 값 에 따라 table 에 저 장 된 위 치 를 확인 합 니 다.이 위치 에 요소 가 없 으 면 바로 삽입 합 니 다.그렇지 않 으 면 이 요소 링크 를 교체 하고 이에 따라 key 의 hash 값 을 비교 합 니 다.두 hash 값 이 같 고 key 값 이 같 으 면(e.hash==hash&&&(k=e.key)=key||key.equals(k))새로운 Entry value 로 원래 노드 의 value 를 덮어 씁 니 다.두 hash 값 이 같 지만 key 값 이 다 르 면 이 노드 를 이 링크 의 체인 헤드 에 삽입 합 니 다.구체 적 인 실현 과정 은 addEntry 방법 을 보면 다음 과 같다.
 

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

이 방법 에는 두 가지 주의 가 필요 하 다.
 하 나 는 체인 의 생 성 이다.이것 은 매우 우아 한 디자인 이다.시스템 은 항상 새로운 Entry 대상 을 bucketIndex 에 추가 합 니 다.bucketIndex 에 대상 이 있 으 면 새로 추 가 된 Entry 대상 은 기 존의 Entry 대상 을 가리 키 며 Entry 체인 을 형성 합 니 다.그러나 bucketIndex 에 Entry 대상 이 없 으 면 e==null 입 니 다.그러면 새로 추 가 된 Entry 대상 이 null 을 가리 키 면 Entry 체인 이 생기 지 않 습 니 다.
 2.확장 문제.
 HashMap 에서 요소 의 수량 이 많아 지면 서 충돌 이 발생 할 확률 이 점점 커지 고 발생 하 는 링크 의 길이 가 점점 길 어 집 니 다.그러면 HashMap 의 속도 에 영향 을 줄 것 입 니 다.HashMap 의 효율 을 확보 하기 위해 시스템 은 반드시 특정한 임계 점 에서 확대 처 리 를 해 야 합 니 다.이 임계 점 은 HashMap 에서 요소 의 수량 이 table 배열 길이*로드 인자 와 같 습 니 다.그러나 확장 은 새로운 table 배열 의 위 치 를 다시 계산 하고 복사 처리 해 야 하기 때문에 시간 이 많이 걸 리 는 과정 이다.따라서 만약 에 우리 가 HashMap 에서 원소 의 개 수 를 예지 했다 면 미리 설 정 된 원소 의 개 수 는 HashMap 의 성능 을 효과적으로 향상 시 킬 수 있다.
5.읽 기 구현:get(key)
      HashMap 의 저장 소 에 비해 취 하 는 것 이 간단 합 니 다.key 의 hash 값 을 통 해 table 배열 의 색인 에 있 는 Entry 를 찾 은 다음 키 에 대응 하 는 value 를 되 돌려 줍 니 다.
     

 public V get(Object key) {
    //   null，  getForNullKey        value
    if (key == null)
      return getForNullKey();
    //     key   hashCode       hash   
    int hash = hash(key.hashCode());
    //    table           
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
      Object k;
      //    key    key  ，       value
      if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
        return e.value;
    }
    return null;
  }

여기 서 key 에 따라 value 를 신속하게 얻 을 수 있 습 니 다.HashMap 의 데이터 구조 가 밀접 한 것 을 제외 하고 Entry 와 큰 관계 가 있 습 니 다.앞에서 언급 한 바 와 같이 HashMap 은 저장 과정 에서 key,value 를 분리 하여 저장 하지 않 고 전체적인 key-value 로 처리 합 니 다.이 전 체 는 Entry 대상 입 니 다.동시에 value 도 key 의 부속 에 불과 하 다.저장 하 는 과정 에서 시스템 은 key 의 hashcode 에 따라 Entry 가 table 배열 에 저 장 된 위 치 를 결정 하고 취 하 는 과정 에서 key 의 hashcode 에 따라 해당 하 는 Entry 대상 을 추출 합 니 다.
원본 링크:http://www.cnblogs.com/chenssy/p/3521565.html
 이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.