Hashmap 소스 코드 분석 (jdk 1.8) 및 면접 문제
24315 단어 자바
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import sun.misc.SharedSecrets;public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
// 16， 2 （ ？ ）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// ， ，
static final int MAXIMUM_CAPACITY = 1 << 30;
//
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// ， ，
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64; static class Node implements Map.Entry {
final int hash;//key 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;
}
} static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}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;
this.threshold = tableSizeFor(initialCapacity);
}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) {
// always check first node
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
/** TreeNode ， ， ， */
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;
} public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**onlyIfAbsent true， */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
/** ， table ， table 0， resize（） */
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/** table null ， */
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/** ， （1） ， ；（2） ， putTreeVal（）；（3） */
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);
// TREEIFY_THRESHOLD-1，
if (binCount >= TREEIFY_THRESHOLD - 1)
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 HashMap ，
++modCount;
/** HashMap ， rehash， */
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// ， ！
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 2 newCap = oldCap << 1
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// initial capacity was placed in threshold
else if (oldThr > 0)
newCap = oldThr;
// zero initial threshold signifies using defaults
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
// bucket buckets
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
//
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
/** ， ？ hash 01010，
*oldCap 10000,01010&10000 = 00000， newCap = oldCap<<1 = 100000,
* newCap-1 hash 11111&01010 = 00000， */
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// bucket
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// +oldCap bucket
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 면접 문제
1. HashMap 의 원리 와 내부 데이터 구조?밑 에 해시 표 (배열 에 링크 추가) 를 사용 하고 링크 가 너무 길 면 (노드 가 8 개 에 달 함) 빨간색 과 검은색 나무 로 전환 하여 O (logn) 시간 복잡 도 에서 찾 을 수 있 습 니 다.2. HashMap 에서 put 방법의 과정 은?(1) 키 에 대해 해시 에 게 테이블 에 있 는 색인 위 치 를 계산 합 니 다.(2) 부 딪 히 지 않 으 면 통 에 넣 기;(3) 부 딪 히 면 링크 의 방식 으로 링크 의 뒤에 놓는다.(4) 링크 의 길이 가 한도 값 8 을 초과 하면 링크 를 빨간색 과 검은색 나무 로 전환한다.(5) 결점 이 이미 존재 한다 면 새 값 으로 낡은 값 을 교체 하고 낡은 값 을 되 돌려 줍 니 다.(6) size > threshold 라면 resize 해 야 합 니 다.3. hash 함수 의 실현?높 은 16 위 는 변 하지 않 고 낮은 16 위 와 높 은 16 위 는 다르다.그리고 (n - 1) & hash 가 아래 표 시 를 받 았 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
