HashMap 실현 원리 분석

  • HashMap 의 데이터 구조 데이터 구조 에는 배열 과 링크 가 있어 데이터 에 대한 저장 을 실현 하지만 이 두 가 지 는 대체적으로 두 극단 이다.배열 배열 저장 구간 은 연속 적 이 고 메모리 사용량 이 심각 하기 때문에 공간 이 매우 복잡 하 다.그러나 배열 의 2 분 검색 시간 은 복잡 도가 적 고 O (1) 입 니 다.배열 의 특징 은 주소 찾기 가 쉽 고 삽입 과 삭제 가 어렵 다 는 것 이다.

  • 링크 링크 메모리 구간 이 분 산 돼 메모리 사용량 이 비교적 넓 기 때문에 공간 복잡 도 는 매우 작 지만 시간 복잡 도가 매우 커서 O (N) 에 달한다.링크 의 특징 은 주소 찾기 가 어렵 고 삽입 과 삭제 가 쉽다 는 것 이다.
    해시 표 그러면 우 리 는 이들 의 특성 을 종합 하여 주소 찾기 가 쉽 고 삽입 삭제 도 쉬 운 데이터 구 조 를 만 들 수 있 습 니까?답 은 긍정 적 이다. 이것 이 바로 우리 가 제기 하고 자 하 는 해시 표 이다.해시 표 (Hash table) 는 데이터 검색 의 편리 함 을 만족 시 킬 뿐만 아니 라 너무 많은 내용 공간 을 차지 하지 않 고 사용 하기에 도 매우 편리 하 다.
    해시 표 는 여러 가지 다른 실현 방법 이 있 습 니 다. 제 가 다음 에 설명 하 는 것 은 가장 자주 사용 하 는 방법 인 지퍼 법 입 니 다. 우 리 는 '링크 의 배열' 이 라 고 이해 할 수 있 습 니 다. 그림 과 같 습 니 다.
    위의 그림 에서 우 리 는 해시 표 가 배열 + 링크 로 구 성 된 것 을 발견 할 수 있 습 니 다. 하나의 길이 가 16 인 배열 에서 모든 요 소 는 하나의 링크 의 끝 점 을 저장 합 니 다. 그러면 이 요 소 는 어떤 규칙 에 따라 배열 에 저장 되 는 것 입 니까? 일반적인 상황 은 hash (key) 를 통 해 저장 되 는 것 입 니까?% len 획득, 즉 요소 의 key 의 해시 값 은 배열 의 길 이 를 모델 링 합 니 다. 예 를 들 어 상기 해시 표 에서 12% 16 = 12, 28% 16 = 12, 108% 16 = 12, 140% 16 = 12. 그래서 12, 28, 108 과 140 은 모두 배열 아래 에 12 로 표 시 된 위치 에 저 장 됩 니 다.
    HashMap 은 사실 선형 배열 로 이 루어 졌 기 때문에 데 이 터 를 저장 하 는 용기 가 선형 배열 이 라 고 이해 할 수 있 습 니 다. 이것 은 우리 로 하여 금 매우 이해 하지 못 하 게 할 수 있 습 니 다. 선형 배열 이 어떻게 버튼 값 대 를 실현 하여 데 이 터 를 액세스 할 수 있 습 니까? 여기 HashMap 은 약간의 처 리 를 하고 있 습 니 다.
    먼저 HashMap 에서 정적 내부 클래스 Entry 를 실현 합 니 다. 그 중요 한 속성 은 key, value, next 입 니 다. 속성 key, value 를 통 해 알 수 있 듯 이 Entry 는 HashMap 키 값 이 실현 하 는 기본 bean 입 니 다. 우 리 는 위 에서 HashMap 의 기 초 는 선형 배열 이 고 이 배열 은 Entry [] 입 니 다. Map 안의 내용 은 모두 Entry [] 안에 저 장 됩 니 다.
    “` /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;
  • HashMap 의 액세스 실현 은 선형 배열 인 데 왜 무 작위 로 액세스 할 수 있 습 니까? 여기 HashMap 은 작은 알고리즘 을 사 용 했 습 니 다. 대체적으로 이렇게 실현 되 었 습 니 다.
  • //    :
    int hash = key.hashCode(); //   hashCode       ,      key hash      int 
    int index = hash % Entry[].length;
    Entry[index] = value;
    
    //    :
    int hash = key.hashCode();
    int index = hash % Entry[].length;
    return Entry[index];

    1)put
    질문: 두 키 가 hash% Entry [] 를 통과 하면. length 에서 얻 은 index 와 같 습 니 다. 덮어 쓸 위험 이 있 습 니까? 여기 HashMap 에 체인 데이터 구 조 를 사용 한 개념 이 있 습 니 다. 위 에서 언급 한 바 와 같이 Entry 클래스 에 next 속성 이 있 는데, 작용 은 다음 Entry 를 가리 키 는 것 입 니 다. 예 를 들 어 첫 번 째 키 값 은 A 에 들 어 와 서 키 의 hash 를 계산 하여 얻 은 index = 0 을 기록 합 니 다: Entry [0]= A. 잠시 후에 또 하나의 키 값 대 B 가 들 어 왔 습 니 다. 계산 을 통 해 index 도 0 과 같 습 니 다. 지금 은 어떻게 합 니까? HashMap 은 이렇게 합 니 다. B. next = A, Entry [0] = B, 또 C 가 들 어 오 면 index 도 0 과 같 습 니 다. 그러면 C. next = B, Entry [0]= C; 이렇게 해서 우 리 는 index = 0 의 곳 에 A, B, C 세 개의 키 값 이 있 는 것 을 발 견 했 습 니 다. 그들 은 next 라 는 속성 을 통 해 연결 되 어 있 습 니 다. 따라서 의문 은 걱정 하지 마 세 요. 즉, 배열 에 저 장 된 것 은 마지막 으로 삽 입 된 요소 입 니 다. 여기까지 HashMap 의 대략적인 실현 은 우리 가 이미 알 고 있 을 것 입 니 다.
     public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value); //null             
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            //    
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                //  key       ,     value
                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;
    }
    
    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //  e,  Entry.next
        //  size  threshold,   table  。   
        if (size++ >= threshold)
                resize(2 * table.length);
    }

    물론 HashMap 에 도 최적화 방면 의 실현 이 포함 되 어 있 습 니 다. 여기 서도 말씀 드 리 겠 습 니 다. 예 를 들 어 Entry [] 의 길이 가 일정 해 지면 map 안의 데이터 가 길 어 지면 서 같은 index 의 체인 이 길 어 지고 성능 에 영향 을 주지 않 습 니까? HashMap 에 인 자 를 설정 합 니 다. map 의 size 가 커지 면서 Entry [] 는 일정한 규칙 으로 길 이 를 늘 립 니 다.
    2get
     public V get(Object key) {
            if (key == null)
                return getForNullKey();
            int hash = hash(key.hashCode());
            //        ,          
            for (Entry<K,V> 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;
    }
    

    3) null key 의 액세스 null key 는 항상 Entry [] 배열 의 첫 번 째 요소 에 저 장 됩 니 다.
       private V putForNullKey(V value) {
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
                if (e.key == null) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }
    
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }
    

    4) 배열 index: hashcode% table. length 모드 HashMap 접근 을 확인 할 때 현재 key 가 Entry [] 배열 에 대응 해 야 할 요 소 를 계산 해 야 합 니 다. 즉, 배열 아래 표 시 를 계산 하 는 것 입 니 다. 알고리즘 은 다음 과 같 습 니 다.
       /** * Returns index for hash code h. */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
    

    비트 에 따라 취 합 하면 모드 모드 모드 나 나머지% 를 취 하 는 역할 을 합 니 다. 이것 은 배열 의 아래 표 시 는 같 고 hashCode 가 같다 는 것 을 의미 하지 않 습 니 다.
    5) 테이블 초기 크기
      public HashMap(int initialCapacity, float loadFactor) {
            .....
            // Find a power of 2 >= initialCapacity
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
            this.loadFactor = loadFactor;
            threshold = (int)(capacity * loadFactor);
            table = new Entry[capacity];
            init();
        }

    table 의 초기 크기 는 구조 함수 의 initialCapacity 가 아 닙 니 다!!
    대신 > = initialCapacity 의 2 의 n 차 멱!!!!
    - 왜 이렇게 디자인 했 어 요?
  • hash 충돌 을 해결 하 는 방법 은 주소 법 (선형 탐지 재 산열, 2 차 탐지 재 산열, 위 랜 덤 탐지 재 산열) 을 개방 하고 해시 법 체인 주소 법 으로 공공 유출 구역 자바 에서 hashmap 의 해결 방법 은 바로 사용 하 는 체인 주소 법 이다.
  • 재 산열 rehash 프로 세 스 는 해시 표 의 용량 이 기본 용량 을 초과 할 때 table 의 크기 를 조정 해 야 합 니 다. 용량 이 최대 가능 치 에 도 달 했 을 때 이 방법 은 Integer. MAX VALUE 로 용량 을 조정 합 니 다. 이 때 새 표를 만 들 고 원래 표 의 맵 을 새 표 에 표시 해 야 합 니 다.
  •  /**
         * Rehashes the contents of this map into a new array with a
         * larger capacity.  This method is called automatically when the
         * number of keys in this map reaches its threshold.
         *
         * If current capacity is MAXIMUM_CAPACITY, this method does not
         * resize the map, but sets threshold to Integer.MAX_VALUE.
         * This has the effect of preventing future calls.
         *
         * @param newCapacity the new capacity, MUST be a power of two;
         *        must be greater than current capacity unless current
         *        capacity is MAXIMUM_CAPACITY (in which case value
         *        is irrelevant).
         */
        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);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
    
      /** * Transfers all entries from current table to newTable. */
        void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) {
                Entry<K,V> e = src[j];
                if (e != null) {
                    src[j] = null;
                    do {
                        Entry<K,V> next = e.next;
                        //    index
                        int i = indexFor(e.hash, newCapacity);
                        e.next = newTable[i];
                        newTable[i] = e;
                        e = next;
                    } while (e != null);
                }
            }
        }

    좋은 웹페이지 즐겨찾기