【JDK1.8】JDK1.8集合源码阅读——TreeMap(一)

一、前言

在前面两篇随笔中,我们提到过,当HashMap的桶过大的时候,会自动将链表转化成红黑树结构,当时一笔带过,因为我们将留在本章中,针对TreeMap进行详细的了解。

二、TreeMap的继承关系

下面先让我们来看一下TreeMap的继承关系,对它有一个大致的了解:

可以看到,除了在之前HashMap里常见的继承类和接口以外,TreeMap实现了NavigableMap接口,而NavigableMap继承自SortedMap,由名字可以看出,只是一个用来实现排序的接口。而这也是为什么TreeMap能够实现排序的原因。由于篇幅关系,将TreeMap的源码解析分为三部分,本章将对接口NavigableMap以及SortedMap进行解析。

三、SortedMap接口源码解析

3.1 SortedMap接口

public interface SortedMap<K,V> extends Map<K,V> {
  //返回用于对键的进行排序的比较器,如果此映射使用其键的自然排序,则为null
  Comparator<? super K> comparator();
  //返回从fromKey(包括)到toKey(不包括)之间的map
  SortedMap<K,V> subMap(K fromKey, K toKey);
  //返回小于toKey的map
  SortedMap<K,V> headMap(K toKey);
  //返回大于或等于fromKey的map
  SortedMap<K,V> tailMap(K fromKey);
  //返回map中第一个(最低)键
  K firstKey();
  //返回map中最后一个(最高)键
  K lastKey();
  Set<K> keySet();
  Collection<V> values();
  Set<Map.Entry<K, V>> entrySet();
}

SortedMap的接口比较简单,没有很特别的地方,唯一比较特别的就是返回Comparator这个接口,可以设想实现排序功能的秘密或许就藏在此处。下面让我们来看一下Comparator和Comparable接口,两者之间有点关联,可以理解为Comparable自带了比较功能,而Comparator是赋予没有比较能力的对象一种比较能力。举个简单例子:面对一道计算题,小明天生口算能力很强,看一眼就能算出来答案。而小李没有这种能力,需要借助计算器才能得出答案。

3.2 Comparable接口

先让我们看下它的代码:

public interface Comparable<T> {
  //如果小于o,返回负数;等于o,返回0;大于o返回正数。
  public int compareTo(T o);
}

对,就是这么简单,里面传入一个泛型T的对象o,对o进行比较。如果小于o,返回负数;等于o,返回0;大于o返回正数。

我们熟悉的很多对象如StringIntegerDouble等都实现了这个接口。可以来看一下简单的例子:

public class Item implements Comparable<Item> {
  private String name;
  private int price;
  
  public Item(String name, int price) {
    this.name = name;
    this.price = price;
  }
  
  public int getPrice() {
    return price;
  }
  
  public String getName() {
    return name;
  }
  
  @Override
  public String toString() {
    return "Item{" +
      "name='" + name + '\'' +
      ", price=" + price +
      '}';
  }
  
  @Override
  public int compareTo(Item o) {
    if (this.name.compareTo(o.name) < 0) {
      return -1;
    } else if (this.name.compareTo(o.name) > 0) {
      return 1;
    } else {
      return 0;
    }
  }
  
  public static void main(String[] args) {
    List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400));
    System.out.println("before:" + items);
    Collections.sort(items);
    System.out.println("after:" + items);
  }
}

上述main函数的输出:

before:[Item{name='banana', price=200}, Item{name='apple', price=400}]
after:[Item{name='apple', price=400}, Item{name='banana', price=200}]

上面的例子中,我们自己实现了Comparable接口,比较了Item的name属性,然后通过Collections.sort对它进行了排序(值得注意的是:没有实现Comparable接口的对象不能使用该方法)。但是,如果我不想用name属性对它进行排序,想对price进行排序呢,或者先对name排序,相同的话在对price进行排序呢,用这个不就没法实现了吗。这就需要提到了下面的Comparator接口

3.3 Comparator接口

照例先来看一下代码:

@FunctionalInterface
public interface Comparator<T> {
  // 核心方法,用来比较两个对象,如果o1小于o2,返回负数;等于o2,返回0;大于o2返回正数
  int compare(T o1, T o2);
  // 好像很少用到,一般都用对象自带的equals
  boolean equals(Object obj);
  
  /**-----------下面的都是JDK1.8新增的接口,挑几个放进去----------*/

  //返回反向排序比较器
  default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
  }
  //根据名字知道,先进行compare比较后,再进行一次比较
  default Comparator<T> thenComparing(Comparator<? super T> other) {
    Objects.requireNonNull(other);
    return (Comparator<T> & Serializable) (c1, c2) -> {
      int res = compare(c1, c2);
      return (res != 0) ? res : other.compare(c1, c2);
    };
  }
  //对int类型的key进行比较
  public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
      (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
  }
  //返回正常顺序的比较器
  public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
    return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
  }
}

一起来看一下如何使用,先来看一下JDK1.8以前的用法:

public class SimpleComparator implements Comparator<Item> {
  @Override
  public int compare(Item o1, Item o2) {
    return o1.price - o2.price;
  }
  
  public static void main(String[] args) {
    List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400), new Item("Orange", 100));
    Collections.sort(items, new SimpleComparator());
    System.out.println(items);
  }
}

