자바 집합 시리즈 의 HashMap 소스 분석

앞에서 우 리 는 Array List 와 LinkedList 라 는 두 집합 을 분석 했다.우 리 는 Array List 가 배열 을 바탕 으로 이 루어 진 것 이 고 LinkedList 는 링크 를 바탕 으로 이 루어 진 것 이라는 것 을 알 고 있다.각각 장단 점 이 있 습 니 다.예 를 들 어 Array List 는 요 소 를 찾 을 때 LinkedList 보다 좋 고 LinkedList 는 삭제 요 소 를 추가 할 때 Array List 보다 좋 습 니 다.한편,본 고 에서 소개 한 HashMap 은 이들 의 장점 을 종합 했다.그 밑바닥 은 해시 표를 바탕 으로 이 루어 진 것 이다.만약 에 해시 충돌 을 고려 하지 않 는 다 면 HashMap 은 삭제 와 수정 작업 에서 의 시간 복잡 도 는 놀 라 운 O(1)에 이 를 수 있다.우 리 는 먼저 그것 이 기초 한 해시 표 의 구 조 를 보 았 다.

위의 그림 에서 볼 수 있 듯 이 해시 표 는 배열 과 링크 가 공동으로 구 성 된 구조 이다.물론 위의 그림 은 좋 지 않 은 사례 이다.좋 은 해시 함 수 는 가능 한 한 평균 요소 가 배열 에서 의 분 포 를 줄 이 고 해시 충돌 을 감소 시 켜 링크 의 길 이 를 줄 여야 한다.체인 테이블 의 길이 가 길 수록 찾 을 때 옮 겨 다 니 는 결점 이 많 을 수록 해시 테이블 의 성능 도 떨어진다 는 뜻 이다.다음은 HashMap 의 일부 구성원 변 수 를 살 펴 보 겠 습 니 다.

//      
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//      
static final int MAXIMUM_CAPACITY = 1 << 30;

//      ,              
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//     
static final Entry<?,?>[] EMPTY_TABLE = {};

//        
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//HashMap  ,  HashMap        
transient int size;

//      ,                
int threshold;

//    
final float loadFactor;

//    ,   fail-fast  
transient int modCount;

//           
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//       ,             
transient int hashSeed = 0;

구성원 변수 에서 보 듯 이 HashMap 의 기본 초기 용량 은 16 이 고 기본 로드 인 자 는 0.75 입 니 다.한편,threshold 는 저장 할 수 있 는 키 쌍 의 밸브 값 을 집합 하 는 것 입 니 다.기본 값 은 초기 용량*로드 인자,즉 16*0.75=12 입 니 다.키 쌍 이 밸브 값 을 초과 할 때 이때 의 해시 표 가 포화 상태 에 있 음 을 의미 합 니 다.원 소 를 계속 추가 하면 해시 충돌 을 증가 시 켜 HashMap 의 성능 을 떨 어 뜨 립 니 다.이 때 HashMap 의 성능 을 확보 하기 위해 자동 확장 메커니즘 을 촉발 합 니 다.우 리 는 해시 표 가 사실은 Entry 배열 이 고 배열 이 저장 하 는 모든 Entry 는 단 방향 링크 의 머리 결산 점 이라는 것 을 볼 수 있다.이 Entry 는 HashMap 의 정적 내부 클래스 입 니 다.Entry 의 구성원 변 수 를 보십시오.

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

