HashMap 이해 (및 hash 함수 의 진정한 교묘 함)

/**
    *@author annegu
    *@date 2009-12-02
    */
Hashmap 은 매우 자주 사용 되 고 광범 위 하 게 응용 되 는 데이터 유형 으로 최근 에 관련 내용 을 연구 한 결과 마침 복습 을 해 보 았 다.인터넷 에 hashmap 에 관 한 글 이 많 지만 자신 이 배 운 총 결 인지 여러분 과 함께 공유 하고 토론 합 니 다.
1. hashmap 의 데이터 구조
  hashmap 이 무엇 인지 알 기 위해 서 는 먼저 데이터 구 조 를 파악 해 야 합 니 다. 자바 프로 그래 밍 언어 에서 가장 기본 적 인 구 조 는 두 가지 입 니 다. 하 나 는 배열 이 고 다른 하 나 는 아 날로 그 포인터 (참조) 입 니 다. 모든 데이터 구 조 는 이 두 가지 기본 구조 로 구 성 될 수 있 습 니 다. hashmap 도 예외 가 아 닙 니 다.Hashmap 는 실제 적 으로 하나의 배열 과 링크 의 결합 체 (데이터 구조 에서 일반적으로 '링크 해시' 라 고 부 릅 니 다) 입 니 다. 다음 그림 을 보 세 요.
그림 에서 볼 수 있 듯 이 hashmap 는 하나의 배열 구조 입 니 다. hashmap 을 새로 만 들 때 하나의 배열 을 초기 화 합 니 다. 자바 코드 를 보 겠 습 니 다.

/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     *  FIXME          ，         
     */
    transient Entry[] table;

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

        위의 Entry 는 배열 의 요소 입 니 다. 다음 요 소 를 가리 키 는 인용 을 가지 고 있 습 니 다. 이것 은 링크 를 구성 합 니 다.
         hashmap 에 put 요 소 를 넣 을 때 키 의 hash 에 따라 이 요소 가 배열 에 있 는 위치 (즉, 아래 표) 에 도착 할 수 있 습 니 다.그 다음 에 이 요 소 를 대응 하 는 위치 에 놓 을 수 있 습 니 다. 만약 에 이 요소 가 있 는 자리 에 다른 요소 가 저장 되 어 있다 면 같은 자리 에 있 는 요 소 는 링크 형식 으로 저장 되 고 새로 추 가 된 것 은 체인 헤드 에 놓 으 며 가장 먼저 추 가 된 것 은 체인 끝 에 놓 습 니 다. hashmap 에서 get 요 소 를 계산 할 때 먼저 key 의 hashcode 를 계산 하여 배열 에 대응 하 는 위 치 를 찾 습 니 다.요 소 는 key 의 equals 방법 을 통 해 해당 위치 에 있 는 링크 에서 필요 한 요 소 를 찾 을 수 있 습 니 다. 여기 서 우 리 는 모든 위치 에 있 는 링크 가 하나의 요소 만 있다 면 hashmap 의 get 효율 이 가장 높 을 것 이 라 고 상상 할 수 있 습 니 다. 그러나 이상 은 항상 아름 답 습 니 다. 지금 은 우리 가 극복 해 야 할 어려움 이 있 습 니 다. 하하 ~
2. hash 알고리즘
hashmap 에서 어떤 요 소 를 찾 으 려 면 key 의 hash 값 에 따라 대응 하 는 배열 의 위 치 를 구 해 야 합 니 다. 이 위 치 를 어떻게 계산 하 는 지 는 hash 알고리즘 입 니 다. 앞에서 말 했 듯 이 hashmap 의 데이터 구 조 는 배열 과 링크 의 결합 이 므 로 우 리 는 당연히 이 hashmap 안의 요소 위 치 를 최대한 고 르 게 분포 하여 모든 위치 에 있 는 요소 수 를 되도록 하 기 를 바 랍 니 다.양 이 하나 밖 에 없 으 면 우리 가 hash 알고리즘 으로 이 위 치 를 구 할 때 해당 하 는 위치 에 있 는 요소 가 바로 우리 가 원 하 는 것 임 을 알 수 있 고 더 이상 링크 를 옮 겨 다 니 지 않 아 도 된다.
그래서 우리 가 먼저 생각 하 는 것 은 hashcode 를 배열 의 길이 에 대해 모델 링 을 하 는 것 입 니 다. 그러면 요소 의 분 포 는 상대 적 으로 고 르 게 됩 니 다. 그러나 '모' 연산 의 소 모 는 비교적 큽 니 다. 더 빠 르 고 소모 가 적은 방식 을 찾 을 수 있 습 니까? 자바 에서 이렇게 했 습 니 다.

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