上述main函数的输出是:

[Item{name='Orange', price=100}, Item{name='banana', price=200}, Item{name='apple', price=400}]

JDK1.8以前的用法要自己手动实现Comparator接口,然后调用Collections.sort(),传入实现类来完成排序,非常麻烦,而JDK1.8则相对来说简单了很多:

public static void main(String[] args) {
  List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400), new Item("Orange", 100));
  Collections.sort(items, (Item a, Item b) -> a.price - b.price);
  System.out.println(items);
}

甚至,我们可以不使用Collections.sort:

public static void main(String[] args) {
  List<Item> items = Arrays.asList(new Item("banana", 100), new Item("Orange", 100), new Item("apple", 400), new Item("Orange", 50));
  items.sort((Item a, Item b) -> a.price - b.price);
  System.out.println(items);
  //使用上面的thenComparing
  items.sort(Comparator.comparing(Item::getName).thenComparing(Comparator.comparingInt(Item::getPrice)));
  System.out.println("after using thenComparing: " + items); 
}

上述main函数的输出:

 [Item{name='orange', price=50}, Item{name='banana', price=100}, Item{name='orange', price=100}, Item{name='apple', price=400}]
 after using thenComparing: [Item{name='apple', price=400}, Item{name='banana', price=100}, Item{name='orange', price=50}, Item{name='orange', price=100}]

四、NavigableMap接口源码解析

public interface NavigableMap<K,V> extends SortedMap<K,V> {
  //返回键小于且最接近Key(不包含等于)的键值对,没有返回null
  Map.Entry<K,V> lowerEntry(K key);
  //返回小于且最接近(不包含等于)Key的键,没有返回null
  K lowerKey(K key);
  //返回键小于且最接近(包含等于)Key的键值对,没有返回null
  Map.Entry<K,V> floorEntry(K key);
  //返回小于且最接近(包含等于)Key的键,没有返回null
  K floorKey(K key);
  //返回大于且最接近(包含等于)给定key的键值对,没有返回null
  Map.Entry<K,V> ceilingEntry(K key);
  //同上
  K ceilingKey(K key);
  //返回大于且最接近(不包含等于)给定key的键值对
  Map.Entry<K,V> higherEntry(K key);
  //同上
  K higherKey(K key);
  //返回第一个Entry
  Map.Entry<K,V> firstEntry();
  //返回最后一个Entry
  Map.Entry<K,V> lastEntry();
  //移除并返回第一个Entry
  Map.Entry<K,V> pollFirstEntry();
  //同上
  Map.Entry<K,V> pollLastEntry();
  //返回map中包含的映射关系的逆序视图
  NavigableMap<K,V> descendingMap();
  //返回map中包含的键的NavigableSet视图。 set的迭代器按key的升序
  NavigableSet<K> navigableKeySet();
  //逆序
  NavigableSet<K> descendingKeySet();
  //根据fromKey和toKey来返回子map,两个boolean参数用于是否包含该key
  NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);
  //返回小于(或等于,根据inclusive)toKey的map
  NavigableMap<K,V> headMap(K toKey, boolean inclusive);
  //返回大于(或等于,根据inclusive)fromKey的map
  NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
  SortedMap<K,V> subMap(K fromKey, K toKey);
  SortedMap<K,V> headMap(K toKey);
  SortedMap<K,V> tailMap(K fromKey);
}

注意:上述返回的map与原map是相互影响的。

五、总结

本章分析了TreeMap的继承关系,给后面分析TreeMap作为铺垫。SortedMap和NavigableMap的接口中,包含了大量的返回Map的方法,这也是作为排序Map的一大特点吧。最后谢谢各位园友观看,与大家共同进步!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(45) 神奇的堆 / 计算机程序的思维逻辑

前面几节介绍了Java中的基本容器类,每个容器类背后都有一种数据结构,ArrayList是动态数组,LinkedList是链表,HashMap/HashSet是...

2189
来自专栏来自地球男人的部落格

[LeetCode] 347. Top K Frequent Elements

【原题】 Given a non-empty array of integers, return the k most frequent elements...

2857
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

764
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——TreeMap(一)

1453
来自专栏有趣的Python

4-Java常用工具类-集合

问题: 存储20名学生的学生信息。20是不变的,就是这么多。 问题: 存储商品信息。不知道自己要买多少商品。

1802
来自专栏拭心的安卓进阶之路

Java 集合源码解析(1):Iterator

Java, Android 开发也有段时间了,当初为了早点学 Android,Java 匆匆了解个大概就结束了,基础不够扎实。 虽然集合框架经常用,但是一直...

2245
来自专栏mySoul

​单链表 C++

1012
来自专栏Java帮帮-微信公众号-技术文章全总结

第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点,如是否可重复,是否有序仅作用在键上,如HashMap集合的键不得重复,值可以重复。

1983
来自专栏函数式编程语言及工具

Scalaz(24)- 泛函数据结构: Tree-数据游览及维护

上节我们讨论了Zipper-串形不可变集合(immutable sequential collection)游标,在串形集合中左右游走及元素维护操作。这篇我...

1956
来自专栏Python爱好者

Java基础笔记17

1456

扫码关注云+社区

领取腾讯云代金券