면접 총결산 HashMap 의 put 는 어떻게 이 루어 졌 습 니까?
14480 단어 면접 총화
1 - HashMap 은 AbstractMap 류 를 계승 하여 Map 인 터 페 이 스 를 실현 합 니 다.그의 데이터 구 조 는 실제 적 으로 링크 배열 이 고 가장 바깥쪽 은 배열 이 며 배열 의 요 소 는 링크 이다.
HashMap 에서 key - value 는 항상 하나의 전체 로 처리 되 고 시스템 은 hash 알고리즘 에 따라 key - value 의 저장 위 치 를 계산 하여 key 를 통 해 빠르게 저장 하고 value 를 가 져 올 수 있 습 니 다.
HashMap 의 무 참 구조 함 수 는 기본 초기 인식 용량 (16) 과 기본 로드 인자 (0.75) 를 가 진 빈 HashMap 을 구성 할 수 있 습 니 다.
-- > 초기 용량, 로 딩 인자.이 두 개의 매개 변 수 는 HashMap 의 성능 에 영향 을 주 는 중요 한 매개 변수 로 그 중에서 용량 은 해시 표 의 통 수량 을 나타 낸다.
초기 용량 은 해시 표를 만 들 때 용량 입 니 다. 로드 인 자 는 해시 표 가 용량 이 자동 으로 증가 하기 전에 더 많은 척도 에 도달 할 수 있 습 니 다.
이것 은 산 목록 의 공간의 사용 정 도 를 평가 하 는데 부하 인자 가 클 수록 산 목록 의 충전 정도 가 높 고 반대로 작 다 는 것 을 나타 낸다.
링크 법의 산 목록 을 사용 할 때 하나의 요 소 를 찾 는 평균 시간 은 O (1 + a) 이기 때문에 부하 인자 가 클 수록 공간 에 대한 이용 이 더욱 충분 합 니 다.
그러나 결 과 는 검색 효율 이 떨 어 지 는 것 이다.부하 인자 가 너무 작 으 면 산 목록 의 데이터 가 너무 적어 공간 에 심각 한 낭 비 를 초래 할 것 이다.
2 - 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 implements Map.Entry {
final K key;
V value;
Entry next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
} 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 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 값 을 계산 하 는 것 입 니 다.
또한, HashMap 의 table 에 있어 데이터 분 포 는 균일 해 야 합 니 다 (모든 항목 에 하나의 요소 만 있 으 면 바로 찾 을 수 있 습 니 다). 너무 타 이 트 하거나 느슨 해 서 는 안 되 고 너무 타 이 트 하면 조회 속도 가 느 리 고 너무 느슨 하면 공간 을 낭비 할 수 있 습 니 다.hash 값 을 계산 한 후에 어떻게 해야만 table 요소 의 분 포 를 모두 보장 할 수 있 습 니까?우 리 는 모델 링 을 생각 할 것 입 니 다. 그러나 모델 링 의 소모 가 비교적 크기 때문에 HashMap 은 이렇게 처리 합 니 다. index For 방법 을 호출 합 니 다.HashMap 의 바 텀 배열 길 이 는 항상 2 의 n 제곱 이 고 구조 함수 에 존재 합 니 다: capacity < < = 1;이렇게 하면 항상 HashMap 의 바 텀 배열 길이 가 2 인 n 제곱 을 확보 할 수 있다.length = 2 ^ n 일 때 서로 다른 hash 값 이 충돌 할 확률 이 비교적 낮 습 니 다. 그러면 데이터 가 table 배열 에 고 르 게 분포 되 고 조회 속도 도 빠 릅 니 다.
--- update 2017.11.07 HashMap 의 용량 과 확장 참고http://blog.csdn.net/gaopu12345/article/details/50831631、http://blog.csdn.net/boom_man/article/details/78286610--------
(1) 첫 번 째 put 때, 즉 배열 이 비어 있 거나 배열 의 길이 가 0 이면 resize () 방법 으로 초기 화 통 배열 의 용량 은 16 이 고 확장 문턱 은 12 이다. 물론 이것 은 기본 적 인 상황 이다.
(2) HashMap 은 서로 다른 구조 방법, 빈 구조, HashMap (int initial Capacity), HashMap (int initial Capacity, float loadFactor), 세 번 째 대 삼 구조 에서 기본 확장 문턱 에 table SizeFor (initial Capacity) 방법 을 설정 하 였 으 니 주의 하 세 요.
(3) 확장 은 if (+ size > threshold) resize(); 즉, map 의 요소 개 수 는 문턱 을 넘 어야 확장 되 는 것 이지 tab 배열 이 loadFactor 에 도달 할 때 확장 되 는 것 이 아니 라 threshold = Integer. MAXVALUE 확장 중지!
(이상 JDK 1.6 에 서 는 1.8 에 서 는 putVal 방법 을 추가 하고, putVal 에 서 는 table 의 존재 여 부 를 판단 하 며, resize () 방법 으로 초기 화 표를 통 해 추 가 된 데이터 의 접점 을 끝 에 삽입 합 니 다)
★ GET 읽 기 실현:
public V get(Object key) {
// null， getForNullKey value
if (key == 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;
} 원본 정리:http://www.cnblogs.com/chenssy/p/3521565.html、http://blog.csdn.net/u013458516/article/details/49498803
좋은 웹페이지 즐겨찾기
