HashMap 깊이 해석: HashMap 에 대해 철저히 알 게 해 드 립 니 다.

앞 에 쓰다
HashMap 은 Map 족 에서 가장 많이 사용 되 는 것 이자 자바 Collection Framework 의 중요 한 구성원 입 니 다.본 고 는 먼저 HashMap 의 실질 을 제시 하고 Map, HashSet 과 의 관 계 를 개술 한 다음 에 HashMap 이 JDK 에서 의 정 의 를 내 렸 고 소스 코드 와 결합 하여 네 가지 구조 방식 을 분석 했다.마지막 으로 HashMap 의 데이터 구조, 실현 원리, 소스 코드 실현 세 가지 측면 에 대한 분석 을 통 해 그의 바 텀 Hash 저장 체제 에 깊이 들 어가 바 텀 배열 의 길이 가 항상 2 의 n 차방 의 원인 을 설명 하고 빠 른 액세스, 확대 와 확대 후의 중 하 쉬 의 원리 와 실현 을 밝 혔 다.
본 논문 의 모든 HashMap 에 관 한 소스 코드 는 모두 기초 이다. JDK 1.6 네, 서로 다른 JDK 버 전 간 에 약간의 차이 가 있 을 수 있 지만 저희 가 HashMap 의 데이터 구조, 원리 등 전체적인 파악 과 이해 에 영향 을 주지 않 습 니 다.
HashMap 개요
Map 은 Key - Value 가 맵 에 대한 추상 적 인 인터페이스 로 이 맵 은 중복 되 는 키, 즉 하나의 키 가 하나의 값 에 대응 하 는 것 을 포함 하지 않 습 니 다.HashMap 은 자바 Collection Framework 의 중요 한 구성원 이자 Map 족 (아래 그림 참조) 에서 우리 가 가장 자주 사용 하 는 것 이다.쉽게 말 하면 HashMap 은 해시 표 의 Map 인터페이스의 실현 을 바탕 으로 Key - Value 형식 으로 존재 한다. 즉, 저장 대상 은 Entry (Key 와 Value 를 동시에 포함) 이다.HashMap 에 서 는 hash 알고리즘 에 따라 key - value 의 저장 위 치 를 계산 하고 빠 른 접근 을 합 니 다.특히, HashMap 은 최대 한 개의 Entry 키 만 Null (여러 개 는 덮어 쓰기) 로 허용 하지만, 여러 개의 Entry 값 은 Null 로 허용 합 니 다.그 밖 에 HashMap 은 Map 의 비동기 적 인 실현 이다.
HashMap 과 HashSet 이 실현 하 는 인터페이스 규범 은 다 르 지만 그 밑 에 있 는 Hash 저장 메커니즘 은 완전히 같다.실제로 HashSet 자체 가 HashMap 을 바탕 으로 이 루어 진 것 이다.
HashMap 의 JDK 정의
HashMap 은 Map 인 터 페 이 스 를 실현 하고 AbstractMap 추상 류 를 계승 하 며 그 중에서 Map 인 터 페 이 스 는 키 맵 규칙 을 정의 합 니 다.AbstractCollection 추상 류 가 Collection 족 에서 의 역할 과 유사 하 다. AbstractMap 추상 류 는 Map 인터페이스의 핵심 실현 을 제공 하여 Map 인 터 페 이 스 를 실현 하 는 데 필요 한 작업 을 최대한 줄인다.HashMap 은 JDK 에서 다음 과 같이 정의 합 니 다.

public class HashMap extends AbstractMapimplements Map, Cloneable, Serializable {
	...}

HashMap 의 구조 함수
HashMap 은 모두 네 개의 구조 함 수 를 제 공 했 는데 그 중에서 기본 적 인 구조 함수 와 매개 변 수 는 Map 의 구조 함수 가 자바 Collection Framework 규범 의 추천 실현 이 고 나머지 두 개의 구조 함 수 는 HashMap 이 전문 적 으로 제공 한 것 이다.
1、HashMap()
이 구조 함 수 는 > 기본 초기 용량 (16) 과 기본 부하 인자 (0.75) 를 가 진 빈 HashMap 을 구성 하 는 것 을 의미 합 니 다. 자바 Collection Framework 규범 이 추천 하 는 것 입 니 다. 그 소스 코드 는 다음 과 같 습 니 다.

 /** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */
 public HashMap() {
 //    :                    this.loadFactor = DEFAULT_LOAD_FACTOR; 
 //HashMap       ，      HashMap           threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
 // HashMap         ，              table = new Entry[DEFAULT_INITIAL_CAPACITY];
 init();
 }

