JAVA数据结构篇--7理解TreeMap
袁志专
前言：java 中提供了无序元素存放的HashMap ，也提供了有序的LinkedHashMap，如果想要实现自定义顺序的存放和读取呢，比较按照时间的前后，年龄的大小，有序的存入，这样当进行遍历时可以保证想要的顺序，java 中提供TreeMap 来对此进行实现；
1 使用：
// 声明 TreeMap 并自定义比较器
Map<Integer, Object> map = new TreeMap<Integer, Object>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 -o2;
}
});
// 放入元素
map.put(10,"10");
map.put(9,"9");
map.put(8,"8");
// 获取元素
map.get(8);
// 移除元素
map.remove(8);
// 遍历元素
Iterator<Map.Entry<Integer, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, Object> entry = iterator.next();
System.out.println("key:" + entry.getKey() + " "
+ "Value:" + entry.getValue());
}
2 过程：
2.1 treeMap 的构建：
// 无参构造 比较器为空
public TreeMap() {
comparator = null;
}
// 传入自定义的比较器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
// 传入map
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
// 传入map
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) {
}
}
2.2 存入元素 put：
public V put(K key, V value) {
// 获取根节点，第一次put root 为null,后续存放root 不为null
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
// new entry 并赋值给root 节点
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 {
// 第一次将root 节点 赋值给parent
parent = t;
// 当前key 与 父节点进行比较
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);// 循环结束条件 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++;// 元素个数+1
modCount++;
return null;
}
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;
}
}
可以看到treeMap 中只使用了一种结构，即红黑树；
2.3 获取元素 get:：
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)// 如果自定义了比较器则进入
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 从根节点进行遍历寻找节点
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
// 没有找到节点返回null
return 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;
}
2.4 移除元素 remove：
public V remove(Object key) {
// 找到要移除的节点
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
// 赋值p 节点的value
V oldValue = p.value;
// 移除p 节点
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;// 元素长度-1
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
root = null;
} else { // No children. Use self as phantom replacement and unlink.
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
2.5 遍历元素：
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
// 获取迭代器
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator(getFirstEntry());
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
return p != null && valEquals(p.getValue(), value);
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object value = entry.getValue();
Entry<K,V> p = getEntry(entry.getKey());
if (p != null && valEquals(p.getValue(), value)) {
deleteEntry(p);
return true;
}
return false;
}
public int size() {
return TreeMap.this.size();
}
public void clear() {
TreeMap.this.clear();
}
public Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
}
}
// 获取红黑树最小节点（最左节点）
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
EntryIterator(Entry<K,V> first) {
super(first);// 调用父类
}
public Map.Entry<K,V> next() {
// 赋值下一个节点
return nextEntry();
}
}
// 调用父类--初始化
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
final Entry<K,V> nextEntry() {
// 本次节点赋值给e
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 下次节点获取
next = successor(e);
lastReturned = e;
// 返回本次节点
return e;
}
// 节点获取规则，先获取右子节点的最左子节点，然后获取最左子节点的父节点，然后是右子节点
// 实现效果中序遍历：（遍历出的节点数据是从小到大有序排列的）：
// 对于每个节点来说，先打印左子节点，在打印自己，最后打印右子节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
判断是否还有下一节点：
PrivateEntryIterator hasNext
public final boolean hasNext() {
return next != null;
}
获取下一节点：
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
EntryIterator(Entry<K,V> first) {
super(first);
}
public Map.Entry<K,V> next() {
return nextEntry();
}
}
3 总结：
3.1 TreeMap的数据结构为红黑树，并且可以实现自定义的比较器来对元素的有序存放；如果没有自定义比较器，则会按照默认的比较器完成数据存放；
3.2 TreeMap 在遍历时使用的是中序遍历以此来保证有序性；
类似资料：