자바 에서 HashMap 에 대한 심도 분석

자바 의 세계 에서 클래스 든 각종 데이터 든 그 구조의 처 리 는 전체 프로그램의 논리 와 성능 의 관건 이다.본인 은 성능 과 논리 가 동시에 존재 하 는 문 제 를 접 했 기 때문에 이 방면 의 문 제 를 연구 하기 시 작 했 습 니 다.크 고 작은 포럼 을 다 찾 았 고,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,여기 HashMap 을 가지 고 연구 해 보 세 요.HashMap 은 JDK 의 큰 실 용적 인 도구 라 고 할 수 있 습 니 다.각 Object 를 매 핑 하여'키-값'에 대응 하 는 빠 른 접근 을 실현 합 니 다.근 데 실제로 뭐 했 어 요?그 전에 부하 인자 와 용량 의 속성 을 소개 합 니 다.알다 시 피 HashMap 의 실제 용량 은 인자*용량 이 고 기본 값 은 16 입 니 다.×0.75＝12； 이것 은 매우 중요 합 니 다.효율 에 어느 정도 영향 을 줍 니 다!HashMap 에 저 장 된 대상 이 이 용량 을 초과 하면 HashMap 은 액세스 표를 다시 구성 합 니 다.이것 이 바로 큰 문제 입 니 다.제 가 나중에 천천히 소개 하 겠 습 니 다.어쨌든 당신 이 몇 개의 대상 을 저장 해 야 하 는 지 이미 알 고 있다 면 이 실제 용량 의 받 아들 일 수 있 는 숫자 로 설정 하 는 것 이 좋 습 니 다.두 가지 관건 적 인 방법 은 put 와 get:먼저 이러한 개념 이 있 습 니 다.HashMap 은 Map,Cloneable,Serializable 인터페이스 와 AbstractMap 류 를 계승 한 것 입 니 다.안의 Iterator 는 주로 내부 류 인 HashIterator 와 다른 몇 개의 iterator 류 가 실현 되 었 습 니 다.물론 Map.Entry 의 Entry 내부 류 를 계승 하 는 것 도 중요 합 니 다.모두 가 소스 코드 가 있 기 때문에 여러분 이 관심 이 있 으 면 이 부분 을 볼 수 있 습 니 다.제 가 주로 설명 하고 싶 은 것 은 Entry 내부 류 입 니 다.이것 은 hash,value,key 와 next 라 는 네 가지 속성 을 포함 하고 있 습 니 다.매우 중요 합 니 다.put 의 원본 코드 는 다음 과 같 습 니 다 Public Object put(Object key,Object value){Object k=maskNull(key);이것 은 키 가 비어 있 는 지 아 닌 지 를 판단 하 는 것 입 니 다.심오 하지 않 습 니 다.사실 비어 있 으 면 static Object 를 키 로 되 돌려 줍 니 다.이것 이 바로 HashMap 이 빈 키 를 허용 하 는 이유 입 니 다.　　int hash = hash(k); 　　int i = indexFor(hash, table.length); 이 연속 두 걸음 이 바로 HashMap 의 가장 큰 곳 입 니 다!연 구 를 마 친 후에 저 는 부끄러워 했 습 니 다.그 중에서 hash 는 바로 key 라 는 Object 의 hashcode 를 통 해 hash 를 한 다음 에 index For 를 통 해 Object table 의 색인 값 을 얻 었 습 니 다.　　table？？？놀 라 지 마 세 요.사실 HashMap 도 신 이 나 지 않 아 요.table 로 놓 은 거 예요.가장 큰 것 은 hash 로 색인 을 정확하게 되 돌 릴 수 있다 는 것 이다.그 중의 hash 알고리즘 은 제 가 JDK 의 작가 Doug 에 게 연락 을 했 습 니 다.그 는 저 에 게'The art of programing vol 3'를 보라 고 권 했 습 니 다.가 증 스 러 운 것 은 제 가 계속 찾 았 는데 찾 지 못 했 습 니 다.그 가 이렇게 말 하 자 저 는 더욱 급 했 습 니 다.주머니 가 텅 비 었 습 니 다!!put 에 주 의 를 기 울 였 는 지 모 르 겠 지만,사실은 되 돌아 오 는 방법 입 니 다.같은 키 의 put 를 덮어 쓰 고 오래된 값 으로 돌아 갑 니 다!다음 과 같은 방법 은 HashMap 의 구 조 를 철저히 설명 했다.사실은 하나의 표 에 해당 하 는 위치 에 있 는 Entry 의 링크 를 더 한 것 이다.for(Entry e=table[i];e != null; e = e.next) { 　　if (e.hash == hash && eq(k, e.key)) { 　　Object oldvalue = e.value; 　　e.value = value; //새로운 값 을 대응 하 는 키 에 부여 합 니 다.　　e.recordAccess(this); //빈 방법,return oldvalue 구현 대기;/같은 키 값 에 대응 하 는 오래된 값 을 되 돌려 줍 니 다.　　} 　　} 　　modCount++; //구조 적 변경 횟수 addEntry(hash,k,value,i);/새로운 요 소 를 추가,관건!　　return null; //같은 키 값 이 되 돌아 오지 않 음}관건 적 인 방법 을 꺼 내 분석 합 니 다:void addEntry(int hash,Object key,Object value,int bucketIndex){table[bucketIndex]=new Entry(hash,key,value,table[bucketIndex]);hash 알고리즘 은 서로 다른 키 값 에 같은 hash 코드 를 가지 고 같은 table 색인 을 가 질 수 있 기 때 문 입 니 다.예 를 들 어 key="33"과 key=Object g 의 hash 는 모두－8901334 입 니 다.그러면 indexfor 를 거 친 후의 색인 은 모두 i 입 니 다.그러면 new 일 때 이 Entry 의 next 는 이 원래 의 table[i]를 가리 키 고 다음 것 도 마찬가지 로 링크 를 만 듭 니 다.put 의 순환 과 e.next 를 맞 춰 오래된 값 을 얻 습 니 다.여기까지,HashMap 의 구조,여러분 도 잘 아 시 겠 죠?if(size++>=threshold)//이 threshold 는 실제 수용 할 수 있 는 양 resize(2*table.length)입 니 다./이 용량 을 초과 하면 Object table 을 재 구성 하 는 이른바 재 구성 도 신 이 나 지 않 습 니 다.바로 두 배 큰 table 을 만 드 는 것 입 니 다.조심 하 세 요!!이게 효율 이 야!!만약 당신 이 당신 의 HashMap 을 그렇게 여러 번 재 구성 할 필요 가 없다 면 효율 이 크게 높 아 질 것 입 니 다!여기까지 만 해도 차이 가 많 지 않 습 니 다.get 은 put 보다 훨씬 간단 합 니 다.여러분,put 를 알 고 get 도 별로 차이 가 나 지 않 습 니 다.collections 에 대해 저 는 광범 위 하 게 적합 하 다 고 생각 합 니 다.특유 에 완전히 적합 하지 않 을 때 여러분 의 프로그램 이 특별한 용도 가 필요 하 다 면 직접 쓰 세 요.사실은 간단 합 니 다.저 자 는 저 에 게 이렇게 말 했 습 니 다.그 는 저 에 게 링크 드 하 쉬 맵 을 사용 하 라 고 권 했 습 니 다.저 는 소스 코드 를 본 후에 링크 하 쉬 맵 은 사실은 하 쉬 맵 을 계승 한 다음 에 override 에 해당 하 는 방법 입 니 다.관심 이 있 는 동인,자신 looklooklook)은 Object table 을 만 들 고 해당 하 는 알고리즘 을 쓰 면 ok 입 니 다.예 를 들 어 Vector,list 같은 것 은 모두 간단 하고 많 으 면 많은 동기 화 된 성명 입 니 다.사실 Vector 와 같은 삽입,삭제 가 많 지 않 은 것 을 실현 하려 면 Object table 로 실현 하고 색인 액세스,추가 등 을 누 를 수 있 습 니 다.삽입 하면 많은 것 을 삭제 할 수 있 습 니 다.두 개의 Object table 을 만 든 다음 에 모든 요 소 는 next 구 조 를 가 진 table 저장 소 를 사용 합 니 다.i 에 삽입 하려 면 i 는 이미 요소 가 있 습 니 다.next 로 연결 한 다음 에 size+++다른 table 에 그 위 치 를 기록 할 수 있 습 니 다.