Map集合之TreeMap

绝地灬酷狼 2023-10-04 12:07 67阅读 0赞

# 写在前面 #

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70][]

## 关于TreeMap的新增删除操作 ##

[通过BST,AVL,234树来理解红黑树\_qfc\_128220的博客-CSDN博客][BST_AVL_234_qfc_128220_-CSDN]

## TreeMap的其他常用操作 ##

package treemap;
    
    import java.util.Collection;
    import java.util.Map;
    import java.util.Set;
    import java.util.TreeMap;
    
    public class TreeMapTest {
        public static void main(String[] args) {
            TreeMap<Country, Integer> tm = new TreeMap<>((o1,o2)->{
                if (o1==null&&o2!=null){
                    return -1;
                }
                if (o2==null&&o1!=null){
                    return 1;
                }
                if (o1==null&&o2==null){
                    return 0;
                }
                int cmp = 0;
                cmp = o1.getGold() - o2.getGold();
                if (cmp==0){
                    cmp = o1.getSilver() - o2.getSilver();
                    if (cmp==0){
                        cmp = o1.getBronze() - o2.getBronze();
                        if (cmp==0){
                            return o1.getName().compareTo(o2.getName());
                        }
                    }
                }
                return cmp;
            });
    
    //        TreeMap<Country, Object> tm = new TreeMap<>();
    
            /**
             * 新增
             */
            tm.put(new Country("China",20,18,2),1);
            tm.put(new Country("Japan",10,28,12),2);
            tm.put(new Country("America",22,20,1),3);
            tm.put(new Country("Russia",20,18,2),4);
            /**
             * 对于TreeMap自然排序，禁止key为null，否则直接抛出NullPointerException
             * 对于TreeMap定制排序，需要看指定的比较器实现，是否支持null
             */
    //        tm.put(null,value);
    //        tm.put(null,value);
    
            /**
             * 查询
             */
            Integer china = tm.get(new Country("China", 20, 18, 2));
            System.out.println(china);
    
            /**
             * 删除
             */
            tm.remove(new Country("Japan",10,28,12));
    
            /**
             * 修改
             */
            tm.put(new Country("America",22,20,1),0);
            System.out.println(tm);
    
            Map.Entry<Country, Integer> firstEntry = tm.firstEntry();
            System.out.println(firstEntry);
    
            Country firstKey = tm.firstKey();
            System.out.println(firstKey);
    
            Map.Entry<Country, Integer> lastEntry = tm.lastEntry();
            System.out.println(lastEntry);
    
            Country lastKey = tm.lastKey();
            System.out.println(lastKey);
    
            Country country1 = tm.lowerKey(new Country("Russia",20,18,2));
            System.out.println(country1);
    
            Map.Entry<Country, Integer> lowerEntry = tm.lowerEntry(new Country("Russia", 20, 18, 2));
            System.out.println(lowerEntry);
    
            Country country2 = tm.higherKey(new Country("Russia", 20, 18, 2));
            System.out.println(country2);
    
            Map.Entry<Country, Integer> higherEntry = tm.higherEntry(new Country("Russia", 20, 18, 2));
            System.out.println(higherEntry);
    
            System.out.println("====================================");
            /**
             * 遍历
             */
            Set<Country> countries = tm.keySet();
            for (Country country : countries){
                System.out.println(country+"~"+tm.get(country));
            }
            System.out.println("====================================");
            Set<Map.Entry<Country, Integer>> entries = tm.entrySet();
            for (Map.Entry entry : entries){
                System.out.println(entry.getKey()+"~"+entry.getValue());
            }
            System.out.println("====================================");
            Collection<Integer> values = tm.values();
            for (Integer v : values){
                System.out.println(v);
            }
            System.out.println("====================================");
            tm.forEach((country, integer) -> System.out.println(country+"~"+integer));
        }
    }

package treemap;
    
    public class Country implements Comparable<Country>{
        private String name;
        private Integer gold;
        private Integer silver;
        private Integer bronze;
    
        public Country(String name, Integer gold, Integer silver, Integer bronze) {
            this.name = name;
            this.gold = gold;
            this.silver = silver;
            this.bronze = bronze;
        }
    
        public String getName() {
            return name;
        }
    
        public Integer getGold() {
            return gold;
        }
    
        public Integer getSilver() {
            return silver;
        }
    
        public Integer getBronze() {
            return bronze;
        }
    
        @Override
        public String toString() {
            return "Country{" +
                    "name='" + name + '\'' +
                    ", gold=" + gold +
                    ", silver=" + silver +
                    ", bronze=" + bronze +
                    '}';
        }
    
    
        @Override
        public int compareTo(Country o) {
            int cmp = this.gold - o.gold;
            int cmp1 = cmp == 0 ? this.silver - o.silver : cmp;
            return cmp1 == 0 ? this.bronze - o.bronze : cmp1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210428223957493.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmY18xMjgyMjA=,size_16,color_FFFFFF,t_70
[BST_AVL_234_qfc_128220_-CSDN]: https://blog.csdn.net/qfc_128220/article/details/116230980?spm=1001.2014.3001.5501