2、HashMap(int initialCapacity, float loadFactor)
이 구조 함 수 는 초기 용량 과 부하 인 자 를 지정 하 는 빈 HashMap 을 구성 하 는 데 목적 을 둡 니 다. 그 소스 코드 는 다음 과 같 습 니 다.

 /** * Constructs an empty HashMap with the specified initial capacity and load factor. */
 public HashMap(int initialCapacity, float loadFactor) {
 //         0 if (initialCapacity  MAXIMUM_CAPACITY)
 initialCapacity = MAXIMUM_CAPACITY;
 //         0 
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
 throw new IllegalArgumentException("Illegal load factor: " +
 loadFactor);
 // HashMap       2    ，   initialCapacity     2^n 
 int capacity = 1;
 while (capacity  
    
3、HashMap(int initialCapacity)
 
    
                         (0.75)   HashMap，     ：
 
    
 // Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75) public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR); //            }
  
4、HashMap(Map extends K, ? extends V> m) 
이 구조 함 수 는 지 정 된 맵 과 같은 맵 을 가 진 HashMap 을 구성 하 는 것 을 의미 합 니 다. 초기 용량 은 16 (지 정 된 맵 의 크기 에 구체 적 으로 의존) 보다 작 지 않 고 부하 인 자 는 0.75 이 며 자바 Collection Framework 규범 이 추천 하 는 것 입 니 다. 그 소스 코드 는 다음 과 같 습 니 다.
 // Constructs a new HashMap with the same mappings as the specified Map. 
 // The HashMap is created with default load factor (0.75) and an initial capacity // sufficient to hold the mappings in the specified Map. public HashMap(Map extends K, ? extends V> m) {
 //         16 
 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 putAllForCreate(m);
 }
  
여기 서 우 리 는 두 가지 매우 중요 한 매개 변 수 를 언급 했다. 초기 용량 과 부하 인자, 이 두 가지 매개 변 수 는 HashMap 의 성능 에 영향 을 주 는 중요 한 매개 변수 이다.그 중에서 용량 은 해시 표 의 통 수량 (table 배열 의 크기) 을 나타 내 고 초기 용량 은 해시 표를 만 들 때 통 의 수량 입 니 다.부하 인 자 는 해시 표 가 용량 이 자동 으로 증가 하기 전에 얼마나 가득 채 울 수 있 는 척도 로 산 목록 의 공간의 사용 정 도 를 평가 하고 부하 인자 가 클 수록 산 목록 의 충전 정도 가 높 고 반대로 작 음 을 나타 낸다.
HashMap 의 데이터 구조
해시 의 관련 개념
Hash 는 임의의 길이 의 입력 (예 영사, pre - image 라 고도 함) 을 해시 알고리즘 을 통 해 고정된 길이 의 출력 (보통 정형) 으로 변환 하 는데 이 출력 은 해시 값 이다.이러한 전환 은 압축 맵 이다. 즉, 해시 값 의 공간 은 보통 입력 한 공간 보다 훨씬 작다.서로 다른 입력 은 같은 출력 으로 흩 어 질 수 있 으 며, 흩 어 진 값 에서 유일한 입력 값 을 정할 수 없습니다.쉽게 말 하면 임의의 길이 의 메 시 지 를 특정한 길이 의 이자 요약 함수 로 압축 하 는 것 이다.
해시 의 응용: 데이터 구조
우 리 는 배열 의 특징 은 주소 찾기 가 쉽 고 삽입 과 삭제 가 어렵 다 는 것 을 알 고 있다.링크 의 특징 은 주소 찾기 가 어렵 고 삽입 과 삭제 가 쉽다 는 것 이다.그렇다면 우 리 는 이들 의 특성 을 종합 하여 주소 찾기 가 쉽 고 삽입 과 삭제 도 쉬 운 데이터 구 조 를 만 들 수 있 을 까?답 은 긍정 적 이다. 이것 이 바로 우리 가 제기 하고 자 하 는 해시 표 이다.사실은 하 쉬 표 는 여러 가지 서로 다른 실현 방법 이 있 습 니 다. 우 리 는 다음 에 가장 전형 적 인 방법 인 지퍼 법 을 설명 합 니 다. 우 리 는 이 를 링크 의 배열 로 이해 할 수 있 습 니 다. 아래 그림 과 같 습 니 다.
우 리 는 위의 그림 에서 볼 수 있 듯 이 왼쪽 은 분명히 배열 이 고 배열 의 모든 구성원 은 하나의 링크 이다.이 데이터 구조 에 포 함 된 모든 요 소 는 하나의 지침 을 포함 하여 요소 간 의 링크 에 사 용 됩 니 다.우 리 는 요소 자체 의 특징 에 따라 요 소 를 서로 다른 링크 에 배분 한다. 반대로 우 리 는 바로 이런 특징 을 통 해 정확 한 링크 를 찾 은 다음 에 링크 에서 정확 한 요 소 를 찾 는 것 이다.그 중에서 요소 특징 에 따라 요소 배열 의 아래 표 시 를 계산 하 는 방법 은 바로 해시 알고리즘 이다.
전반적 으로 해시 표 는 빠 른 검색, 삭제 의 기본 데이터 구조 로 적합 하 며, 일반적으로 총 데 이 터 량 을 메모리 에 넣 을 수 있어 야 한다.해시 표를 사용 할 때 다음 과 같은 몇 가지 관건 이 있 습 니 다.
 hash 함수 (해시 알고리즘) 의 선택: 서로 다른 대상 (문자열, 정수 등) 에 대한 구체 적 인 해시 방법;
  
 충돌 처리: 자주 사용 하 는 두 가지 방식 이 있 는데 하 나 는 open hashing, 즉 > 지퍼 법 이다.
  
 다른 하 나 는 closed hashing, 즉 주소 법 (opened addressing) 이다.
  
HashMap 의 데이터 구조
우 리 는 자바 에서 가장 자주 사용 하 는 두 가지 구 조 는 배열 과 링크 로 거의 모든 데이터 구 조 는 이 두 가지 로 조합 하여 실현 할 수 있다 는 것 을 알 고 있다. HashMap 은 바로 이런 응용의 전형 이다.실제로 HashMap 은 하나의 링크 배열 로 다음 과 같은 데이터 구조 입 니 다.
위의 그림 에서 우 리 는 HashMap 의 밑바닥 이 실현 되 는 지 수조 가 되 는 지 형상 적 으로 볼 수 있다. 다만 수조 의 모든 항목 이 하나의 사슬 일 뿐이다.그 중에서 매개 변수 initialCapacity 는 이 배열 의 길이, 즉 통 의 개 수 를 대표 합 니 다.3 절 에서 우 리 는 HashMap 의 기본 구조 함수 의 소스 코드 를 알 게 되 었 다.
 /** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). */
 public HashMap() {
 //    :                    this.loadFactor = DEFAULT_LOAD_FACTOR; 
 //HashMap       ，      HashMap           threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
 // HashMap         ，              table = new Entry[DEFAULT_INITIAL_CAPACITY];
 init();
 }
  
상기 소스 코드 에서 알 수 있 듯 이 HashMap 을 새로 만 들 때마다 Entry 형식의 table 배열 을 초기 화 합 니 다. 그 중에서 Entry 유형의 정 의 는 다음 과 같 습 니 다.
static class Entry implements Map.Entry {
 final K key; //       V value; //       Entry next; //       final int hash; // hash(key.hashCode())       /** * Creates new entry. */
 Entry(int h, K k, V v, Entry n) { // Entry       value = v;
 next = n;
 key = k;
 hash = h;
 }
 ......}
  
그 중에서 Entry 는 HashMap 의 내부 클래스 로 Map. Entry 인 터 페 이 스 를 실 현 했 는데 키 키 키, 값 value, 다음 노드 next, 그리고 hash 값 네 가지 속성 을 포함한다.사실 Entry 는 해시 표를 구성 하 는 초석 으로 해시 표 에 저 장 된 요소 의 구체 적 인 형식 이다.
HashMap 의 빠 른 액세스
다음은 JDK 소스 코드 와 결합 하여 HashMap 의 액세스 실현 을 살 펴 보 겠 습 니 다.
HashMap 의 저장 실현
HashMap 에서 키 값 이 맞 는 저장 소 는 put (key, vlue) 방법 으로 이 루어 집 니 다. 그 소스 코드 는 다음 과 같 습 니 다.
 /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or null if there was no mapping for key. * Note that a null return can also indicate that the map previously associated null with key. */
 public V put(K key, V value) {
 // key null ，  putForNullKey  ，         table       
 if (key == null)
 return putForNullKey(value); 
 //  key hashCode  hash  int hash = hash(key.hashCode()); // ------- (1) //               （   ） int i = indexFor(hash, table.length); // ------- (2) // table  i       ，   key       for (Entry e = table[i]; e != null; e = e.next) { // ------- (3) 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; //      }
 }
 modCount++; //      1，       // HashMap     ，           addEntry(hash, key, value, i); 
 return null;
 }
  
