HashMap 실현 원리, 당신 은 이 편 을 다 볼 수 있 으 면 충분 합 니 다!

1. HashMap 바 텀 데이터 구 조 는 jdk 1.7 에서 HashMap 은 비트 통 + 링크 로 jdk 1.8 에서 이 루어 진 HashMap 은 비트 통 + 링크 + 빨 간 검 은 나무 가 8 개 노드 를 초과 하지 않 을 때 비트 통 + 링크 로 이 루어 지고 노드 수가 8 개 노드 를 초과 할 때 비트 통 + 빨 간 검 은 나무 로 이 루어 집 니 다.
둘째, HashMap 의 실현 원리 jdk 1.7 의 HashMap HashMap 의 주간 은 하나의 Entry 배열 이 고 배열 의 모든 항목 은 하나의 Entry 입 니 다. 해시 충돌 을 해결 하기 위해 배열 + 링크 방법 1 을 사용 하여 Entry 의 코드 구 조 를 설명 합 니 다.

transient  Node[] table;//          

동시에 Entry 는 HashMap 의 정적 내부 클래스 로 다음 과 같다.

static  class Entry{
final K key;
v value;
Entry next;//       Entry   ，      
int hash;//  Key  hashCode（）      

2 Entry 의 구 조 를 알 게 된 후에 우 리 는 간단 한 Entry 를 만 듭 니 다!

//  Entry     4   ，hash ，key ，value  Entry next
Entry(int h,K k,V v,Entry n)
{
hash=h;
key=k;
value=V;
next=n;
}

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

3. 간단 한 엔 트 리 의 구조 과정 을 보고 엔 트 리 의 원 리 를 설명 한다!Entry 의 저장 과정 을 요약 합 니 다: 키 값 을 입력 하려 고 할 때 1 키 값 에 따라 해당 하 는 hash 값 hashCode () 를 가 져 옵 니 다.
2 hash 값 에 따라 대응 하 는 배열 아래 에 hash. index For () 를 표시 합 니 다.
3 배열 아래 에 표 시 된 항목 에 따라 이 항목 을 저장 합 니 다.
3.1 이 아래 표 시 된 곳 에 대응 하 는 값 이 없 으 면 이 Entry 를 직접 저장 합 니 다.
3.2 아래 표 시 된 곳 에 값 이 있 으 면 그들의 hash 값 을 비교 합 니 다.
3.3 hash 값 이 다 르 면 해당 Entry 를 해당 Entry 체인 에 저장 합 니 다.
3.4 hash 값 이 같 으 면 이 Entry 를 이 곳 의 Entry 값 으로 대체 합 니 다.
그 원 리 를 대충 알 고 나 서 그 소스 코드 가 어떻게 실현 되 었 는 지 살 펴 보 자.
3. 소스 코드 분석 은 먼저 HashMap 의 모든 관건 적 인 속성 을 전면적으로 살 펴 봅 니 다.

transient Entry[] table;//         
transient int size;//       
int threshold;//               ，     //threshold=    *    
final  float loader;//    ，     0.75
transient int modCount;//      

해시 맵 과 해시 테이블 의 차 이 를 살 펴 보 자. 그 중에서 해시 표 의 초기 길 이 는 16 이 고 2 배의 속도 로 확장 되 며 해시 테이블 의 초기 길 이 는 11 이 며 2n + 1 의 속도 로 확장 된다.
1. HashMap 구조 기 는 hashMap 에 모두 네 개의 구조 기 가 있 는데 기본 적 인 구조 기 문법 에 중심 을 두 고 설명 합 니 다. (용량, 충전 인자)

public HashMap(int initialCapacity,float loadFactory){
//             ，         2 30   1<<30，  30 ，   0）
//       0，     
if(initialCapacity<0) throw new  IllegalArgumentException("Illegal inital capacity:"+initialCapacity);
//               ，                ，
if(initialCapacity >MAXIMUM_CAPACITY)
initicalCapacity=MAXIMUM_CAPACITY;

if(loadFactor <=0||Float.isNAN("illegal loadFactor:"+loadFactor);
this.loadFactor=loadFactor;
threshold=initialCapacity;
init();}

상기 코드 는 우리 의 HashMap 에 용량 과 로드 인 자 를 분 배 했 지만 table 배열 을 구축 하지 않 았 습 니 다. 이것 은 그 가 게 으 르 기 때 문 입 니 다. 우리 가 put 작업 을 해 야 할 때 만 table 배열 을 만 들 수 있 습 니 다.
2 HashMap 배열 상세 설명

public V put(K key,V value){
//1   =      
if(table==EMPTY_TABLE){
//  threshold initialCapacity，   1>>4（16）
inflateTable(threshold);//         ，         
}
//2        ，     put   
if(key==null)
return putForNullKey(value);//        ，       
int hash=hash(key);// key hashCode     ，          
//    ,            
int idx=indexFor(hash,table.length);
//3            ，          ，             ，            
//4   3      i，           ，            ，                
for(Entry e=table[i];e!=null;e=e.next){
//5          ，         ，      value
Object k;
//5.1   hash   key     
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
//5.2  hash  key     ，       ，       
V oldValue=e.value;
e.value=value;
e.recordAccess(this);//  C          
//    
return  oldValue;
}
}
modCount++;//       ，     
addEntry(hash,key,value,i);//    entry,/    hash，key value   i
return  null;
}

위의 방법 중 하 나 를 해석: 중점 포인트!!2.1 inflateTable: 배열 에 초기 화 값 을 어떻게 부여 하 는 지 보 세 요. 즉, 배열 의 용량 을 확인 하고 배열 을 구축 하 는 것 입 니 다.
위의 의문 은 아래 와 같다.

//1   =      
if(table==EMPTY_TABLE){
//  threshold initialCapacity，   1>>4（16）
inflateTable(threshold);//         ，         
}

inflateTable (threshold) 해석

private void inflateTable(int toSize){
//       ，  hashmap   16，  2      ，     capacity      ，      2   ，             2    ？       roundUpToPowerOf2(toSize）       ，       
//1      
int capacity=roundUpToPowerOf2(toSize);
//2      ，         
threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);//   threshold      HashMap    ， capacity*loadFactor MAXIMUM_CAPACITY+1    ，capacity      MAXIMUM_CAPACITY，   1>>30
//3     ，                   
table=new Entry[capacity];
initHashSeedAsNeed(capacity);
}
  ：inflateTable   capacity        ， capacity             

