자바 기반 트 리 맵 상세 설명
TreeMap 의 바 텀 데이터 구 조 는 빨간색 과 검은색 나무 이 고 TreeMap 은 집합 요소 의 순 서 를 실현 할 수 있다.
그래서 TreeMap 의 소스 코드 는 실현 되 어야 합 니 다.
1.빨간색 과 검은색 나무의 데이터 구조,그리고 빨간색 과 검은색 나무의 노드 삽입,삭제,그리고 빨간색 과 검은색 나무의 자체 균형 작업,예 를 들 어 왼쪽 회전,오른쪽 회전,그리고 노드 변색 등 이다.
2.빨간색 과 검은색 나 무 는 지 정 된 비교 기 에 따라 정렬 하거나 자 연 스 럽 게 정렬 하 는 것 을 지원 해 야 한다.
정의
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
public interface NavigableMap<K,V> extends SortedMap<K,V> {AbstractMap 을 이 어 받 았 습 니 다.
NavigableMap 을 실 현 했 고 NavigableMap 인 터 페 이 스 는 SortedMap 인 터 페 이 스 를 계승 했다.SortedMap 인 터 페 이 스 는 현 류 가 질서 있 는 집합 임 을 나타 낸다.
Cloneable 을 실 현 했 기 때문에 지원 대상 복제
Serializable 을 실 현 했 기 때문에 지원 대상 의 서열 화
구성원 변수
comparator
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;
root
private transient Entry<K,V> root;레 드 블랙 트 리 데이터 구조의 실현 은 Entry
size
/**
* The number of entries in the tree
*/
private transient int size = 0;modCount
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;내부 클래스
Entry
Entry
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
K key,V value 는 각각 TreeMap 집합 에 저 장 된 키 쌍 의 키 와 값 입 니 다.
Entry
Entry
Entry
boolean color 는 현재 노드 의 색 을 대표 합 니 다.기본 값 은 검은색 이 고 true 입 니 다.
구조 기
Entry
즉,빨간색 과 검은색 트 리 노드 를 만 들 려 면 저 장 된 키 정보 와 부모 노드 참조 만 지정 해 야 합 니 다.왼쪽 아이 와 오른쪽 아이,그리고 색깔 을 지정 할 필요 가 없다.
구성원 방법
getKey()방법 을 제공 하여 현재 노드 의 key 값 을 되 돌려 줍 니 다.
getValue(),setValue(V)를 각각 Value 를 가 져 오고 Value 를 덮어 쓴 후 oldValue 로 되 돌려 줍 니 다.
equals()방법 을 다시 써 서 두 개의 빨 간 검 은 나무 노드 가 같 는 지 판단 하 는 데 사용 합 니 다.논 리 는 두 개의 빨 간 검 은 나무 노드 의 key 는 모두 null 이거 나 equals 결과 true 이 며,value 는 모두 null 이거 나 equals 결 과 는 true 입 니 다.
hashCode()방법 을 다시 썼 습 니 다.
toString()방법 을 다시 썼 습 니 다.
구조 기
public TreeMap()
public TreeMap() {
comparator = null;
}이 때 집합 키 값 을 삽입 하 는 key 의 유형 은 Comparable 인 터 페 이 스 를 실현 해 야 합 니 다.즉,자연 정렬 능력 을 제공 해 야 합 니 다.그렇지 않 으 면 잘못된 형식 변환 이상 을 보고 할 수 있 습 니 다.
public TreeMap(Comparator comparator)
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}지정 한 비교 기 는 key 를 비교 하 는 데 사용 되 며,coparator 는 범 형 을 지정 합 니 다.즉,비교 기 가 비교 하 는 요소 의 유형 은 K 나 K 의 부모 유형 이 어야 합 니 다.
public TreeMap(Map m)
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}public TreeMap(SortedMap
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
구성원 방법
public V get(Object key)
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}get 방법 이 getEntry(Object key)에 의존 하 는 방법 을 볼 수 있 습 니 다.
getEntry(Object key)방법 은 지정 한 key 에 따라 해당 하 는 빨 간 검 은 나무 노드 를 찾 아 이 노드 를 되 돌려 주 는 것 입 니 다.
final Entry
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)//
return getEntryUsingComparator(key);//
if (key == null)// ， key null，
throw new NullPointerException();
@SuppressWarnings("unchecked")// ， Key null
Comparable<? super K> k = (Comparable<? super K>) key;// Key Comparable ， ， ， ，
Entry<K,V> p = root;
while (p != null) {// key
int cmp = k.compareTo(p.key);
if (cmp < 0)// key key， key ，
p = p.left;
else if (cmp > 0)// key key， key ，
p = p.right;
else// key key， ，
return p;
}
return null;// Key ， null
}
final Entry<K,V> getEntryUsingComparator(Object key) {// ， ，
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
public V put(K key, V value)
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}삽 입 된 키 가 집합 에 존재 하지 않 을 때 put 는 키 값 을 추가 하고 null 로 되 돌려 줍 니 다.
삽 입 된 key 가 집합 에 존재 할 때 put 는 key 에 대응 하 는 value 를 덮어 쓰 고 오래된 value 를 되 돌려 줍 니 다.
private void fixAfterInsertion(Entry
private void fixAfterInsertion(Entry<K,V> x) {//x
x.color = RED;//
while (x != null && x != root && x.parent.color == RED) {//
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;// ，
}
이 방법의 입 삼 은 삽 입 된 붉 은 검 은 나무 노드 다.
자바 기반 의 트 리 맵 에 대한 자세 한 설명 은 여기까지 입 니 다.더 많은 자바 트 리 맵 에 대한 자세 한 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