NULL 키 에 대한 특별 처리: putForNullKey ()
우 리 는 직접 그 소스 코드 를 본다.
 /** * Offloaded version of put for null keys */
 private V putForNullKey(V value) {
 //  key==null，     table     ，  table[0] for (Entry e = table[0]; e != null; e = e.next) { 
 if (e.key == null) { //      key null  ，     ，      V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++; //      addEntry(0, null, value, 0); //   ，      table[0]     return null;
 }
  
HashMap 의 해시 정책 (알고리즘)
/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions. This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits.
 *
 * Note: Null keys always map to hash 0, thus index 0.
 */
static int hash( int h )
{
/*
 * This function ensures that hashCodes that differ only by
 * constant multiples at each bit position have a bounded
 * number of collisions (approximately 8 at default load factor).
 */
	h ^= (h >>> 20) ^ (h >>> 12);
	return(h ^ (h >>> 7) ^ (h >>> 4) );
}
  
JDK 가 공식 적 으로 이 방법 에 대한 설명 처럼 hash () 방법 으로 한 대상 의 hashCode 를 재 계산 하 는 것 은 품질 이 낮은 hashCode () 함수 의 실현 을 방지 하기 위 한 것 이다.hashMap 의 지지 배열 길 이 는 항상 2 의 미터 이기 때문에 오른쪽 이동 을 통 해 낮은 비트 의 데 이 터 를 최대한 다 르 게 하여 hash 값 의 분 포 를 최대한 고 르 게 할 수 있 습 니 다.
상기 hash () 방법 을 통 해 Key 의 hash 값 을 계산 한 후에 어떻게 해 야 요소 가 table 의 모든 통 에 고 르 게 분포 되 는 것 을 확보 할 수 있 습 니까?우 리 는 모델 링 을 생각 할 것 입 니 다. 그러나 모델 링 의 효율 이 비교적 낮 기 때문에 HashMap 은 위의 index For () 방법 으로 처 리 했 습 니 다. 간단 할 뿐만 아니 라 효율 도 높 습 니 다. 소스 코드 는 다음 과 같 습 니 다.
/** * * Returns index for hash code h. * */static int indexFor( int h, int length ){
	return(h & (length - 1) ); /*          ，          */}
  
HashMap 의 키 쌍 추가: addEntry ()
우 리 는 직접 그 소스 코드 를 본다.
 /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. * 
 *                 */
 void addEntry(int hash, K key, V value, int bucketIndex) {
 //  bucketIndex     Entry e = table[bucketIndex];
 //      Entry    bucketIndex        
 table[bucketIndex] = new Entry(hash, key, value, e);
 // HashMap            threshold，        if (size++ >= threshold)
 resize(2 * table.length);
 }
  
HashMap 의 확장: resize ()
HashMap 에서 요소 의 수량 이 점점 많아 지면 서 충돌 이 발생 할 확률 이 점점 커지 고 발생 하 는 서브 체인 의 길이 가 점점 길 어 집 니 다. 그러면 HashMap 의 액세스 속도 에 영향 을 줄 것 입 니 다.HashMap 의 효율 을 확보 하기 위해 서 시스템 은 특정한 임계 점 에서 확장 처 리 를 해 야 합 니 다. 이 임계 점 은 HashMap 에서 요소 의 수량 이 수치 적 으로 threshold (table 배열 길이 * 로드 인자) 와 같 습 니 다.그러나 확장 은 새로운 table 배열 에 있 는 위 치 를 다시 계산 하고 복사 처리 해 야 하기 때문에 시간 이 많이 걸 리 는 과정 이 라 고 할 수 밖 에 없다.따라서 만약 에 우리 가 HashMap 에서 원소 의 개 수 를 미리 예측 할 수 있다 면 HashMap 을 구성 할 때 원소 의 개 수 를 미리 설정 하면 HashMap 의 성능 을 효과적으로 향상 시 킬 수 있다.우 리 는 직접 그 소스 코드 를 본다.
/** * * 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;
	/*   oldCapacity       ，    threshold    Integer.MAX_VALUE */
	if ( oldCapacity == MAXIMUM_CAPACITY )
	{
		threshold = Integer.MAX_VALUE;
		return; /*      */
	}
	/*   ，          */
	Entry[] newTable = new Entry[newCapacity];
	/*    Entry           */
	transfer( newTable );
	table = newTable;
	threshold = (int) (newCapacity * loadFactor); /*      threshold */}
  
