Hashmap \ \ LinkedHashMap 의 실현 원리 분석
1. 데이터 구조
hashmap 는 실제 적 으로 하나의 배열 + 링크 의 데이터 구조 이 고 hashmap 바 텀 은 하나의 배열 구조 이 며 배열 의 모든 항목 은 하나의 링크 구조 이다.링크 는 hash 충돌 을 해결 하기 위해 서 입 니 다.
/**
*
*/
static final HashMapEntry,?>[] EMPTY_TABLE = {};
/**
* ， ， 2 ，
*/
transient HashMapEntry[] table = (HashMapEntry[]) EMPTY_TABLE;
/**
* ， next ， map ， key、value
*/
static class HashMapEntry implements Map.Entry {
final K key;
V value;
HashMapEntry next;
int hash;
} 2. hashmap 초기 화
hashmap 의 구조 함수 에서 hashmap 용량 을 초기 화 합 니 다. 기본 적 인 초기 용량 은 16 입 니 다. 적재 용량 은 0.75 이기 때 문 입 니 다. 즉, 용량 이 12 에 이 르 면 hashmap 를 확대 하고 한 부 를 확대 하 며 32 로 변 합 니 다. 우 리 는 그 구조 함 수 를 호출 하여 용량 크기 를 스스로 설정 할 수 있 습 니 다.
//initialCapacity ， 16、loadFactor ， 0.75
public HashMap(int initialCapacity, float loadFactor) {
}3. hasmap 액세스 구현
3.1 put 조작
put 작업 이 이 루어 지 는 방식 은 key 에 따라 hash 값 을 계산 하고 배열 에 대응 하 는 위 치 를 찾 아 이 배열 에 대응 하 는 위치 에 값 이 있 는 지 판단 하고 값 이 있 으 면 같은 key 값 이 있 는 지 판단 하 며 새 값 을 오래된 값 으로 바 꾸 고 오래된 값 을 되 돌려 저장 하 는 것 입 니 다.이 배열 은 대응 하 는 위치 에 값 이 없 거나 값 이 있 지만 같은 key 값 이 없 으 면 Entry 요 소 를 새로 만 들 고 해당 하 는 배열 위치 에 놓 습 니 다.소스 코드 먼저 보기:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
// ， table[0]
return putForNullKey(value);
// 1: hash key hash
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// 2: hash hashmap
int i = indexFor(hash, table.length);
// 3: hashmap ， for ， for key key
for (HashMapEntry e = table[i]; e != null; e = e.next) {
Object k;
// hash key ， ，
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 4: hash ， key key ， Entry hashmap
addEntry(hash, key, value, i);
return null;
} 상기 네 가지 절 차 는 hash 충돌 처리 방법 을 나타 내지 않 았 습 니 다. hash 충돌 은 key 값 이 다 르 지만 계산 한 hash 값 은 같 습 니 다.우 리 는 이어서 addEntry 방법 을 보 았 다.
void addEntry(int hash, K key, V value, int bucketIndex) {
// 1： hashmap （ 16*0.75）， ， 。 hash
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 2: Entry hashmap
createEntry(hash, key, value, bucketIndex);
}createEntry 함수 에 들 어가 서 hashmap 가 어떻게 새 요 소 를 배열 에 저장 하 는 지 확인 합 니 다.
void createEntry(int hash, K key, V value, int bucketIndex) {
// 1: ， Entry
HashMapEntry e = table[bucketIndex];
// 2: Entry ， e key,value,hash
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
} 여기 서 hashmap 가 충돌 을 처리 하 는 방식 이 나타 나 지 않 았 습 니 다. 우 리 는 이어서 새로운 Entry 요소 방법 을 보 겠 습 니 다.
HashMapEntry(int h, K k, V v, HashMapEntry n) {
value = v;// value
next = n;// ， next， ， next
key = k;
hash = h;
} 드디어 hashmap 에서 충돌 을 처리 하 는 코드 를 찾 았 습 니 다. hash 충돌 이 발생 하면 새 요 소 를 링크 머리 에 두 고 next 를 원래 링크 의 요 소 를 가리 킵 니 다.예 를 들 어 첫 번 째 키 값 은 A 에 들 어 와 서 key 의 hash 를 계산 하여 얻 은 index = 2 를 기록 합 니 다: Entry [2] = A.잠시 후에 또 하나의 키 값 이 B 에 들 어 왔 습 니 다. 계산 을 통 해 index 도 2 와 같 습 니 다. HashMap 은 B. next = A, Entry [2] = B 를 다시 들 어 오 면 index 도 2 와 같 습 니 다. 그러면 C. next = B, Entry [2] = C;이렇게 해서 우 리 는 index = 2 의 곳 에서 A, B, C 세 개의 키 값 을 액세스 한 것 을 발 견 했 습 니 다. 그들 은 next 라 는 속성 을 통 해 연결 되 어 있 습 니 다.
3.2 해시 값 에 따라 배열 의 위 치 를 찾 습 니 다.
static int indexFor(int h, int length) {
return h & (length-1);
}비트 에 따라 취 합 하면 모드 모드 모드 나 나머지% 작업 에 해당 하지만 바 이 너 리 를 이용 하 는 작업 이 빠 릅 니 다.여기 서 배열 의 길 이 는 반드시 2 의 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수 지수그리고 확장 후 한 개의 차이 만 있 습 니 다. 즉, 가장 왼쪽 에 있 는 1 이 더 많아 졌 습 니 다. 그러면 h & (length - 1) 를 통과 할 때 h 에 대응 하 는 가장 왼쪽 에 있 는 차이 점 이 0 이면 얻 을 수 있 는 새로운 배열 색인 과 오래된 배열 색인 이 일치 하고 이전에 잘 분 열 된 오래된 배열 의 데이터 위 치 를 크게 줄 일 수 있 습 니 다.
3.3 키 를 빈 값 으로 저장 합 니 다.
key 값 이 비어 있 는 모든 요 소 는 배열 의 머리 table [0] 위치 에 놓 습 니 다. 여 기 는 배열 의 머리 table [0] 위치 에 값 이 있 는 지, 값 이 있 는 지, 같은 key 값 이 있 는 지, 있 으 면 교체 되 는 지, 없 으 면 새 Entry 를 판단 합 니 다. 절 차 는 위 와 유사 합 니 다.
private V putForNullKey(V value) {
for (HashMapEntry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
} 4 get 방법
get 작업 의 소스 코드 는 다음 과 같 습 니 다:
public V get(Object key) {
// key null，
if (key == null)
return getForNullKey();
// key Entry
Entry entry = getEntry(key);
// Entry value
return null == entry ? null : entry.getValue();
} getEntry () 방법의 실현 을 다시 봅 시다.
final Entry getEntry(Object key) {
if (size == 0) {
return null;
}
// ： key hash
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
// ： hash ， Entry key key ， Entry
for (HashMapEntry 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;
} 5. hashmap 스 트 리밍 방법
1) Iterator 로 옮 겨 다 니 기
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}2) 각 사 이 를 위 한
for (Entry entry : map.entrySet()) {
Object key = entry.getKey();
Object val = entry.getValue();
} 6. LinkedHashMap 원리
링크 드 하 쉬 맵 은 하 쉬 맵 의 하위 클래스 로 실현 구 조 는 하 쉬 맵 과 유사 하 다. 다만 하 쉬 맵 의 링크 는 단 방향 링크 이 고 링크 드 하 쉬 맵 은 양 방향 링크 이 며 하 쉬 맵 을 바탕 으로 순 서 를 매 겨 실현 했다.
6.1 구조 함수
링크 드 HashMap 의 구조 함 수 는 HashMap 보다 정렬 매개 변수 accessOrder 가 많 습 니 다.
/**
* @param initialCapacity ，16
* @param loadFactor 0.75
* @param accessOrder ， true ， false ，
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}6.2 정렬 방식 실현
링크 드 Hash MapEntry 에 recordAccess 방법 을 다시 썼 습 니 다. Hash Map 의 Hash MapEntry 는 빈 방법 입 니 다.이 방법 은 접근 순서에 따라 정렬 할 지 여 부 를 판단 합 니 다. addBefore () 를 호출 하면 현재 방문 한 요 소 를 링크 머리 로 이동 합 니 다.접근 순서에 따라 정렬 하지 않 으 면 링크 의 요 소 는 변 하지 않 습 니 다.요 소 를 삽입 할 때 새로 삽 입 된 요 소 는 HashMap 에서 링크 머리 에 넣 는 것 이기 때 문 입 니 다.
void recordAccess(HashMap m) {
LinkedHashMap lm = (LinkedHashMap)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
/**
*
*/
private void addBefore(LinkedHashMapEntry existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
} 6.3 put 실현
링크 드 HashMap 은 put 방식 을 재 작성 하지 않 았 으 나 addEntry (), createEntry (), 링크 드 HashMapEntry 의 recordAccess () 방법 을 재 작성 했다.HashMap 에서 하나의 요 소 를 넣 을 때 저장 할 요소 의 hash 값 과 key 값 이 현재 링크 에 존재 하면 이전 값 을 교체 한 후 recordAccess () 방법 을 호출 하기 때 문 입 니 다.createEntry () 방법 에서 LinkedHashMap 의 실현 은 다음 과 같 습 니 다. addBefore () 방법 호출 을 추 가 했 습 니 다.현재 새로 삽 입 된 요 소 를 링크 머리 에 놓 습 니 다.
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry old = table[bucketIndex];
LinkedHashMapEntry e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);// ， ，
size++;
} 6.3 get 실현
링크 드 HashMap 에서 요 소 를 가 져 올 때 도 recordAccess 방법 을 사용 하여 방문 요 소 를 링크 머리 로 옮 겼 습 니 다.
public V get(Object key) {
LinkedHashMapEntry e = (LinkedHashMapEntry)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);// ， ，
return e.value;
} 7. LruCache 에서 LinkedHashMap 을 호출 하 는 실현
final LinkedHashMap cache = new LinkedHashMap(100, 0.75f, true); accessOrder 인 자 를 true 로 설정 하면 방문 순서에 따라 정렬 할 수 있 습 니 다.
8. object 류 의 equals () 를 다시 쓰 는 동시에 hashcode () 를 다시 쓰 는 이 유 는 무엇 입 니까?
Object 대상 의 equals (Object) 방법 은 비어 있 지 않 은 인용 값 x 와 y 에 대해 x 와 y 가 같은 대상 을 인용 할 때 만 true 로 돌아 갑 니 다.equals () 방법 이 재 작성 되 었 을 때 hashcode () 방법 을 다시 써 야 합 니 다. hash 협정 성명 이 같은 대상 은 똑 같은 hashcode 를 가 져 야 합 니 다. 다음 과 같 습 니 다.
1) obj 1. equals (obj 2) 가 true 일 때 obj 1. hashCode () = obj 2. hashCode () 는 true 2 여야 합 니 다. obj 1. hashCode () = = = obj 2. hashCode () 가 false 일 때 obj 1. equals (obj 2) 는 false 여야 합 니 다. obj 1. hashCode () = = obj 2. hashCode () 가 true 일 때 obj 1. equals (obj 2) 가 true 가 아 닙 니 다.
equals 를 다시 쓰 지 않 으 면 대상 의 참조 가 같은 메모리 주 소 를 가리 키 는 지 비교 합 니 다. 다시 쓰 면 두 대상 의 value 값 이 같 는 지 비교 하기 위해 서 입 니 다.Hashcode 는 해시 데이터 의 빠 른 액세스 에 사 용 됩 니 다. 예 를 들 어 HashSet \ HashMap \ \ Hashtable 류 를 이용 하여 데 이 터 를 저장 할 때 hashcode 값 이 같 는 지 판단 하고 다 르 면 equals 비 교 를 할 필요 가 없습니다.equals () 를 다시 썼 지만 hashcode () 를 다시 쓰 지 않 았 다 면 new 대상 이 있 을 때 원래 대상. equals (새로운 대상) 가 true 와 같 을 때 이들 의 hashcode 는 같 지 않 아 두 대상 이 서로 다른 상황 을 얻 을 수 있다.저장 할 때 도 두 개의 값 이 같은 대상 이 발생 합 니 다. hashcode 는 다 르 고 두 개 를 저장 하여 헷 갈 립 니 다.그래서 Object 의 equals () 방법 은 다시 쓰 는 동시에 hashcode () 방법 도 다시 써 야 합 니 다.
자신 이 소스 코드 를 한 번 훑 어 본 후에 자신 이 그것 을 다시 써 서 HashMap 의 실현 에 대한 이 해 는 더욱 깊 어 졌 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
자바 의 부동 소수점 표시 방법먼저 십 진법 의 부동 소수점 을 이 진 으로 바 꾸 는 부동 소수점 을 두 부분 으로 나 눕 니 다. 한 숫자 에 대해 플 로 트 와 의 범 위 를 초과 하지 않 고 소수 부분 이 무한 소수 가 아니라면 대응 하 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
