TreeMap是如何实现去重和排序的

落日映苍穹つ 2023-02-27 13:58 135阅读 0赞

TreeMap实现了SortedMap接口，它是一个key有序的Map类。

## TreeMap的默认排序规则 ##

TreeMap并不是根据插入的顺序来排序，而是根据key元素的 compareTo 方法来排序。

测试代码：

Map<Integer, Object> map = new TreeMap<>();
    map.put(5, new Object());
    map.put(10, new Object());
    map.put(8, new Object());
    map.put(12, new Object());
    System.out.println(map);

输出结果

> \{5=java.lang.Object@49097b5d, 8=java.lang.Object@6e2c634b, 10=java.lang.Object@37a71e93, 12=java.lang.Object@7e6cbb7a\}

## 自定义排序 ##

我们还可以向TreeMap的构造方法中传入 `Comparator` 对象来覆盖元素的默认排序规则。即：当TreeMap 创建时如果有传入 `Comparator` ，优先按照 `Comparator` 的规则来排序，如果没有传入 `Comparator` ，就按照key的 `compareTo` 方法来排序。

测试代码：

Map<Integer, Object> map = new TreeMap<>(new Comparator<Integer>() { 
        @Override
        public int compare(Integer o1, Integer o2) { 
            return o2 - o1;
        }
    });
    map.put(5, new Object());
    map.put(10, new Object());
    map.put(8, new Object());
    map.put(12, new Object());
    System.out.println(map);

输出结果

> \{12=java.lang.Object@49097b5d, 10=java.lang.Object@6e2c634b, 8=java.lang.Object@37a71e93, 5=java.lang.Object@7e6cbb7a\}

## 判断重复的依据 ##

在HashMap中判断key是否重复的依据是根据hash值和equals比较，但是在TreeMap中，判断key是否重复的依据是根据 `comparaTo` 是否为0，如果为0，TreeMap 就认为key是重复的。

测试代码：

public class Demo { 
        public static void main(String[] args) { 
            Map<User, Object> map = new TreeMap<>();
            map.put(new User("小红"), new Object());
            map.put(new User("小明"), new Object());
            map.put(new User("小王"), new Object());
            System.out.println(map);
        }
    }
    
    class User implements Comparable<User> { 
        private String username;
    
        public User(String username) { 
            this.username = username;
        }
    
        public String getUsername() { 
            return username;
        }
    
        public void setUsername(String username) { 
            this.username = username;
        }
    
        @Override
        public boolean equals(Object o) { 
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            User user = (User) o;
            return Objects.equals(username, user.username);
        }
    
        @Override
        public int hashCode() { 
            return Objects.hash(username);
        }
    
        /**
        * 这里让compareTo的返回结果永远为0
        * /
        @Override
        public int compareTo(User o) { 
            return 0;
        }
    
        @Override
        public String toString() { 
            return "User{" +
                    "username='" + username + '\'' +
                    '}';
        }
    }

输出结果

> \{User\{username=‘小红’\}=java.lang.Object@49097b5d\}

## 一个坑点 ##

值得注意的是，当我们创建 TreeMap 的时候没有传入 Comparator ，而且存入 TreeMap 中的元素没有实现 Comparable 接口，当调用 put 方法的时候，就会抛出异常 `ClassCastException` 。

## 从源码上看TreeMap去重和排序的实现原理 ##

TreeMap 底层是一棵红黑树，红黑树是由排序二叉树扩展而来的，key的去重与红黑树的特性无关，所以我们这里就只考虑排序二叉树的特性：

*  对于任意一个节点，它的左子树上所有节点的值都小于该节点
 *  右子树上所有节点的值大于该节点
 *  它的左右子树也是排序二叉树

### 在添加时，key去重的原理 ###

TreeMap的put方法源代码：  
![在这里插入图片描述][format_png]  
从源码上可以看出，每次要向TreeMap中添加新的键值对时，会执行以下步骤：

1.  定义一个指针先指向二叉树的向根节点
2.  将传入的key与指针节点的key对比，如果传入的key大于指针节点的key，就将指针移动到当前节点的右子树，如果传入的key小于指针节点的key，就将指针移动到当前节点的左子树。
3.  循环执行上一步，直到传入的key值与指针节点的key值相等，就将value值替换掉，或者指针已经移动到底了，就将传入的key和value作为新的节点，添加到树的底部
4.  为了维护红黑树的平衡，将一些节点翻转，代码细节在 `fixAfterInsertion` 方法中，这里面的代码与插入去重无关，就不再展开来说了。

### 在遍历的时候时如何有序的 ###

由于TreeMap在存入节点的时候已经是按照排序二叉树的特性来插入了，所以在遍历二叉树的时候只要用中序遍历，就可以按照从小到大的顺序读取每一个节点了。  
以下是我找到的迭代器中序遍历的相关代码

![在这里插入图片描述][format_png 1]

[format_png]: /images/20230209/19a381977a12457d8002398ea57ba367.png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMTM0MTk0Ny8xNTk1MDUzNDUxOTQ2LTBhOWJjYmM0LWRlNDktNDYzYy04MjRkLTg3MjEwNzUzOTY2Yi5wbmc?x-oss-process=image/format,png