HashMap 의 중 해시: transfer ()
하 쉬 를 다시 계산 하 는 것 은 원래 하 쉬 맵 의 요소 가 새 table 배열 에 있 는 위 치 를 다시 계산 하고 복사 처리 하 는 과정 입 니 다. 우 리 는 그 소스 코드 를 직접 봅 니 다.
/** * * Transfers all entries from current table to newTable. * */void transfer( Entry[] newTable ){/*      table      src */
	Entry[] src = table;
	int newCapacity = newTable.length;/*     src            newTable   */
	for ( int j = 0; j  e = src[j];
		if ( e != null )
		{
			src[j] = null; /* src    *//*                newTable        */
			do
			{
				Entry next = e.next;/* e.hash    hash(key.hashCode())    ; *//*    newTable    ，                          */
				int i = indexFor( e.hash, newCapacity );
				e.next		= newTable[i];
				newTable[i]	= e;
				e		= next;
			}
			while ( e != null );
		}
	}}
  
특히 주의해 야 할 것 은 중 하 쉬 과정 에서 원래 한 통 에 속 했 던 Entry 대상 이 다른 통 으로 나 눌 수 있다 는 점 이다. HashMap 의 용량 이 변 했 기 때문에 h & (length - 1) 의 값 도 상응 한 변화 가 생 길 수 있다.극단 적 으로 무 거 운 해시 이후 에 도 한 통 에 속 했 던 엔 트 리 대상 이 같은 통 에 속한다 면 무 거 운 해시 도 의 미 를 잃 게 된다.
HashMap 읽 기 실현
HashMap 의 저장 소 에 비해 읽 기 가 간단 합 니 다.HashMap 은 key 의 hash 값 을 통 해 table 배열 의 특정한 통 을 찾 은 다음 에 이 key 에 대응 하 는 value 를 찾 아 되 돌려 주면 되 기 때 문 입 니 다. 소스 코드 는 다음 과 같 습 니 다.
/** * * Returns the value to which the specified key is mapped, * * or {@code null} if this map contains no mapping for the key. * * 
More formally, if this map contains a mapping from a key * * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * * key.equals(k))}, then this method returns {@code v}; otherwise * * it returns {@code null}. (There can be at most one such mapping.) * 
A return value of {@code null} does not necessarily * * indicate that the map contains no mapping for the key; it's also * * possible that the map explicitly maps the key to {@code null}. * * The {@link #containsKey containsKey} operation may be used to * * distinguish these two cases. * @see #put(Object, Object) * */public V get( Object key ){/*   null，  getForNullKey        value */
	if ( key == null )/*  table         key   null    ；    ，    null */
		return(getForNullKey() );/*     key   hashCode       hash   */
	int hash = hash( key.hashCode() );/*    table         */
	for ( Entry 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);}
  
키 가 NULL 인 키 쌍 에 대해 HashMap 은 전문 적 인 처 리 를 제공 합 니 다: getForNullKey (), 그 소스 코드 는 다음 과 같 습 니 다.
/** * * Offloaded version of get() to look up null keys. Null keys map * * to index 0. This null case is split out into separate methods * * for the sake of performance in the two most commonly used * * operations (get and put), but incorporated with conditionals in * * others. * */private V getForNullKey(){
	/*   NULL       ，          */
	for ( Entry e = table[0]; e != null; e = e.next )
	{
		if ( e.key == null )
			return(e.value);
	}
	/*   NULL        ，      null */
	return(null);}
  
따라서 HashMap 의 get (Object key) 방법 을 호출 한 후 반환 값 이 NULL 이면 다음 과 같은 두 가지 가능성 이 있 습 니 다.
 이 키 에 대응 하 는 값 은 null 입 니 다.
  
 HashMap 에는 이 key 가 존재 하지 않 습 니 다.
  
다음으로 전송:https://blog.51cto.com/14207296/2380981