자바 향상 편(2,3)-HashMap 상세 설명
10557 단어 hashmap
정의
HashMap 은 Map 인 터 페 이 스 를 실현 하여 AbstractMap 을 계승 하 였 다.그 중에서 Map 인 터 페 이 스 는 키 가 값 에 비 치 는 규칙 을 정 의 했 고 AbstractMap 류 는 Map 인터페이스의 핵심 을 제공 하여 이 인 터 페 이 스 를 실현 하 는 데 필요 한 작업 을 최대한 줄 였 습 니 다.사실은 AbstractMap 류 는 Map 을 실 현 했 습 니 다.여기에 Map LZ 를 표시 하면 더욱 뚜렷 해 질 것 같 습 니 다!
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, SerializableHashMap 은 세 개의 구조 함 수 를 제공 합 니 다.
HashMap():기본 초기 용량(16)과 기본 로드 인자(0.75)를 가 진 빈 HashMap 을 구성 합 니 다.
HashMap(int initialCapacity):초기 용량 과 기본 로드 인자(0.75)를 지정 한 빈 HashMap 을 구성 합 니 다.
HashMap(int initialCapacity,float loadFactor):초기 용량 과 로드 인 자 를 지정 한 빈 HashMap 을 구성 합 니 다.
여기 서 두 개의 매개 변 수 를 언급 했다.초기 용량,로드 인자.이 두 개의 매개 변 수 는 HashMap 의 성능 에 영향 을 주 는 중요 한 매개 변수 이다.그 중에서 용량 은 해시 표 의 통 수량 을 나타 내 고 초기 용량 은 해시 표를 만 들 때의 용량 이다.로드 인 자 는 해시 표 가 용량 이 자동 으로 증가 하기 전에 얼마나 가득 찬 척도 에 이 를 수 있 는 지 를 나타 낸다.이 는 산 목록 의 공간 사용 정 도 를 평가 하고 부하 인자 가 클 수록 산 목록 의 충전 정도 가 높다 는 것 을 나타 낸다.반대로 작 을 수록링크 법의 산 목록 을 사용 할 때 하나의 요 소 를 찾 는 평균 시간 은 O(1+a)이기 때문에 부하 인자 가 클 수록 공간 에 대한 이용 이 더욱 충분 하지만 결 과 는 검색 효율 이 떨어진다.부하 인자 가 너무 작 으 면 산 목록 의 데이터 가 너무 적어 공간 에 심각 한 낭 비 를 초래 할 것 이다.시스템 의 기본 부하 인 자 는 0.75 이 며,일반적인 상황 에서 우 리 는 수정 할 필요 가 없다.
HashMap 은 빠 른 접근 을 지원 하 는 데이터 구조 로 성능 을 알 기 위해 서 는 데이터 구 조 를 알 아야 합 니 다.
3.데이터 구조
자바 에서 가장 많이 사용 되 는 두 가지 구 조 는 배열 과 시 뮬 레이 션 포인터(참조)라 는 것 을 알 고 있 습 니 다.거의 모든 데이터 구 조 는 이 두 가지 로 조합 하여 실현 할 수 있 습 니 다.HashMap 도 마찬가지 입 니 다.실제로 HashMap 은'링크 해시'로 다음 과 같은 데이터 구조 입 니 다
위의 그림 에서 우 리 는 HashMap 의 밑바닥 이 실현 되 는 지,아니면 수조 가 실현 되 는 지 알 수 있다.단지 수조 의 모든 항목 이 하나의 체인 일 뿐이다.그 중에서 인자 initialCapacity 는 이 배열 의 길 이 를 대표 합 니 다.다음은 HashMap 구조 함수 의 소스 코드 입 니 다.
public HashMap(int initialCapacity, float loadFactor) {
// <0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
// > ，HashMap 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// < 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
// initialCapacity 2 n 。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// HashMap ， HashMap
threshold = (int) (capacity * loadFactor);
// table
table = new Entry[capacity];
init();
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
}
위 에서 HashMap 의 데이터 구 조 를 간단하게 분 석 했 고 HashMap 이 어떻게 빠 른 접근 을 실현 하 는 지 연구 할 것 이다.
4.저장 실현:put(key,vlue)
일단 소스 부터 볼 게 요.
public V put(K key, V value) {
// key null， putForNullKey ， null table ， HashMap null
if (key == null)
return putForNullKey(value);
// key hash
int hash = hash(key.hashCode()); ------(1)
// key hash table
int i = indexFor(hash, table.length); ------(2)
// i e, key
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
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; //
}
}
// 1
modCount++;
// key、value i
addEntry(hash, key, value, i);
return null;
}1.교체 처 를 먼저 본다.이 교체 원인 은 같은 key 값 이 존재 하 는 것 을 방지 하기 위해 서 입 니 다.두 개의 hash 값(key)이 동시에 발견 되면 HashMap 의 처리 방식 은 새로운 value 로 오래된 value 를 교체 하 는 것 입 니 다.여기 서 key 를 처리 하지 않 았 습 니 다.이것 은 HashMap 에 같은 key 가 두 개 없다 는 것 을 설명 합 니 다.
2.보고 있다(1),(2).여 기 는 HashMap 의 에센스 가 있 는 곳 입 니 다.우선 hash 방법 입 니 다.이 방법 은 순수한 수학 계산 으로 h 의 hash 값 을 계산 하 는 것 입 니 다.
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}우 리 는 index For 방법 으로 돌아 갑 니 다.이 방법 은 h&(length-1)만 있 습 니 다.이 말 은 위의 모델 링 연산 을 제외 하고 매우 중요 한 책임 이 있 습 니 다.table 데 이 터 를 골 고루 분포 하고 공간 을 충분히 이용 합 니 다.
여기 서 우 리 는 length 가 16(2^n)과 15,h 가 5,6,7 이 라 고 가정 합 니 다
n=15 시 에 6 과 7 의 결과 가 똑 같 으 면 그들 이 table 에 저 장 된 위치 가 같다 는 것 을 나타 낸다.즉,충돌 이 발생 하면 6,7 은 한 위치 에서 링크 를 형성 하여 조회 속도 가 떨어진다.물론 여기 서 세 개의 숫자 만 분석 하 는 것 은 그리 많 지 않다.그러면 우 리 는 0-15 를 보 자
위의 도표 에서 우 리 는 모두 8 개의 충돌 이 발생 한 것 을 보 았 고 낭비 하 는 공간 이 매우 크다 는 것 을 발견 했다.1,3,5,7,9,11,13,15 곳 이 기록 되 지 않 은 것,즉 데 이 터 를 저장 하지 않 은 것 이다.이 는 그들 이 14 와&연산 을 할 때 얻 은 결과 의 마지막 위 치 는 영원히 0,즉 0001,0011,0101,0111,1001,1011,1101,1111 위치 에 데 이 터 를 저장 할 수 없고 공간 이 줄 어 들 며 충돌 확률 을 더욱 높 여 조회 속도 가 느 리 기 때문이다.한편,length=16 시 length C 1=15 즉 1111 이면 낮은 비트&연산 을 할 때 값 은 항상 원래 hash 값 과 같 고 높 은 비트 연산 을 할 때 그 값 은 낮은 비트 값 과 같다.그래서 length=2^n 일 때 서로 다른 hash 값 이 충돌 할 확률 이 비교적 낮 습 니 다.그러면 데이터 가 table 배열 에 고 르 게 분포 되 고 조회 속도 도 빠 릅 니 다.
여기에서 우 리 는 put 의 절 차 를 다시 복습 합 니 다.HashMap 에 key-value 를 추가 하고 싶 을 때 시스템 은 먼저 key 의 hash 값 을 계산 한 다음 hash 값 에 따라 table 에 저 장 된 위 치 를 확인 합 니 다.이 위치 에 요소 가 없 으 면 바로 삽입 합 니 다.그렇지 않 으 면 이 요소 링크 를 교체 하고 이에 따라 key 의 hash 값 을 비교 합 니 다.두 hash 값 이 같 고 key 값 이 같 으 면(e.hash==hash&&&(k=e.key)=key||key.equals(k))새로운 Entry value 로 원래 노드 의 value 를 덮어 씁 니 다.두 hash 값 이 같 지만 key 값 이 다 르 면 이 노드 를 이 링크 의 체인 헤드 에 삽입 합 니 다.구체 적 인 실현 과정 은 addEntry 방법 을 보면 다음 과 같다.
void addEntry(int hash, K key, V value, int bucketIndex) {
// bucketIndex Entry
Entry<K, V> e = table[bucketIndex];
// Entry bucketIndex ， Entry Entry
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
// HashMap ，
if (size++ >= threshold)
resize(2 * table.length);
}하 나 는 체인 의 생 성 이다.이것 은 매우 우아 한 디자인 이다.시스템 은 항상 새로운 Entry 대상 을 bucketIndex 에 추가 합 니 다.bucketIndex 에 대상 이 있 으 면 새로 추 가 된 Entry 대상 은 기 존의 Entry 대상 을 가리 키 며 Entry 체인 을 형성 합 니 다.그러나 bucketIndex 에 Entry 대상 이 없 으 면 e==null 입 니 다.그러면 새로 추 가 된 Entry 대상 이 null 을 가리 키 면 Entry 체인 이 생기 지 않 습 니 다.
2.확장 문제.
HashMap 에서 요소 의 수량 이 많아 지면 서 충돌 이 발생 할 확률 이 점점 커지 고 발생 하 는 링크 의 길이 가 점점 길 어 집 니 다.그러면 HashMap 의 속도 에 영향 을 줄 것 입 니 다.HashMap 의 효율 을 확보 하기 위해 시스템 은 반드시 특정한 임계 점 에서 확대 처 리 를 해 야 합 니 다.이 임계 점 은 HashMap 에서 요소 의 수량 이 table 배열 길이*로드 인자 와 같 습 니 다.그러나 확장 은 새로운 table 배열 의 위 치 를 다시 계산 하고 복사 처리 해 야 하기 때문에 시간 이 많이 걸 리 는 과정 이다.따라서 만약 에 우리 가 HashMap 에서 원소 의 개 수 를 예지 했다 면 미리 설 정 된 원소 의 개 수 는 HashMap 의 성능 을 효과적으로 향상 시 킬 수 있다.
5.읽 기 구현:get(key)
HashMap 의 저장 소 에 비해 취 하 는 것 이 간단 합 니 다.key 의 hash 값 을 통 해 table 배열 의 색인 에 있 는 Entry 를 찾 은 다음 키 에 대응 하 는 value 를 되 돌려 줍 니 다.
public V get(Object key) {
// null， getForNullKey value
if (key == null)
return getForNullKey();
// key hashCode hash
int hash = hash(key.hashCode());
// table
for (Entry<K, V> 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;
}
원본 링크:http://www.cnblogs.com/chenssy/p/3521565.html
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
투썸이 문제를 어떻게 해결할 수 있는지 봅시다. 이 접근 방식에 대한 코드를 확인해 보겠습니다. for 루프를 중첩했기 때문에 이 접근 방식의 시간 복잡도는 O(n^2)이고 공간 복잡도는 추가 공간을 사용하지 않기 때문...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
