JDK 7 과 JDK 8 의 hashmap 실현 이 다 릅 니 다.
JDK 7 에서 hashmap 은 통 (배열) 과 링크 의 데이터 구 조 를 통 해 이 루어 집 니 다.hash 충돌 이 발생 했 을 때 링크 형식 으로 저장 합 니 다.
Entry[] table //
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); // hash
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;
}
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);// hash
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e); // , entry next entry,
size++;
}
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
JDK 8
JDK 7 에 서 는 hashmap 이 기 존 통 (배열) + 링크 에 검 은 빨 간 나무 사용 을 추가 했다.hash 가 지 정 된 횟수 (TREEIFY THRESHOLD) 를 초과 하면 링크 는 빨 간 검 은 나무 구조 로 전 환 됩 니 다.
static final int TREEIFY_THRESHOLD = 8;
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);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
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;
}
키 에 대해 hash 를 진행 하고 통 에 해당 하 는 위 치 를 찾 습 니 다.이 위치 가 비어 있 으 면 바로 기록 합 니 다.이 위치 에 node 대상 이 존재 한다 면:
빨 간 검 은 나무의 시간 복잡 도 는 O (lgn) 이 고 링크 의 시간 복잡 도 는 O (n) 이다. hash 가 부 딪 히 는 상황 이 비교적 심각 한 상황 에서 빨 간 검 은 나무의 검색 속 도 는 링크 보다 우수 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.