TreeSet 中 floor 方法的解析

在学习算法时，遇到 TreeSet 的 floor() 方法，由于不太了解，故查阅资料并做此笔记。

JDK API 对TreeSet 的解释

参数： e 准备匹配的值 返回值： 方法的返回类型为Element ，它返回此TreeSet中最大的元素，该元素可以等于或小于给定的元素(ele)，否则返回null。

TreeSet 底层代码

发现 floor 方法中调用了 TreeSet 中的一个成员变量m.floorKey(e)方法。

private transient NavigableMap<E,Object> m; public E floor(E e) { return m.floorKey(e); }

而 NavigableMap 是一个接口，但是它有一个实现类是TreeMap：

那么，就应该看看 TreeSet 中该m变量的初始化到底是哪个实现类了：

public TreeSet() { this(new TreeMap<E,Object>()); }

看到默认构造器中为 TreeMap，则可以知道 floorKey(K key) 方法实际调用的是 TreeMap 中的 floorKey(K key) 方法，跟踪进入源码：

public K floorKey(K key) { return keyOrNull(getFloorEntry(key)); }

可以看到返回值调用了 getFloorEntry(key) 方法，跟踪该方法找到源代码：

final Entry<K,V> getFloorEntry(K key) { Entry<K,V> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp > 0) { if (p.right != null) p = p.right; else return p; } else if (cmp < 0) { if (p.left != null) { p = p.left; } else { Entry<K,V> parent = p.parent; Entry<K,V> ch = p; while (parent != null && ch == parent.left) { ch = parent; parent = parent.parent; } return parent; } } else return p; } return null; }

底层原理

通过观察 TreeSet 的底层源码发现，TreeSet 的 floor(e) 方法底层数据结构是红黑树。通过循环比较与根节点值的大小，来找到 set 中小于等于给定元素的最大元素。