자바 HashMap 실현 원리 상세 설명
HashMap 내부 저장 소
HashMap 내부 에 서 는 순간 변수 배열 table(또는 통)을 유지 하여 모든 키 쌍 관 계 를 저장 합 니 다.통 은 Entry 대상 배열 입 니 다.통 의 크기 는 필요 에 따라 크기 를 조정 할 수 있 고 길 이 는 2 의 차 멱 이 어야 합 니 다.다음 코드:
/**
* entry ，
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* ， ， 2
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
HashMap 은 두 개의 매개 변수 가 성능 에 영향 을 주 고 초기 용량 과 부하 인자 가 있 습 니 다.용량 은 해시 표 의 통 수량 이 고 초기 용량 은 해시 표 가 만 들 때 용량 일 뿐 부하 인 자 는 해시 표 가 용량 이 자동 으로 증가 하기 전에 더 많은 척도 에 이 를 수 있다.해시 표 의 항목 수가 부하 인자 와 현재 용량 의 곱 을 초과 할 때 이 해시 표 에 대해 rehash 작업(즉 내부 데이터 구 조 를 재 구축 하 는 것)을 하고 재 구축 할 때 현재 용량 의 두 배 수량 으로 새로 만들어 야 합 니 다.구조 기 를 통 해 초기 용량 과 부하 인 자 를 설정 할 수 있 습 니 다.기본 초기 용량 은 16 개 항목 이 고 최대 용량 은 2^30 제곱 항목 입 니 다.기본 부하 인 자 는 0.75 입 니 다.
통 은 물 을 저장 하 는 물통 과 같 습 니 다.기본 적 인 초기 저장 용량 은 16 개 단위 의 물 입 니 다.기본 적 으로 16*0.75 에 물 을 주입 할 때 다음 에 데 이 터 를 추가 할 때 먼저 용량 을 늘 려 32 단위 로 확대 합 니 다.0.75 는 부하 인자 로 초기 용량 과 부하 인 자 는 물통 을 만 들 때 설정 할 수 있다.물통 의 최대 용량 은 2 의 30 제곱 단위 의 물이 다.초기 용량 설정 의 수량 이 최대 용량 보다 많 을 때 최대 용량 을 기준 으로 합 니 다.확장 시 최대 용량 보다 크 면 바로 돌아 갑 니 다.
아래 는 HashMap 의 일부 소스 코드 로 기본 초기 용량,부하 인자 및 기타 상수 들 을 정의 합 니 다.
/**
* ， 2 The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* ， ， * 2 2 30 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* ，
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* ，
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* , ， ， 2
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* Map ， size +1 -1 .
*/
transient int size;
/**
* ， ， ：(capacity * load factor).
* @serial
*/
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
/**
* ， ， ，
*
* @serial
*/
final float loadFactor;
/**
* HashMap ， HashMap （ ，* rehash ， ）， * HashMap
*/
transient int modCount;
일반적으로 기본 부하 인자(0.75)는 시간 과 공간 원가 에서 절충 을 찾는다.부하 인자 가 너무 높 아 공간 비용 을 줄 였 지만 조회 비용 도 증가 했다.초기 용량 을 설정 할 때 맵 에 필요 한 항목 수 와 부하 요 소 를 고려 하여 rehash 작업 횟수 를 최대한 줄 여야 합 니 다.초기 용량 이 최대 항목 수 를 로드 인자 로 나 누 면 rehash 작업 이 일어나 지 않 습 니 다.
많은 맵 관 계 를 HashMap 인 스 턴 스 에 저장 하려 면 필요 에 따라 자동 rehash 작업 을 실행 하여 표 의 용량 을 늘 리 는 것 보다 충분 한 초기 용량 으로 만 들 면 맵 관 계 를 더욱 효과적으로 저장 할 수 있 습 니 다.
HashMap 데이터 구 조 를 재 구축 하기 위 한 코드:
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { // ，
threshold = Integer.MAX_VALUE;
return;
}
// table
Entry[] newTable = new Entry[newCapacity];
// table table ，
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//
threshold = (int) Math.min(newCapacity * loadFactor,
MAXIMUM_CAPACITY + 1);
}
네 번 째 구조 방법 은 이미 존재 하 는 Map 으로 새로운 HashMap 을 만 드 는 것 입 니 다.잠시 후에 말씀 드 리 겠 습 니 다.앞의 세 번 째 구조 방법 은 모두 세 번 째 로 두 개의 매개 변 수 를 가 진 방법 입 니 다.만약 에 매개 변 수 를 전달 하지 않 으 면 기본 적 인 수 치 를 사용 합 니 다.코드 는 다음 과 같 습 니 다.
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
put 방법
이제 HashMap 에서 중요 한 부분 을 살 펴 보도 록 하 겠 습 니 다.
/**
* 。 ，
*
* @param
* @param
* @return key ， key ， null（ null null key ）
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
1.먼저 put 방법 에서 통 이 기본 적 인 초기 화 되 지 않 은 상태 인지 판단 하고 초기 화 되 지 않 으 면 inflateTable 방법 으로 초기 화 한 다음 에 매개 변수 key 가 null 인지 판단 합 니 다.null 이면 putForNullKey 를 사용 하여 key 를 null 로 하 는 데 이 터 를 사용 합 니 다.putForNullKey 방법 은 아래 의 세 번 째 단계 와 똑 같 습 니 다.다만 키 가 null 인 데이터 의 기본 저장 위 치 는 첫 번 째 입 니 다.즉,아래 표 시 는 기본 값 이 0 입 니 다.
2. key 가 null 이 아니라면 hash()방법 으로 key 의 hash 값 을 가 져 옵 니 다.hash 값,통 의 길이 에 따라 index For 방법 으로 이 key 를 통 의 위치 에 놓 을 수 있 습 니 다.
3.Entry 대상 중 하나의 속성 next 가 있 는데 단 방향 링크 를 형성 하여 해시 값 과 같은 요 소 를 저장 할 수 있 습 니 다.따라서 key 의 hash 값 이 중복 되 었 을 때 저장 위치 도 중복 되 며,저장 위치 에 있 는 요소 와 이 요소 의 next 속성 링크 에서 주어진 key 와 key 의 hash 값 이 완전히 일치 하 는 지 판단 하면 됩 니 다.만약 완전히 일치 하 는 것 이 있다 면,대표 가 이미 존재 한다 면,낡은 값 을 교체 하고,낡은 값 을 반환 값 으로 직접 되 돌려 줍 니 다.
4.구조 수정 횟수 1 증가
5.addEntry 방법 을 호출 하여 새로운 키 쌍 을 HashMap 에 추가 합 니 다.addEntity 방법 은 먼저 현재 항목 데이터 가 부하 값(통 의 용량*부하 인자)보다 크 고 통 의 지정 위 치 는 null 이 아 닌 지 판단 합 니 다.만약 에 이미 크 고 지 정 된 위치 가 null 이 아니라면 통 의 용량 을 현재 용량 의 2 배로 조정 하고 통 의 용량 을 조정 하 는 것 은 위의 초기 용량 과 부하 인자 성능 조정 디 렉 터 리 를 참조 합 니 다.Hash 값 을 다시 계산 하여 저장 위 치 를 계산 합 니 다.createEntry 방법 을 통 에 저장 합 니 다.
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
/**
* Entry ， Entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
항목 을 새로 만 들 때 hash 값 을 계산 해 야 하기 때문에 길이 가 부족 할 때 길 이 를 조정 해 야 합 니 다.계 산 된 저장 위치 에 요소 가 있 을 때 링크 식 저장 이 필요 하기 때문에 HashMap 을 사용 하여 새로 만 드 는 작업 의 효율 이 그리 높 지 않 습 니 다.
get 방법
우선 get 방법의 원본 코드 를 보십시오.
/**
* ； ， ， null
* null ， null， containsKey
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
사용자 정의 대상 을 HashMap 키 로 사용 합 니 다.
class User {
//
protected int idNumber;
public User(int id){
idNumber = id;
}
}
public class TestUser{
public static void main(String[] args) {
Map<User, String> map = new HashMap<User, String>();
for (int i=0; i<5; i++) {
map.put(new User(i), " : " + i);
}
System.out.println("User3 ：" + map.get(new User(3)));
}
}
：
User3 ：null
정확 한 equals()방법 은 다음 과 같은 5 가지 조건 을 만족 시 켜 야 한다.-489 페이지 참조
다시 강조:기본 Object.equals()는 대상 의 주소 만 비교 하기 때문에 하나의 new User(3)는 다른 new User(3)와 같 지 않 습 니 다.따라서 자신의 클래스 를 HashMap 키 로 사용 하려 면 hashCode()와 equals()를 동시에 다시 불 러 와 야 합 니 다.
다음 코드 는 정상적으로 작 동 할 수 있 습 니 다.
class User {
//
protected int idNumber;
public User(int id){
idNumber = id;
}
@Override
public int hashCode() {
return idNumber;
}
@Override
public boolean equals(Object obj) {
return obj instanceof User && (idNumber==((User)obj).idNumber);
}
}
public class TestUser{
public static void main(String[] args) {
Map<User, String> map = new HashMap<User, String>();
for (int i=0; i<5; i++) {
map.put(new User(i), " : " + i);
}
System.out.println("User3 ：" + map.get(new User(3)));
}
}
：
User3 ： : 3
참고:
《자바 프로 그래 밍 사상》.
JDK 1.6 중국어 도움말 북
이상 은 본 고의 모든 내용 입 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.또한 저 희 를 많이 지지 해 주시 기 바 랍 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
