HashMap 소스 코드 얕 은 입 심 출 (1)
0. HashMap 구조
HashMap 의 데 이 터 는 어디 에 있 습 니까?데이터 구 조 는 무엇 입 니까?
1. HashMap 의 모든 key - value 는 전역 변수 Node [] table 에 존재 합 니 다.
2. Node 라 는 구 조 는 코드 를 구체 적 으로 본다.
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry,?> e = (Map.Entry,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
hash 는 이 Node 에서 key 가 HashMap 의 hash (K key) 방법 으로 계산 한 것 을 저장 하 는 데 사 용 됩 니 다. key, value 는 말 하지 않 고 next 에 Node 노드 를 저장 합 니 다.HashMap 은 배열 + 링크 형식 으로 저장 되 어 있 습 니 다. 물론 이 Node 의 하위 클래스 와 TreeNode 도 있 습 니 다. 이 건 나중에 말씀 드 리 겠 습 니 다.
해시 값 이 중복 되 었 습 니까?왜 링크 로 저장 합 니까?
이치 에 따 르 면 해시 값 은 중복 되 지 않 습 니 다. 자바 Object 류 의 hashCode 방법 은 유형의 주 소 를 사용 하여 int 로 전환 하여 hash 값 의 유일 성 을 확보 합 니 다. 해시 값 은 중복 되 지 않 지만 저장 할 때 우 리 는 충돌 이 발생 할 수 있 습 니 다. 구체 적 으로 우 리 는 아래 의 소 개 를 볼 수 있 습 니 다. 링크 로 저장 하 는 것 은 충돌 문 제 를 해결 하기 위해 서 입 니 다. 구체 적 으로 1.1.2 절 을 자세히 연구 할 수 있 습 니 다.그 다음 에 1.8 은 링크 뿐만 아니 라 링크 의 길이 가 기본 값 (8) 을 초과 할 때 HashMap 은 이 링크 를 빨간색 과 검은색 나무 로 바 꾸 는데 이것 도 검색 효율 을 높이 기 위해 서 이다.
본문
HashMap 소스 코드 에서 가장 유용 합 니 다. 가장 볼 만 한 것 은 resize () 확장 방법 입 니 다. resize () 방법 을 직접 보 러 가 는 것 은 분명 안개 입 니 다.
그래서 이곳 은 우리 가 가장 자주 사용 하 는 방법 으로 한 걸음 한 걸음 나 누 는 것 이다.
1. get(Object key)
직접 코드
public V get(Object key) {
Node e;
return(e = getNode(hash(key),key)) ==null?null: e.value;
}
get 방법 은 주로 hash 와 getNode 입 니 다.
1.1 hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.1.1 hashCode
모든 대상 이 있 을 수 있 고 hashCode () 방법 이 있어 야 합 니 다. 이것 이 바로 HashMap 의 Key 요구 가 대상 이 어야 하 는 이유 입 니 다 (기본 유형, int, long 등 을 사용 할 수 없습니다).물론 밸 류 도 반드시 대상 이 어야 한 다 는 것 을 요구 하 는데, 왜 나중에 다시 이야기 합 니까?
이것 은 Object 클래스 의 hashCode () 방법 입 니 다.
public native int hashCode();
흔 하지 않 은 키워드 native, native 키 워드 를 사용 하여 이 방법 이 원생 함수 임 을 설명 합 니 다. 즉, 이 방법 은 C / C + + 언어 로 이 루어 진 것 입 니 다.뒤의 것 은 말 하고 싶 지 않 습 니 다. C 시리즈 라면 아래 의 관심 속 에 있 지 않 습 니 다. 우 리 는 소스 Object 로 돌아 가 이 함수 에 대한 묘사 입 니 다.
* Returns a hash code value for the object. This method is
* supported for the benefit of hash tables such as those provided by
* {@link java.util.HashMap}.
* ， （ HashMap）
*
* The general contract of {@code hashCode} is:
*
*
* - Whenever it is invoked on the same object more than once during
* an execution of a Java application, the {@code hashCode} method
* must consistently return the same integer, provided no information
* used in {@code equals} comparisons on the object is modified.
* This integer need not remain consistent from one execution of an
* application to another execution of the same application.
* java ， hashCode() ， ，
* ， . ，
*
- If two objects are equal according to the {@code equals(Object)}
* method, then calling the {@code hashCode} method on each of
* the two objects must produce the same integer result.
* equals() ， hashCode
*
- It is not required that if two objects are unequal
* according to the {@link java.lang.Object#equals(java.lang.Object)}
* method, then calling the {@code hashCode} method on each of the
* two objects must produce distinct integer results. However, the
* programmer should be aware that producing distinct integer results
* for unequal objects may improve the performance of hash tables.
* ，（ ） hashCode ， ，
* hash hash
*
*
* As much as is reasonably practical, the hashCode method defined by
* class {@code Object} does return distinct integers for distinct
* objects. (This is typically implemented by converting the internal
* address of the object into an integer, but this implementation
* technique is not required by the
* Java™ programming language.)
* ，Object hashCode
*（ ， ~）
*
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
1.1.2 >>>
Object. hashCode () 는 이 대상 의 hash 값 을 되 돌려 주 었 습 니 다. 그런데 왜 HashMap 에 hash 방법 이 있 습 니까?
(h = key.hashCode()) ^ (h >>> 16)
이 조작의 고도 요약 은 키 의 해시 값 을 높 은 위치 로 연산 에 참여 시 키 는 것 이다.
왜 높 은 자리 에서 연산 에 참여 해 야 합 니까?
우리 가 계산 한 해시 값 은 int 형 입 니 다. 2 진법 32 비트 기호 가 있 는 int 는 - 2147483648 ~ 2147483648 입 니 다. 부 딪 히 기 어렵 습 니 다.그래서 이 계산 한 해시 값 은 현재 HashMap 의 크기 와 모드 연산 을 통 해 얻 은 나머지 현재 HashMap 의 크기 - 1 과 연산 을 아래 표 로 합 니 다.
p = tab[index = (n - 1) & hash]
이 단락 은 나중에 put 방법 에서 아래 표 시 를 얻 은 문 구 를 사용 하 는 것 입 니 다. 이것 은 우리 가 나중에 다시 이야기 하 겠 습 니 다. 위의 코드 에 따라 다시 보 겠 습 니 다.HashMap 의 기본 크기 는 2 ^ 4 = 16 이 며 32 비트 로 환산 하 는 스타일 은
0000 0000 0000 0000 0000 0000 0001 0000 -->16
0000 0000 0000 0000 0000 0000 0000 1111 -->15
우리 가 15 를 들 고 연산 을 할 때
0000, 0000, 0000, 0000, 0000.
1111 1111 1111 1111 1111 1111 1111 1111 0000 까지.
4 위 이하 의 대상 은 모두 0 으로 표 시 된 대상 에 저장 되 어 있 으 며, 확장 등 을 고려 하지 않 는 다. 이러한 HashMap (1.8 이전) 의 검색 효율 은 링크 와 마찬가지 로 1.8 가 링크 크기 가 8 이 넘 는 링크 를 빨 간 검 은 나무 로 바 꾸 더 라 도 HashMap 의 디자인 취지 가 아니다.
그러나 우리 가 계산 한 해시 값 을 오른쪽으로 16 자리 옮 긴 후에 이 를 취하 거나 현재 크기 16 의 HashMap 에 있어 연산 에 참여 하 는 것 은 0 ~ 3 자리 가 아니 라 0 ~ 3 과 16 ~ 19 명의 공 통 된 계산 결과 로 이 조작 은 우리 의 분 포 를 더욱 고 르 게 한다.
그리고 우리 의 HashMap 의 크기 기본 값 은 16 즉 2 ^ 4 이 고 기호 int 표지 범위 가 있 습 니 다.
참고 로 이것 도 왜 우리 HashMap 의 크기 는 반드시 2 의 멱 차방 이 어야 하 는 지 입 니 다. 왜냐하면 크기 - 1 은 바로 위치 마스크 이기 때 문 입 니 다.
1.2 getNode(int hash,Object key)
이상, 우 리 는 HashMap 에서 해시 값 의 계산 방식 을 알 게 되 었 습 니 다. 아래 에서 우리 가 토론 하고 자 하 는 것 은 hash 값 을 얻 은 후에 구체 적 인 Value 를 어떻게 찾 아야 하 는 지 입 니 다.
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
우 리 는 이미 알 고 있 습 니 다. HashMap, 맨 밑 에 있 는 데이터 구 조 는 Node [] 입 니 다. 사실 이 코드 는 잘 알 고 있 습 니 다. 바로 몇 가지 조건 입 니 다. 유일 하 게 주의해 야 할 것 은 우리 가 구체 적 으로 판단 할 때 먼저 (k = e. key) = key) 를 판단 하 는 것 입 니 다. 그 다음 에 우 리 는 (key! = null & key. equals (k) 를 판단 해 야 합 니 다. = equals 와 의 차 이 는 군말 하지 않 겠 습 니 다.
get 방법 을 통 해 알 수 있 듯 이 만약 에 우리 가 새로 만 든 클래스 를 HashMap 의 key 로 사용 하려 면 우 리 는 이런 종류의 hashCode () 와 equals () 방법 을 정확하게 다시 써 야 한다. 그렇지 않 으 면 최종 결 과 는 우리 가 원 하 는 것 이 아 닐 수도 있다.
이 코드 에는 이전 JDK 버 전에 비해 가장 큰 차이 점 이 있 습 니 다. 바로 빨간색 과 검은색 트 리 를 도입 한 것 입 니 다. 이 코드 도 볼 수 있 습 니 다. 만약 에 우리 가 이 노드 가 TreeNode 라면 우 리 는 TreeNode 의 getTreeNode (hash, key) 방법 으로 우리 가 원 하 는 Node 노드 를 얻 을 것 입 니 다. TreeNode 가 아니라면 우 리 는 링크 를 옮 겨 다 닐 것 입 니 다.
오늘 은 여기까지 ~
나 는 임금 인상 고양이 기술 은 임금 인상 의 전제 이 고, 생활 은 임금 인상 의 의미 기술 은 생활 과 같다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
