当前位置: 首页 > 工具软件 > Treemap > 使用案例 >

JAVA数据结构篇--7理解TreeMap

袁志专
2023-12-01

前言: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 在遍历时使用的是中序遍历以此来保证有序性;

 类似资料: