HashMap 왜 이렇게 빨 라 요?HashMap 의 해시 체 제 를 깊이 이해 하 다.

위의 블 로 그 를 통 해 Map 의 내부 유지 키 - 값 이 맞 는 기본 방식 을 알 게 된 후에 - 모 르 는 것 은 이 (자바 집합 의 기본 요약) 을 보면 우 리 는 HashMap 내부 에서 키 - 값 이 맞 는 Map. Entry 실 체 를 어떻게 조직 하고 배열 하 는 지 생각 할 것 이다.어떻게 조직 해야만 더욱 높 은 효율 에 도달 할 수 있 습 니까?
HashMap 의 해시 체 제 를 이해 하기 전에 HashMap 내부 의 데이터 구조의 배열 방식 을 가정 해 보 자.
배열 을 통 해 내부 키 를 유지 합 니 다. - 값 이 맞습니다. 배열 은 우리 가 가장 쉽게 생각 할 수 있 는 데이터 구조 일 수도 있다. 우 리 는 한 조 의 데 이 터 를 저장 하 는 가장 빠 른 데이터 구 조 는 바로 배열 이라는 것 을 알 고 있다. 이것 도 배열 이 남 아 있 는 장점 이다. 마찬가지 로 배열 의 결함 도 매우 뚜렷 하 다. 예 를 들 어 대량의 연속 적 인 메모리 공간 이 필요 하고 요소 에 대한 삽입 작업 대가 가 높 으 며 용량 을 임의로 확대 할 수 없다.
따라서 HashMap 의 내부 에서 배열 을 통 해 키 - 값 을 유지 하면 우리 가 요 소 를 증가 할 때 비용 이 많이 들 지 않 는 것 같 지만 우리 가 하나의 key 로 value 를 얻 을 때 우리 가 어떻게 실현 해 야 하 는 지 생각해 보 자. 가장 흔히 볼 수 있 는 방식 은 바로 key 에 대해 선형 equals 조 회 를 하 는 것 이다. 처음부터 끝까지 이런 조회 속도 가 이렇게 낮 고 효율 이 상상 할 수 있다.또 하나의 결함 은 바로 배열 이 타고 난 것 으로 너무 큰 연속 적 인 메모리 공간 이 필요 하기 때문에 배열 을 통 해 HashMap 내부 의 데이터 결함 이 너무 커서 가치 가 없다 는 것 이다.
링크 를 통 해 유지 위 에서 배열 의 그렇게 많은 결함 을 말 한 후에 많은 학생 들 이 링크 를 사용한다 고 말 할 수 있 습 니 다. 맞습니다. 링크 는 배열 의 가장 치 명 적 인 결함 (대량의 연속 적 인 메모리 공간 이 필요 합 니 다) 을 해결 한 것 같 습 니 다. 그러나 링크 는 우리 가 하나의 key 로 value 를 조회 할 때 낮은 효율 을 해결 할 수 없습니다. 그 이 유 는 처음부터 끝까지 선형 으로 옮 겨 다 니 기 때 문 입 니 다.
위 에서 우 리 는 배열 이나 링크 로 내부 의 키 를 유지 하 겠 다 고 말 했다. - 수 치 는 효율 이 낮은 것 같 습 니 다. 배열 과 링크 두 가지 장점 을 결합 시 켜 효율 적 인 조회 속 도 를 가 진 데이터 구 조 는 없 습 니까?
이것 이 바로 HashMap 내부 에서 데 이 터 를 유지 하 는 방식 - 배열 링크 + 해시 체제 입 니 다.
속 도 를 위 한 해시:
산열 의 가 치 는 바로 속도 에 있 습 니 다. 산열 은 조 회 를 신속하게 진행 할 수 있 습 니 다. 그러면 무엇이 배열 링크 이 고 무엇이 산열 체제 입 니까?
바로 배열 링크 란 하나의 배열 을 정의 한 다음 에 배열 의 모든 구성원 은 하나의 링크 입 니 다. 배열 은 이 링크 의 인용 만 기록 하면 됩 니 다. 그러면 배열 내부 에 키 - 값 을 직접 저장 하지 않 고 대량의 연속 적 인 메모리 공간 이 필요 합 니 다. 해시 체 제 는 이른바 hashCode 방법 으로 돌아 오 는 int 수 입 니 다. 그 는 대상 의 정보 (기본 값 은 주소) 를 통 해 특정한 해시 수학 함 수 를 통 해 생 성 된 int 숫자 입 니 다. 배열 링크 와 해시 체 제 를 알 게 된 후에 우 리 는 HashMap 내부 의 키 - 값 이 어떻게 효율 적 으로 유지 되 는 지 다시 생각해 보 자.
우선, 하나의 배열 을 정의 합 니 다. 이 배열 은 링크 를 저장 하 는 참조 배열 로 배열 이 저장 대상 으로 인해 대량의 연속 적 인 메모리 공간 이 필요 한 결함 을 해결 합 니 다. 그 다음 에 우 리 는 put 요 소 를 사용 할 때 key 의 HashCode 방법 으로 해시 코드 를 생 성 한 다음 에 이 해시 코드 로 나머지 배열 의 용량 을 사용 하여 한 배열 의 아래 표 시 를 얻 은 다음 에 이 키 - 값 을 이 아래 표 시 된 링크 에 저장 합 니 다. 이상 적 인 상황 에서 해시 충돌 이 없다 고 가정 합 니 다. (서로 다른 대상 이 똑 같은 해시 코드 를 만 들 었 습 니 다) 우리 가 key 로 value 를 조회 할 때 이 해시 함수 로 배열 의 아래 표 시 를 받 아 대응 하 는 value 를 직접 얻 었 습 니 다. 이 효율 은 정말 몇 배 올 랐 습 니까? 그러나 충돌 이 발생 하지 않 는 해시 함 수 는 거의 존재 하지 않 기 때문에 서로 다른 key 가 똑 같은 해시 코드 를 만 들 수 있 습 니 다. 우리 가 조회 할 때 equals 선형 으로 이 작은 부분 을 옮 겨 다 녀 야 합 니 다. 충돌 로 인해 하나의 링크 에 저 장 된 키 - 값 이 맞습니다. 그러나 이것 은 모든 요소 와 선형 으로 옮 겨 다 니 며 효율 이 아직도 여러 배 높 아 졌 습 니 다. 위의 해석 을 통 해 배열 링크 와 해시 체 제 를 사용한다. 이 루어 진 HashMap 이 왜 이렇게 효율 이 높 은 지 이 해 했 습 니 다. 다음은 간단 한 HashMap 을 실현 하 겠 습 니 다.

   class MyHashMap extends AbstractMap {

        private static final int SIZE = 16;
        LinkedList>[] buckets = new LinkedList[SIZE];

        @Override
        public v put(k key, v value) {
            int index = key.hashCode() % SIZE;
            if (buckets[index] == null) {
                buckets[index] = new LinkedList<>();
            }

            boolean found = false;
            Map.Entry pair = new HashMap.SimpleEntry<>(key, value);
            v oldValue = null;
            // Begin to found whether already have this key and value.
            for (Entry kvEntry : buckets[index]) {
                // If already have this key, replace value.
                if (kvEntry.getKey().equals(key)) {
                    oldValue = kvEntry.getValue();
                    found = true;
                    buckets[index].set(buckets[index].indexOf(kvEntry), pair);
                    break;
                }
            }
            // If not found, add the new key-value to the linked end.
            if (!found) {
                buckets[index].add(pair);
            }
            return oldValue;
        }

        @Override
        public v get(Object key) {
            // Use hash code to get index.
            int index = key.hashCode() % SIZE;
            if (buckets[index] == null) {
                return null;
            }
            for (Entry kvEntry : buckets[index]) {
                // If have this key, return value.
                if (kvEntry.getKey().equals(key)) {
                    return kvEntry.getValue();
                }
            }
            return null;
        }

        @Override
        public Set> entrySet() {
            HashSet> entryHashSet = new HashSet<>();
            for (LinkedList> bucket : buckets) {
                if (bucket != null) {
                    entryHashSet.addAll(bucket);
                }
            }
            return entryHashSet;
        }
    }

위 에서 간단 한 HashMap 의 원 리 를 실현 한 후에 우 리 는 왜 우리 가 사용자 정의 형식 을 키 로 사용 할 때 equals 와 hashcode 방법 을 동시에 덮어 써 야 하 는 지 알 게 되 었 다.

좋 은 해시 함 수 는 균일 한 해시 코드 를 만 들 수 있어 야 합 니 다. 또한 해시 코드 는 유일한 것 을 요구 하지 않 습 니 다. 더욱 관심 을 가 지 는 것 은 생 성 속도 입 니 다. 우 리 는 대상 의 일부 의미 있 는 정 보 를 사용 하여 해시 코드 를 만 드 는 것 이 좋 습 니 다.

해시 코드 를 만 드 는 데 사용 되 는 정 보 는 쉽게 바 꿀 수 없 는 값 일 것 입 니 다. 같은 key 에 hashCode 를 호출 했 는데 두 개의 다른 해시 코드 를 만 들 었 다 면 이전 value 를 얻 을 수 없습니다.

계속..................................................................