Java 진보(一)---HashMap
HashMap 은 jdk 1.2 에 가입 하여 다 중 스 레 드 동기 화 를 고려 하지 않 았 습 니 다.단일 스 레 드 성능 은 HashTable Note 보다 좋 습 니 다.같은 종류의 HashMap 이라도 서로 다른 jdk 버 전에 서 차이 가 있 고 심지어 매우 클 수 있 습 니 다.따라서 원본 코드 를 붙 일 때 대응 하 는 jdk 버 전 을 첨부 해 야 합 니 다.
일단 1,6 의 HashMap.
1.6 의 HashMap 코드 가 비교적 적어 서 읽 기 쉽다.
HashMap 에 저 장 된 대상 은 Entry 이 고 HashMap 은 사실상 Entry 배열 입 니 다.배열 의 크기 는 2 의 n 제곱 이 고 기본 값 은 16 이 며 대응 속성 은 capacity 입 니 다.
HashMap 에는 4 개의 구조 함수 가 있 지만 최종 호출 된 것 은 모두 HashMap(int initial Capacity,float loadFactor)입 니 다.구조 HashMap 은 두 개의 매개 변수 용량 인 initialCapacity 와 부하 인자 loadFactor 가 필요 합 니 다.
initial Capacity 라 는 매개 변 수 는 HashMap 에 몇 개의 요 소 를 담 을 수 있 는 지 를 말 하 는 것 이 아니 라 HashMap 에 몇 개의 통 이 있 는 지,즉 Entry 배열 의 크기 입 니 다.그것 은 항상 당신 이 설정 한 값 과 같 지 않 고 initial Capacity 보다 큰 2 의 n 제곱 을 취 할 것 입 니 다.예 를 들 어 initial Capacity=9 를 설정 하면 실제 통 의 크기 는 16 입 니 다.통 크기 는 변 함 없 는 것 이 아니 라 HashMap 의 총 요소 의 증가 에 따라 확 대 됩 니 다.확장 용량 은 배로 증가 할 것 이다.예 를 들 어 현재 capacity 는 16 이 고 다음 조정 은 32 이 며 다시 증가 하면 64 이다.
HashMap 은 구조 시 확 장 된 한도 값 shreshold=initialCapacity*loadFactor 를 설정 합 니 다.
다음은 자주 사용 하 는 put 방법 입 니 다.1.6 소스 코드
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry 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;
}
먼저 key 가 null 인지 여부 에 따라 분기 가 다 릅 니 다.key==null 의 경우 하나의 방법 으로 putForNullKey()를 단독으로 갑 니 다.null 이 key 는 table[0]에 고정 되 어 있 습 니 다.
hash 값 은 key.hashCode 가 hash 함수 에 들 어가 계산 한 값 과 같 습 니 다.이 hash()함 수 는 몇 번 의 자리 이동 과 취 또는 연산 을 했 습 니 다.index For()는 hash 값 으로 table 의 길 이 를 모델 링 하여 나중에 배열 에 놓 을 위 치 를 얻 는 것 과 같 습 니 다.여 기 는 위치 와 속도 가%보다 훨씬 빠르다.
put 방법 은 반환 값 이 있 습 니 다.put 시 세 가지 상황 이 있 습 니 다.1.i 위치 에 요소 가 없 으 면 for 순환 이 들 어가 지 않 고 Entry 노드 를 새로 만 들 고 i 위치 에 놓 고 null 로 돌아 갑 니 다.상황 2.i 위치 에 요소 가 있 고 한 줄 의 요소,링크 저장 방식 이지 만 옮 겨 다 니 면서 똑 같은 key 가 없다.그러면 Entry 노드 를 새로 만 들 고 i 의 위치 에 두 었 다.그 전에 이곳 의 링크 는 새로 만 든 노드 뒤에 걸 렸 거나 새로 만 든 노드 는 예전 에 여기에 걸 렸 던 링크 를 가리 키 며 null 로 돌아 가 는 데 2 가지 주의 가 있다.1.새로 만 든 노드.끝 이 아니 라 원래 목록 의 머리 에 걸 려 있 습 니 다.이렇게 하면 끝까지 옮 겨 다 니 지 않도록 할 수 있다.2.키 가 같다 고 판단 하 는 방법 은?e.hash==hash&&(k=e.key)==key||key.equals(k)key 의 hash 값 이 같 고 key 의 equals 방법 이 같 거나 근본적으로 key(같은 참조)입 니 다.이것 도 하나의 대상 이 Key 를 하려 면 hashCode()와 equals()방법 을 다시 불 러 와 야 하 는 이유 입 니 다.상황 3.사실 앞의 두 가지 상황 은 모두 새로운 key 로 가입 되 었 는데 1 은 hash 충돌 이 발생 하지 않 았 고 2 는 충돌 이 발생 했다.상황 3 은 키 가 이미 존재 하 는 경우 입 니 다.다시 put 새 값 은 어떻게 됩 니까?먼저 새 값 이 오래된 값 을 덮어 쓰 고 오래된 값 을 되 돌려 줍 니 다.그래서 put 반환 값 을 통 해 put 가 새로운 key 인지 오래된 key 인지 판단 할 수 있 습 니 다.
get 방법 1.6 소스 코드
public V get(Object key) {
// key==null 。
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
키==null 은 따로 방법 을 찾 습 니 다.다른 것 은 hash 값 을 계산 하고 해당 하 는 통 을 찾 아 옮 겨 다 닙 니 다.같은 키 가 있 으 면 대응 하 는 value 를 되 돌려 줍 니 다.그렇지 않 으 면 null 을 되 돌려 줍 니 다.
size 속성,HashMap 에 얼마나 많은 요소(Entry)가 있 는 지 기록 합 니 다.Entry 를 추가 할 때마다 size 는 1 을 증가 하 는 동시에 한도 값 shreshold 와 비교 합 니 다.size>=shreshold 일 때 resize 방법 으로 jdk 1.6 에서 노드 를 확대 하 는 방법 입 니 다.
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
jdk 1.6 resize 방법
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// transfer hash ，
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
매번 용량 이 이전의 2 배로 확 대 될 때마다 new 의 새로운 배열 을 먼저 한 다음 에 transfer 방법 을 통 해 이전의 요 소 를 새로운 배열 로 다시 hash 하고 한도 값 은 새로운 용량 에 따라 다시 계산한다.
remove()
삭제 하 는 방법 도 있 습 니 다.삭제 에 도 반환 값 이 있 습 니 다.null 로 돌아 가면 삭제 할 key 가 존재 하지 않 습 니 다.null 이 아니면 요 소 를 삭제 하 는 value 입 니 다.
1.6 의 HashMap 은 배열+링크 의 형식 을 사용 하고 해시 값 을 모델 로 한 후에 배열 의 색인 이기 때문에 충돌 하지 않 을 때 시간 복잡 도 는 1 이다.충돌 할 때 여러 노드 가 하나씩 하나의 체인 구 조 를 형성 하고 나중에 체인 표 에 삽입 된다.
=======jdk 버 전 분할 선======================================
jdk 1.6 의 HashMap 소스 코드 아래 jdk 1.8 의 HashMap 에 대해 이야기 합 니 다.이 버 전의 HashMap 변 화 는 비교적 큽 니 다.전체 원본 파일 크기 는 1000 줄 에서 2300 줄(모든 주석 빈 줄 포함)로 증가 하 였 습 니 다.첫 번 째 변 화 는 이전의 Entry 류 를 Node 로 바 꾸 는 것 이다.jdk 1.8 에서 많은 내부 클래스 가 Entry 에서 Node 로 바 뀌 었 다)Entry 와 Node 는 모두 Map.Entry 인 터 페 이 스 를 실현 했다.이 인 터 페 이 스 는 4 개의 static 방법 이 있어 서 실현 할 필요 가 없다.Note:자바 8 에서 인터페이스 에서 정적 방법 을 지원 합 니 다.이 정적 방법 은 body 가 필요 합 니 다.클래스 는 인 터 페 이 스 를 실현 하 는 방법 일 때 정적 방법 을 실현 할 필요 가 없습니다.
1.8.HashMap 에 대한 또 다른 변 화 는 원래 의 링크 구 조 를 길이 가 8 을 넘 으 면 빨 간 검 은 나무 구조 로 바 꾸 는 것 이다.그래서 1.8 의 HashMap 은 배열+링크+빨 간 검 은 나무 입 니 다.
HashMap 은 4 개의 구조 함수 가 있 는데 가장 중요 한 것 은 HashMap(int,float)이다.1.8 에 서 는 구조 할 때 new table 배열 이 아니 라 첫 번 째 put 데이터 로 지연 된다.구조 함 수 는 loadFactor 와 threshold 인자 만 설정 합 니 다.threshold 의 계산 방법 은 이전 과 다 릅 니 다.tableSizeFor 방법 을 호출 했 습 니 다.이 방법 은 initialCapacity 의 2 보다 큰 n 차 멱 jdk 1.8 tableSizeFor 로 되 돌아 갑 니 다.
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
hash 값 은 여전히 key 의 hash Code 에 대해 재 hash 를 진행 하지만 hash 함수 와 1.6 은 또 다 릅 니 다.
put 방법 1.8 의 put 는 실제 적 으로 puutVal 방법 을 호출 하 는 것 입 니 다.이 방법 은 only IfAbsent 인 자 를 하나 더 만 들 었 습 니 다.앞으로 puut 에 있 을 때 이 key 가 존재 한다 면 덮어 쓰 지 않 는 것 을 고려 하 는 것 같 습 니 다.현재 이 매개 변 수 는 false 입 니 다.put 할 때마다 key 가 존재 하면 새 값 으로 오래된 값 을 바 꿉 니 다.1.8 소스 코드,put 와 putVal
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); // 1
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 2
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 3
else { // 4
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
1.8 의 코드 는 1.6 의 보기 보다 더욱 치밀 하 게 쓰 여 있어 서 이해 하기 쉽 지 않다.일부 변수 할당,방법 호출 과 비 교 는 모두 한 문장 에 쓰 여 있다.효율 성 을 높이 기 위해 서인 지 읽 기 체험 이 떨어진다.
새 버 전의 resize 방법 은 인자 가 필요 없 는 자체 적응 방법 입 니 다.이 resize 는 이전 보다 복잡 하고 table 을 초기 화 하 는 작업 이 있 습 니 다.키=null 에 대한 특수 함수 처리 가 없습니다.put 는 몇 가지 상황 이 있 습 니 다.1.table 이 이 자리 에 노드 가 없 으 면 new 의 새로운 노드 를 걸 면 null 로 돌아 갑 니 다.상황 2,table[i]는 위 에 노드 가 있 고 첫 번 째 노드 의 key 는 바로 이번 번 째 put 의 key 입 니 다.그러면 새 값 으로 오래된 값 을 덮어 쓰 고 오래된 값 을 되 돌려 줍 니 다.다시 뒤로 판단 하면 이 위치 에 있 는 연결 노드 를 옮 겨 다 니 는 것 이다.1.8 의 이런 노드 는 두 가지 조직 방식 이 있 는데 8 개가 안 되 는 것 에 대해 체인 테이블 의 구조 이다.8 개 이상 의 것 은 붉 은 검 은 나무의 구조 로 바 뀌 어 저장 된다.상황 3.뒤쪽 노드 는 나무의 구조 입 니 다.그러면 TreeNode 의 put 방법 을 호출 하여 key 가 존재 하면 교체 하고 이전 값 으로 돌아 가 며 존재 하지 않 으 면 새 노드 로 null 로 돌아 갑 니 다.상황 4.뒤의 노드 는 링크 의 구조 이다.이 노드 를 옮 겨 다 니 며 같은 key 가 존재 합 니 다.새 값 은 오래된 값 을 덮어 쓰 고 오래된 값 을 되 돌려 줍 니 다.옮 겨 다 니 고 key 가 존재 하지 않 으 면 새 노드 를 만 듭 니 다.이 노드 는 링크 끝 에 걸 려 있 고 null 로 돌아 갑 니 다.1.6 은 체인 헤드 에 걸 려 있 었 던 것 으로 기억 합 니 다.그 다음 에 링크 의 길이 가 한도 값 8 보다 크 면 이 링크 구 조 를 나무의 구조 로 바 꿔 야 한다.1.8 의 HashMap 에 내부 클래스 TreeNode 가 추가 되 었 는데 이것 은 LinkHashMap.Entry 를 계승 한 것 이다.한 통 안의 원소 수량 이 한도 값 보다 많 을 때(TREEIFYTHRESHOLD=8),한도 값 보다 작은 트 리 로 전 환 됩 니 다(UNTREEIFYTHRESHOLD=6)는 또 링크 구조 로 전환 된다.이것 은 대량의 hash 충돌 상황 에 대해 최적화 되 었 고 hash 충돌 시간 에 비해 TreeNode 구 조 를 사용 하지 않 습 니 다.
get()방법 1.8 소스 코드
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.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;
}
get 방법,key 를 찾 으 면 value 로 돌아 갑 니 다.그렇지 않 으 면 null 로 돌아 갑 니 다.노드 구조 가 빨 간 검 은 나무 인지,링크 가 사용 하지 않 는 방식 으로 옮 겨 다 닐 것 이다.
참고:put 의 함수 이름 은 putVal 이 고 get 의 함수 이름 은 getNode 입 니 다.여기 가 일치 하지 않 아 좀 이상 합 니 다.
remove()삭제 방법,key 를 찾 으 면 삭 제 된 value 를 되 돌려 줍 니 다.그렇지 않 으 면 null 로 돌아 갑 니 다.node 의 구조 에 따라 트 리 를 옮 겨 다 닐 지,링크 로 옮 겨 다 닐 지 선택 하 십시오.
1.8 에 추 가 된 코드 는 주로 붉 은 검 은 나 무 를 도 입 했 기 때문이다.많은 곳 에서 두 가지 상황 을 고려 해 야 한다.HashMap 충돌 이 그렇게 잦 았 나 요?만약 충돌 이 정말 이렇게 심 하 다 면,이것 도 일종 의 최적화 라 고 할 수 있다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