하나의 Entry 인 스 턴 스 는 키 값 쌍 입 니 다.키 와 value 가 포함 되 어 있 으 며,모든 Entry 인 스 턴 스 는 다음 Entry 인 스 턴 스 를 가리 키 는 참조 가 있 습 니 다.중복 계산 을 피하 기 위해 모든 Entry 인 스 턴 스 는 해당 하 는 Hash 코드 를 저장 합 니 다.Entry 배열 은 HashMap 의 핵심 이 라 고 할 수 있 습 니 다.모든 조작 은 이 배열 을 대상 으로 이 루어 집 니 다.HashMap 소스 코드 가 비교적 길 기 때문에 모든 방법 을 다 소개 할 수 없 기 때문에 우 리 는 중점 만 잡 고 소개 합 니 다.다음 에 우 리 는 문 제 를 중심 으로 다음 과 같은 몇 가지 문제 에 대해 HashMap 의 내부 체 제 를 깊이 연구 할 것 이다.
1.HashMap 은 구조 할 때 어떤 조작 을 했 습 니까?

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

void init() {}

모든 구조 기 는 이 구조 기 에 호출 됩 니 다.이 구조 기 에서 우 리 는 매개 변 수 를 검사 하 는 것 을 제외 하고 두 가지 일 을 했 습 니 다.로드 인 자 를 들 어 오 는 로드 인자 로 설정 하고 밸브 값 을 들 어 오 는 초기 화 크기 로 설정 합 니 다.init 방법 은 비어 있 고 아무것도 하지 않 았 습 니 다.이 때 들 어 오 는 초기 화 크기 에 따라 Entry 배열 을 새로 만 들 지 않 았 습 니 다.그럼 언제 새 배열 로 갈 까요?계속 내 려 다 봐.
2.HashMap 키 를 추가 할 때 어떤 동작 을 합 니까?

//  key-value    HashMap 
public V put(K key, V value) {
  //                
  if (table == EMPTY_TABLE) {
    //      
    inflateTable(threshold);
  }
  if (key == null) {
    return putForNullKey(value);
  }
  //  key hash 
  int hash = hash(key);
  //  hash          
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    //     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;
    }
  }
  modCount++;
  //       key   Entry HashMap 
  addEntry(hash, key, value, i);
  //      null
  return null;
}

키 값 을 추가 할 때 해시 표 가 빈 표 인지 확인 하고 빈 표 라면 초기 화 합 니 다.그 다음 에 후속 작업 을 하고 해시 함수 로 들 어 오 는 key 의 Hash 코드 를 계산 합 니 다.hash 코드 에 따라 Entry 배열 의 지정 슬롯 위 치 를 찾 은 다음 이 슬롯 의 단 방향 링크 를 옮 겨 다 니 며 들 어 온 것 이 존재 하면 교체 작업 을 합 니 다.그렇지 않 으 면 새 Entry 를 해시 표 에 추가 합 니 다.
3.해시 표 는 어떻게 초기 화 됩 니까?

//      ,            ,             2  
private void inflateTable(int toSize) {
  //        2   
  int capacity = roundUpToPowerOf2(toSize);
  //    ,       capacity*loadFactor
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  //          
  table = new Entry[capacity];
  //       
  initHashSeedAsNeeded(capacity);
}

위 에서 알 고 있 듯 이 HashMap 을 구성 할 때 Entry 배열 을 새로 만 들 지 않 고 put 작업 을 할 때 현재 해시 표 가 빈 표 인지 확인 합 니 다.빈 표 라면 inflateTable 방법 으로 초기 화 합 니 다.위 에 이 방법의 코드 가 붙 어 있 습 니 다.방법 내부 에서 Entry 배열 의 용량 을 다시 계산 하 는 것 을 볼 수 있 습 니 다.HashMap 을 구성 할 때 들 어 오 는 초기 화 크기 는 2 의 멱 이 아 닐 수 있 으 므 로 이 수 를 2 의 멱 으로 바 꾸 고 새로운 용량 에 따라 Entry 배열 을 새로 만들어 야 합 니 다.해시 표를 초기 화 할 때 밸브 값 을 다시 설정 합 니 다.밸브 값 은 보통 capacity*loadFactor 입 니 다.또한 해시 테이블 을 초기 화 할 때 해시 피 드(hashSeed)를 초기 화 합 니 다.이 hashSeed 는 해시 함 수 를 최적화 하 는 데 사 용 됩 니 다.기본 값 은 0 으로 해시 알고리즘 을 대체 하지 않 지만 hashSeed 의 값 을 스스로 설정 하여 최적화 효 과 를 얻 을 수 있 습 니 다.구체 적 으로 다음 에 말씀 드 리 겠 습 니 다.
4.HashMap 은 언제 확장 여 부 를 판단 하고 어떻게 확장 하 는 지 판단 합 니까?