먼저 key 는 hashcode 값 을 계산 한 다음 배열 의 길이 - 1 과 "연산 (&) 을 한 번 합 니 다. 보기 에는 간단 하지만 사실은 현묘 합 니 다. 예 를 들 어 배열 의 길이 가 2 의 4 제곱 이면 hashcode 는 (2 의 4 제곱 - 1) 과" 와 "를 합 니 다.연산. 많은 사람들 이 이 의문 을 가지 고 있 습 니 다. 왜 hashmap 의 배열 초기 화 크기 는 2 의 차방 큰 시간 이 고 hashmap 의 효율 이 가장 높 습 니까? 저 는 2 의 4 차방 예 를 들 어 왜 배열 크기 가 2 의 멱 일 때 hashmap 가 방문 하 는 성능 이 가장 높 은 지 설명 하 겠 습 니 다.
         아래 그림 을 보면 왼쪽 두 조 는 배열 의 길이 가 16 (2 의 4 제곱) 이 고 오른쪽 두 조 는 배열 의 길이 가 15 이다. 두 조 의 hashcode 는 모두 8 과 9 이지 만 분명 하 다.같은 결과 가 나 왔 습 니 다. 즉, 배열 의 같은 위치 에 위치 하 게 됩 니 다. 이 로 인해 충돌 이 생 겼 습 니 다. 8 과 9 는 같은 링크 에 올 라 갑 니 다. 그러면 조회 할 때 이 링크 를 옮 겨 다 니 며 8 이나 9 를 얻 으 면 조회 의 효율 이 떨 어 집 니 다. 또한 배열 의 길이 가 15 일 때 hashcode 의 것 도 발견 할 수 있 습 니 다.값 은 14 (1110) 와 "와" 를 진행 합 니 다.그러면 마지막 자 리 는 영원히 0 이 고 0001, 0011, 0101, 1001, 1011, 0111, 1101 이라는 몇 개의 위 치 는 요 소 를 저장 할 수 없습니다. 공간 낭비 가 상당히 크 고 더 나 쁜 것 은 이런 상황 에서 배열 이 사용 할 수 있 는 위 치 는 배열 의 길이 보다 훨씬 작 습 니 다. 이것 은 충돌 확률 을 더욱 증가 시 켜 조회 의 효율 을 늦 추 었 다 는 것 을 의미 합 니 다!
          따라서 배열 의 길이 가 2 인 n 차 멱 일 때 서로 다른 key 가 index 와 같은 확률 로 계산 하면 데이터 가 배열 에 비교적 고 르 게 분포 된다. 즉, 부 딪 힐 확률 이 적 고 상대 적 으로 조회 할 때 특정한 위치 에 있 는 링크 를 옮 겨 다 니 지 않 아 도 된다 는 것 이다. 그러면 조회 효율 이 비교적 높다. 이것 이 바로 진정한 원인 이다. 많은 사람들 이 소스 코드 를 보 더 라 도.이 유 를 모르다.
          ÷ 여기까지 하면 hashmap 의 기본 배열 크기 가 얼마 인지 다시 한 번 살 펴 보 겠 습 니 다. 소스 코드 를 보면 16 인지 알 수 있 습 니 다. 왜 15 가 아니 라 16 인지 20 도 아 닙 니 다. 위의 annegu 의 설명 을 보면 알 수 있 습 니 다. 16 은 2 의 전체 수 멱 이기 때 문 입 니 다. 작은 데 이 터 량 의 경우 16 대 15 와 20 이 key 간 의 충돌 을 더욱 줄 일 수 있 습 니 다.조회 의 효율 을 가속 화하 다.
