Java基础之TreeMap详解

一、写在前面

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> {

TreeMap

继承了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;

外部指定的比较器。在创建TreeMap对象时可以指定。如果指定了比较器,则TreeMap插入键值对时,按照comparator比较排序。

root

 private transient Entry<K,V> root;

root指代TreeMap底层红黑树的根节点。 root的类型Entry<K,V>就是红黑树节点的类型。

红黑树数据结构的实现就依赖于Entry<K,V>

size

/**
     * The number of entries in the tree
     */
    private transient int size = 0;

表示TreeMap集合中键值对个数。

modCount

/**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

表示TreeMap集合被结构化修改的次数。用于迭代器迭代过程中检测集合是否被结构化修改,若是,则fail-fast。

四、内部类

Entry<K,V>

Entry<K,V>是红黑树节点的代码实现,是实现红黑树数据结构的基础。

    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<K,V> left 代表当前节点的左子节点

Entry<K,V> right 代表当前节点的右子节点

Entry<K,V> parent 代表当前节点的父节点

boolean color 代表当前节点的颜色,默认是黑色,为true

构造器

Entry<K,V>只提供了一个构造器 Entry(K key, V value, Entry<K,V> parent)

即:创建一个红黑树节点,只需要指定其存储的键值信息,以及其父节点引用。不需要指定左孩子和右孩子,以及颜色。

成员方法

提供了getKey()方法返回当前节点的key值。

提供了getValue(),setValue(V 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<? super K> comparator)

 public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

指定比较器的构造器。

指定的比较器用于比较key,且comparator指定了泛型,即比较器比较的元素的类型必须是K或者K的父类类型。

public TreeMap(Map<? extends K, ? extends V> m)

    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

将非TreeMap集合转为TreeMap集合构造器

public TreeMap(SortedMap<K, ? extends V> m)

 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) {
        }
    }

将有序Map集合转为TreeMap集合

六、成员方法

public V get(Object key)

    public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

TreeMap的get方法用于获取指定key的value。如果指定key没有对应的红黑树节点,则返回null,否则返回对应红黑树节点的value。

可以看到get方法实现依赖于getEntry(Object key)方法。

getEntry(Object key)方法是根据指定key找对应的红黑树节点并返回该节点。

final Entry<K,V> getEntry(Object key)

    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;
        }

TreeMap的put方法用于插入一个键值对,

当插入的key在集合中不存在时,则put表示新增键值对,并返回null;

当插入的key在集合中存在时,则put表示覆盖已存在key对应的value,并返回老value。

private void fixAfterInsertion(Entry<K,V> x)

  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;//如果被插入的节点是根节点,则节点颜色改为黑色
    }

fixAfterInsertion方法用于:当TreeMap插入红黑树节点后,导致红黑树不平衡时,TreeMap保持自平衡的自旋和变色操作。

该方法的入参就是插入的红黑树节点。

到此这篇关于Java基础之TreeMap详解的文章就介绍到这了,更多相关Java TreeMap详解内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java HashMap,TreeMap与LinkedHashMap的详解

     java HashMap,TreeMap与LinkedHashMap的详解 今天上午面试的时候 问到了Java,Map相关的事情,我记错了HashMap和TreeMap相关的内容,回来赶紧尝试了几个demo理解下 package Map; import java.util.*; public class HashMaps { public static void main(String[] args) { Map map = new HashMap(); map.put("a", &

  • Java源码解析TreeMap简介

    TreeMap是常用的排序树,本文主要介绍TreeMap中,类的注释中对TreeMap的介绍.代码如下. /** * A Red-Black tree based {@link NavigableMap} implementation. * The map is sorted according to the {@linkplain Comparable natural * ordering} of its keys, or by a {@link Comparator} provided at

  • java TreeMap源码解析详解

    java TreeMap源码解析详解 在介绍TreeMap之前,我们来了解一种数据结构:排序二叉树.相信学过数据结构的同学知道,这种结构的数据存储形式在查找的时候效率非常高. 如图所示,这种数据结构是以二叉树为基础的,所有的左孩子的value值都是小于根结点的value值的,所有右孩子的value值都是大于根结点的.这样做的好处在于:如果需要按照键值查找数据元素,只要比较当前结点的value值即可(小于当前结点value值的,往左走,否则往右走),这种方式,每次可以减少一半的操作,所以效率比较高

  • 浅谈java中的TreeMap 排序与TreeSet 排序

    TreeMap: package com; import java.util.Comparator; import java.util.TreeMap; public class Test5 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub TreeMap<String, String> tree = new TreeMap<String,

  • java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

    java 中HashMap.HashSet.TreeMap.TreeSet判断元素相同的几种方法比较 1.1     HashMap 先来看一下HashMap里面是怎么存放元素的.Map里面存放的每一个元素都是key-value这样的键值对,而且都是通过put方法进行添加的,而且相同的key在Map中只会有一个与之关联的value存在.put方法在Map中的定义如下. V put(K key, V value); 它用来存放key-value这样的一个键值对,返回值是key在Map中存放的旧va

  • 通过java.util.TreeMap源码加强红黑树的理解

    在此之前,我们已经为大家整理了很多关于经典问题红黑树的思路和解决办法.本篇文章,是通过分析java.util.TreeMap源码,让大家通过实例来对红黑树这个问题有更加深入的理解. 本篇将结合JDK1.6的TreeMap源码,来一起探索红-黑树的奥秘.红黑树是解决二叉搜索树的非平衡问题. 当插入(或者删除)一个新节点时,为了使树保持平衡,必须遵循一定的规则,这个规则就是红-黑规则:  1) 每个节点不是红色的就是黑色的  2) 根总是黑色的  3) 如果节点是红色的,则它的子节点必须是黑色的(反

  • Java TreeMap升序|降序排列和按照value进行排序的案例

    TreeMap 升序|降序排列 import java.util.Comparator; import java.util.TreeMap; public class Main { public static void main(String[] args) { TreeMap<Integer,Integer> map1 = new TreeMap<Integer,Integer>(); //默认的TreeMap升序排列 TreeMap<Integer,Integer>

  • java中TreeMap排序的示例代码

    1. 定义TreeMap的排序方法 使用Comparator对象作为参数 需要注意的是:排序方法是针对键的,而不是值的.如果想针对值,需要更麻烦的一些方法(重写一些方法) TreeMap<Screen,Integer> res = new TreeMap<Screen, Integer>(new Comparator<Screen>() { @Override public int compare(Screen screen1, Screen t1) { // 定义Tr

  • Java TreeMap排序算法实例

    本文实例讲述了Java TreeMap排序算法.分享给大家供大家参考,具体如下: TreeMap 和 HashMap 用法大致相同,但实际需求中,我们需要把一些数据进行排序: 以前在项目中,从数据库查询出来的数据放在List中,顺序都还是对的,但放在HashMap中,顺序就完全乱了. 为了处理排序的问题: 1. 对于一些简单的排序,如:数字,英文字母等 TreeMap hm = new TreeMap<String, String>(new Comparator() { public int

  • Java中HashMap和TreeMap的区别深入理解

    首先介绍一下什么是Map.在数组中我们是通过数组下标来对其内容索引的,而在Map中我们通过对象来对对象进行索引,用来索引的对象叫做key,其对应的对象叫做value.这就是我们平时说的键值对. HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的). HashMap 非线程安全 TreeMap 非线程安全 线程安全 在Java里,线程安全一般体

  • 在Java中如何决定使用 HashMap 还是 TreeMap

    HashMap简单总结: 1.HashMap 是链式数组(存储链表的数组)实现查询速度可以,而且能快速的获取key对应的value: 2.查询速度的影响因素有 容量和负载因子,容量大负载因子小查询速度快但浪费空间,反之则相反: 3.数组的index值是(key 关键字, hashcode为key的哈希值, len 数组的大小):hashcode%len的值来确定,如果容量大负载因子小则index相同(index相同也就是指向了同一个桶)的概率小,链表长度小则查询速度快,反之index相同的概率大

  • JAVA使用TreeMap对字符串进行排序

    这篇文章主要介绍了JAVA使用TreeMap对字符串进行排序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目要求: 给出一个字符串:fjdjskgfhbsjkgjnsrgnaHNGKEURHGASLGNw5y74236720573. 要求: 化成字符串a(字符的个数)b()c()... 区分大小写 只读取字母 直接上代码: import java.util.Map; import java.util.Set; import java.uti

  • java中treemap和treeset实现红黑树

    TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点. TreeSet 和 TreeMap 的关系 为了让大家了解 TreeMap 和 TreeSet 之间的关系,下面先看 TreeSet 类的部分源代码: public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializab

随机推荐