提出需求:
需要对一组数据进行排序,并剔除重复数据。
解决思路:
①:首先你可能会想到使用 List + Comparator
,当然这是一种很普遍常用的实现方式。
②:然后在排序的同时剔除重复数据,那这时候你肯定会跟已有的节点做比较(循环比较,或者将节点存放在一个map中再通过containsKey()
的方式比较)。
上述解决思路也挺好,那我们能不能换种思路呢?
当然,仔细思考一下,上述思路其实和Java中现有的 TreeSet
还挺像的,那我们何妨不直接拿来使用呢!
public class TreeSetDemo { public static void main(String[] args) { int[] nums = { 3, 2, 5, 1, 7, 0, 1 }; TreeSet<Integer> treeSet = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { treeSet.add(nums[i]); } System.out.println(treeSet); } }
执行结果:这不就是我们想要的嘛!
[0, 1, 2, 4, 6]
从类图中很直观的就可以看出,TreeSet
是一个支持排序(可以自定义实现排序算法,实现 Comparator
)的集合。
TreeSet.java
/** * The backing map. */ private transient NavigableMap<E,Object> m; // 添加元素 // 使用map那很容易的就能联想到不支持重复数据 public boolean add(E e) { return m.put(e, PRESENT)==null; //真正实现在TreeMap中 }
TreeMap.java
public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { // 第一次put操作 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; }
Entry的结构:
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; } }
在Java世界中,已经封装了非常多非常完善的数据结构API,我们在使用的时候可以多思考,不要仅仅局限于只使用最常规的ArrayList
、HashMap
这两个最最常见的API。
感谢阅读,下次再见。ヾ( ̄▽ ̄)ByeBye!