//  Entry  ,         
void addEntry(int hash, K key, V value, int bucketIndex) {
  //  HashMap                     
  if ((size >= threshold) && (null != table[bucketIndex])) {
    //  HashMap       ,           ,       
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }
  //     HashMap         ,        
  createEntry(hash, key, value, bucketIndex);
}

//        
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, initHashSeedAsNeeded(newCapacity));
  //              
  table = newTable;
  //       
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

put 방법 을 호출 하여 키 쌍 을 추가 할 때 집합 에 존재 하 는 key 가 없 으 면 addEntry 방법 으로 새 Entry 를 호출 합 니 다.위 에 붙 어 있 는 addEntry 코드 를 보면 새 Entry 를 만 들 기 전에 현재 집합 요소 의 크기 가 밸브 값 을 초과 하 는 지 여 부 를 판단 하고 밸브 값 을 초과 하면 resize 를 사용 하여 확장 합 니 다.들 어 오 는 새로운 용량 은 원래 해시 표 의 두 배 이 며,resize 방법 내부 에 원래 의 2 배 용량 의 Entry 배열 을 새로 만 듭 니 다.그리고 오래된 해시 표 에 있 는 요 소 를 모두 새로운 해시 표 로 옮 깁 니 다.그 중에서 재 하 시 를 진행 할 수 있 습 니 다.initHash Seed AsNeeded 방법 으로 계 산 된 값 에 따라 재 하 시 를 진행 할 지 여 부 를 확인 할 수 있 습 니 다.해시 표 의 이전 을 마 친 후 현재 해시 표를 새로운 것 으로 바 꾸 고 마지막 으로 새로운 해시 표 용량 에 따라 HashMap 의 밸브 값 을 다시 계산 합 니 다.
5.왜 Entry 배열 의 크기 는 2 의 멱 이 어야 합 니까?

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

index For 방법 은 해시 코드 에 따라 배열 에 대응 하 는 아래 표 시 를 계산 하 는 것 입 니 다.우 리 는 이 방법 내부 에서(&)연산 자 를 사용 한 것 을 볼 수 있다.조작 과 는 두 조작 수 에 대해 비트 연산 을 하 는 것 으로 대응 하 는 두 자리 가 모두 1 이면 결 과 는 1 이 고 그렇지 않 으 면 0 이다.작업 과 함께 작업 수의 높 은 비트 값 을 제거 하 는 데 자주 사 용 됩 니 다.예 를 들 어 01011010&0001111=0001010.우 리 는 계속해서 코드 로 돌아 가서 h&(length-1)가 무엇 을 했 는 지 보 자.

들 어 오 는 length 는 Entry 배열 의 길이 입 니 다.배열 의 아래 표 시 는 0 부터 계산 되 는 것 을 알 고 있 기 때문에 배열 의 최대 아래 표 시 는 length-1 입 니 다.length 가 2 의 멱 이 라면 length-1 의 이 진 위 는 모두 1 이다.이때 h&(length-1)의 역할 은 h 의 높 은 비트 값 을 제거 하고 h 의 낮은 비트 값 만 남 겨 서 배열 의 아래 표 시 를 하 는 것 이다.이 를 통 해 알 수 있 듯 이 Entry 배열 의 크기 가 2 로 규정된 멱 은 이 알고리즘 을 사용 하여 배열 의 아래 표 시 를 확정 할 수 있 도록 하 는 것 이다.
6.해시 함 수 는 Hash 코드 를 어떻게 계산 합 니까?