따라서 대 용량 데 이 터 를 저장 할 때 hashmap 의 size 를 2 의 정수 차 로 미리 지정 하 는 것 이 좋 습 니 다. 지정 하지 않 더 라 도 지정 치 크기 에 가장 가 까 운 2 차 로 초기 화 됩 니 다. 코드 는 다음 과 같 습 니 다 (HashMap 의 구조 방법 중).
hashmap 의 resize
       hashmap 의 요소 가 점점 많아 질 때 부 딪 힐 확률 도 점점 높 아 집 니 다 (배열 의 길이 가 고정 되 어 있 기 때 문 입 니 다)따라서 조회 의 효율 을 높이 기 위해 hashmap 의 배열 을 확대 해 야 합 니 다. 배열 확장 이라는 조작 도 Array List 에 나타 날 수 있 기 때문에 이것 은 통용 되 는 조작 입 니 다. 많은 사람들 이 그의 성능 에 대해 의심 을 표 했 지만 우리 의 '균등 한 분담' 을 생각해 보 세 요.원 리 는 석연 하 다. hashmap 배열 이 확 대 된 후에 가장 성능 을 소모 하 는 점 이 나 타 났 다. 원래 배열 의 데 이 터 는 반드시 새로운 배열 에 있 는 위 치 를 다시 계산 하고 넣 어야 한다. 이것 이 바로 resize 이다.
         그러면 hashmap 는 언제 확장 합 니까? hashmap 의 요소 개수 가 배열 크기 * loadFactor 를 초과 할 때 배열 확장 을 합 니 다. loadFactor 의 기본 값 은 0.75 입 니 다. 즉, 기본 적 인 상황 에서 배열 크기 는 16 입 니 다. 그러면 hashmap 에서 요소 개수 가 16 * 0.75 = 12 를 초과 할 때 배열 의 크기 를 2 * 16 = 32, 즉 배로 확대 한 다음 에 다시 확대 합 니 다.모든 요소 가 배열 에 있 는 위 치 를 계산 하 는 것 은 성능 을 매우 소모 하 는 작업 입 니 다. 그래서 만약 에 우리 가 hashmap 에서 요소 의 개 수 를 미리 알 았 다 면 미리 설 치 된 요소 의 개 수 는 hashmap 의 성능 을 효과적으로 향상 시 킬 수 있 습 니 다. 예 를 들 어 우 리 는 1000 개의 요 소 를 hashmap 에 넣 어야 합 니 다. 그러면 hashmap 의 size 를 1024 로 설정 하 는 것 이 좋 은 선택 이지 만 위 에 annegu 가 있 습 니 다.1000 이 라 고 해도 hashmap 은 자동 으로 1024 로 설정 된다 고 했 습 니 다.
4. key 의 hashcode 와 equals 방법 변경
첫 번 째 부분 hashmap 의 데이터 구조 에서 annegu 는 get 방법 을 쓰 는 과정 입 니 다. 먼저 key 의 hashcode 를 계산 하고 배열 에 대응 하 는 위치의 특정한 요 소 를 찾 은 다음 에 key 의 equals 방법 을 통 해 해당 하 는 위치의 링크 에서 필요 한 요 소 를 찾 습 니 다. 따라서 hashcode 와 equals 방법 은 대응 하 는 요 소 를 찾 는 데 두 가지 관건 적 인 방법 입 니 다.
Hashmap 의 key 는 모든 유형의 대상 이 될 수 있 습 니 다. 예 를 들 어 user 와 같은 속성 을 가 진 user 의 hashcode 가 같 도록 hashcode 방법 을 바 꿔 야 합 니 다. 예 를 들 어 hashcode 값 의 계산 을 user 대상 의 id 와 연결 시 키 면 user 가 같은 id 를 가지 고 있 으 면 그들의 hashcode 도 일치 할 수 있 습 니 다. 그러면 hashm 에서 찾 을 수 있 습 니 다.ap 배열 의 위치 입 니 다. 이 위치 에 여러 요소 가 있다 면 key 의 equals 방법 으로 해당 위치 에 있 는 링크 에서 필요 한 요 소 를 찾 아야 합 니 다. 그래서 hashcode 방법 만 바 꾸 는 것 은 부족 합 니 다. equals 방법 도 바 꿔 써 야 합 니 다. 물론 정상 적 인 사고 논리 에 따 르 면 equals 방법 은 보통 실제 업무 내용 에 따라 정 의 됩 니 다. 예 를 들 어 user 대상 에 따라 정 의 됩 니 다.두 user 가 같은 지 아 닌 지 를 판단 합 니 다.
equals 방법 을 고 칠 때 다음 과 같은 세 가 지 를 만족 시 켜 야 합 니 다.
(1) 자 반성: 즉 a. equals (a) 는 반드시 true 여야 한다.
(2) 대칭 성: 즉 a. equals (b) = true 라면 b. equals (a) 도 true 여야 한다.
(3) 전달 성: 즉 a. equals (b) = true, 그리고 b. equals (c) = true 라면 a. equals (c) 도 true 여야 한다.
key 대상 의 equals 와 hashcode 방법 을 바 꾸 면 우 리 는 임의의 업무 대상 을 map 의 key 로 할 수 있 습 니 다.
요약:        본 고 는 주로 HashMap 의 구조 와 hashmap 에서 hash 함수 의 실현, 그리고 이 실현 의 특성 을 묘사 하 였 으 며, 동시에 hashmap 에서 resize 가 성능 소 모 를 가 져 오 는 근본 원인 과 일반 도 메 인 모델 대상 을 key 의 기본 요구 로 하 였 다. 특히 hash 함수 의 실제 현 재 는 전체 HashMap 의 정수 라 고 할 수 있 으 며, 이 hash 함 수 를 진정 으로 이해 해 야 한다.HashMap 에 대해 어느 정도 이 해 를 했다 고 합 니 다.