2.2 그 중의 roundUpToPowerOf 2 (tosize) 방법 역할 을 분석 합 니 다. 들 어 오 는 값 에 따라 이 배열 의 용량 이 이 배열 의 용량 에 가장 가 까 운 2 의 배수 임 을 확인 합 니 다.
2.2.1 이 배열 의 용량 이 16 보다 크 거나 같 으 며 2 의 차 멱 이 며 이 숫자 에 가장 가 까 운 용량 을 확보한다.

private static int roundUpToPowerOf2(int number){
return number>=MAXIMUM_CAPACITY?MAXIMUMCITY:(number>1)?Integer.highestOneBit((number-1)<<1):1;

결과 분석 1 number 가 최대 제한 치 보다 클 때 이 최대 치 는 2 의 30 제곱 2 입 니 다. 그렇지 않 으 면 실행 (number > 1) 합 니까?Integer. highest OneBit (number - 1) < 1): 13 number > 1 은 Integer. highest OneBit (number - 1) < 1) 를 실행 합 니 다.
3Hash 값 의 획득 주요 운용 수단: 이 또는 이 위 등 연산 을 사용 하여 마지막 저장 위치 분포 가 고 르 도록 확보한다.

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

4. 저장 위치 / index For () 방법

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

배열 아래 표 시 를 어떻게 확인 하 는 지 정리 합 니 다: key - - > hashCode () - - > hash () - - > hash 값 - - > indexfor () - - > 아래 표 시 를 저장 합 니 다.
위 에서 우 리 는 HashMap 에서 Entry 배열 의 초기 화 를 실현 하 였 으 며, 이어서 HashMap 에 Entry 배열 을 추가 하 였 습 니 다. 4 addEntry 의 실현 을 보 세 요.

//    ，   bucketIndex        IndeFor()         
void addEntry(int hash,k key,v value,int bucketIndex){
//                 ，      ，    hash  ，     2   
if((size>=threshold)&&(table[bucketIndex])){
resize(2*table.length);//                     
hash=(key!=null)?hash(key）:0;//  key  ，      0
}
//      Entry          
createEntry(hash,key,value,buckerIndex);
}

4.1 resize () 확장 메커니즘

void  resize(int newCapacity){
//1            HashMap     
Entry[] oldTable=table;
int oldCapacity=oldTable.length;
if(oldCapacity==MAXIMUN_CAPACITY){
threshold=Integer.MAX_VALUE;
return ;
}
Entry[] newTable =new Entry[newCapacity];
//  Table               Table   
transfer(newTable);
//         table   table
table=newTable;
//     
threshold=(int)(newCapacity*loadFactory);

위 에서 보 듯 이 확장 을 진행 할 때 먼저 이 구 배열 의 용량 이 배열 의 최대 용량 인지 아 닌 지 를 판단 한다. 만약 에 확장 할 필요 가 없다 면 확장 을 하고 Transfer 방법 을 사용 하여 구 배열 의 요 소 를 모두 새 배열 로 옮 기 고 임계값 을 계산한다.
5HashMap 은 앞에서 hashMap 의 초기 화 와 요소 의 추 가 를 읽 었 습 니 다. 다음은 HashMap 이 데 이 터 를 어떻게 읽 는 지 알려 드 리 겠 습 니 다!알다 시 피 HashMap 에서 데 이 터 를 읽 는 것 은 get 방법 을 통 해 읽 는 것 이기 때문에 다음은 이 get 방법 에 대한 해석 입 니 다!

public V get(Object   key){
//1   key    ，   ，   getForNullkey    
if(key==null)
return getForNullkey();
//    ，    key hash 
int hash=hash(key.hashCode());
//  hash       
int i=indexFor(hash,table.length);
//          
for(Entry e=table[i];e!=null;e=e.next){
Object k;
if(e.hash==hash&&((k=e.key)==key||key.equals(k)))
return e.value;
}return null;
}

이렇게 해서 우 리 는 HashMap 의 읽 기 를 완성 했다!!