//  hash    
final int hash(Object k) {
  int h = hashSeed;
  //key String             
  if (0 != h && k instanceof String) {
    return sun.misc.Hashing.stringHash32((String) k);
  }
  h ^= k.hashCode();
  //    
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

hash 방법의 마지막 두 줄 은 hash 값 을 진정 으로 계산 하 는 알고리즘 입 니 다.hash 코드 를 계산 하 는 알고리즘 은 스 포일 러 함수 라 고 합 니 다.스 포일 러 함수 란 모든 것 을 한데 섞 는 것 입 니 다.여기 서 네 개의 오른쪽으로 이동 연산 을 사용 한 것 을 볼 수 있 습 니 다.목적 은 h 의 높 은 비트 와 낮은 비트 를 혼합 하여 낮은 비트 의 임 의 성 을 증가 시 키 는 것 이다.위 에서 우 리 는 포 지 셔 닝 배열 의 아래 표 시 는 hash 코드 의 낮은 비트 값 에 따라 확정 된다 는 것 을 알 고 있다.key 의 hash 코드 는 hashCode 방법 을 통 해 생 성 되 며,나 쁜 hashCode 방법 으로 생 성 된 hash 코드 의 낮은 비트 값 은 매우 중복 될 수 있 습 니 다.hash 코드 가 배열 에 비교적 고 르 게 투사 되 기 위해 교란 함 수 는 도움 이 되 었 다.고위 값 의 특성 을 낮은 값 에 섞 어 낮은 값 의 임 의성 을 증가 시 켜 산열 분 포 를 더욱 느슨하게 하여 성능 을 향상 시 켰 다.아래 그림 은 예 를 들 어 이 해 를 돕는다.

7.하 쉬 대신 어떻게 된 거 야?
우 리 는 hash 방법 을 보면 먼저 hashSeed 를 h 에 게 할당 합 니 다.이 hashSeed 는 바로 해시 씨앗 입 니 다.이것 은 무 작위 값 입 니 다.역할 은 해시 함 수 를 최적화 하 는 데 도움 을 주 는 것 입 니 다.hashSeed 는 기본 값 이 0 입 니 다.즉,기본 값 은 해시 알고리즘 을 대체 하지 않 습 니 다.그럼 hashSeed 는 언제 사용 하나 요?우선 해시 대신 오픈 을 설정 해 야 합 니 다.시스템 속성 에 jdk.map.althashing.threshold 의 값 을 설정 해 야 합 니 다.시스템 속성 에서 이 값 은 기본적으로-1 입 니 다.-1 일 때 해시 대신 밸브 값 을 Integer.MAX 로 사용 합 니 다.VALUE。하 쉬 대신 영원히 사용 하지 않 을 수도 있다 는 뜻 이기 도 하 다.물론 이 밸브 값 을 좀 작 게 설정 할 수 있 습 니 다.그러면 집합 요소 가 밸브 값 에 도달 하면 무 작위 hashSeed 가 생 성 됩 니 다.이로써 hash 함수 의 임 의성 을 증가 시 킵 니 다.왜 하 쉬 를 대신 해서 사용 합 니까?집합 요소 가 설정 한 밸브 값 에 이 르 렀 을 때 해시 표 가 포화 되 었 음 을 의미 합 니 다.해시 충돌 이 발생 할 가능성 이 크게 증가 합 니 다.이때 추 가 된 요소 에 대해 더욱 무 작위 적 인 해시 함 수 를 사용 하면 뒤에 추 가 된 요 소 를 산 목록 에 더욱 무 작위 로 분포 할 수 있 습 니 다.
주의:상기 분석 은 모두 JDK 1.7 을 바탕 으로 서로 다른 버 전 간 에 비교적 큰 변화 가 있 을 수 있 으 므 로 독자 들 은 주의해 야 합 니 다.