Monday, September 21, 2015

Java TreeMap



Java TreeMap 源码解析
  • Comparable一般表示类的自然序,比如定义一个Student类,学号为默认排序
  • Comparator一般表示类在某种场合下的特殊分类,需要定制化排序。比如现在想按照Student类的age来排序
插入SortedMap中的key的类类都必须继承Comparable类(或指定一个comparator),这样才能确定如何比较(通过k1.compareTo(k2)comparator.compare(k1, k2))两个key,否则,在插入时,会报ClassCastException的异常。
此为,SortedMap中key的顺序性应该与equals方法保持一致。也就是说k1.compareTo(k2)comparator.compare(k1, k2)为true时,k1.equals(k2)也应该为true。
NavigableMap是JDK1.6新增的,在SortedMap的基础上,增加了一些“导航方法”(navigation methods)来返回与搜索目标最近的元素。例如下面这些方法:
  • lowerEntry,返回所有比给定Map.Entry小的元素
  • floorEntry,返回所有比给定Map.Entry小或相等的元素
  • ceilingEntry,返回所有比给定Map.Entry大或相等的元素
  • higherEntry,返回所有比给定Map.Entry大的元素

TreeMap是用红黑树作为基础实现的,红黑树是一种二叉搜索树

三叉搜索树在将问题规模减少三分之二时,所需比较操作的次数是两次(二叉搜索树再将问题规模减少一半时,只需要一次比较操作)
我们不能把这两次给忽略了,对于更一般的情况:
n个元素,K叉树搜索树需要的平均比较次数为k*log(n/k)
对于极端情况k=n时,K叉树就转化为了线性表了,复杂度也就是O(n)了,如果用数学角度来解这个问题,相当于:
n为固定值时,k取何值时,k*log(n/k)的取值最小?
k*log(n/k)根据对数的运算规则可以转化为ln(n)*k/ln(k)ln(n)为常数,所以相当于取k/ln(k)的极小值。这个问题对于大一刚学高数的人来说再简单不过了,我们这里直接看结果😊
当k=e时,k/ln(k)取最小值。
自然数e的取值大约为2.718左右,可以看到二叉树基本上就是这样最优解了

红黑树示例红黑树示例

上图是从wiki截来的,需要说明的一点是:
叶子节点为上图中的NIL节点,国内一些教材中没有这个NIL节点,我们在画图时有时也会省略这些NIL节点,但是我们需要明确,当我们说叶子节点时,指的就是这些NIL节点。
红黑树通过下面5条规则,保证了树是平衡的:
  1. 树的节点只有红与黑两种颜色
  2. 根节点为黑色的
  3. 叶子节点为黑色的
  4. 红色节点的字节点必定是黑色的
  5. 从任意一节点出发,到其后继的叶子节点的路径中,黑色节点的数目相同
满足了上面5个条件后,就能够保证:根节点到叶子节点的最长路径不会大于根节点到叶子最短路径的2倍
其实这个很好理解,主要是用了性质4与5,这里简单说下:
假设根节点到叶子节点最短的路径中,黑色节点数目为B,那么根据性质5,根节点到叶子节点的最长路径中,黑色节点数目也是B,最长的情况就是每两个黑色节点中间有个红色节点(也就是红黑相间的情况),所以红色节点最多为B-1个。这样就能证明上面的结论了。
Serialization
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out the Comparator and any hidden stuff
        s.defaultWriteObject();

        // Write out size (number of Mappings)
        s.writeInt(size);

        // Write out keys and values (alternating)
        for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
            Map.Entry<K,V> e = i.next();
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }

    /**
     * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
     * deserialize it).
     */
    private void readObject(final java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in the Comparator and any hidden stuff
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        buildFromSorted(size, null, s, null);

    }
http://stackoverflow.com/questions/14923407/why-red-black-tree-based-implementation-for-java-treemap
Red-Black trees are more general purpose. The do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Java's general policy is to provide the best general purpose data structures.
Java uses quicksort for primitive objects as it is faster than merge sort in the average case . It uses merge sort for sorting objects as merge sort is a stable sorting algorithm.
http://daoluan.net/blog/category/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/

https://github.com/aorzecho/ds/blob/master/src/main/java/org/aorzecho/ds/java/util/TreeMap.java
final Entry<K,V> getIthEntry(Entry<K,V> entry, int i) {
  if (i > size || i<=0)
    throw new IndexOutOfBoundsException("Size is " + size
        + ", requested i=" + i + " out of bounds");
  int r = 1;
  if (entry.left != null)
    r += entry.left.size;
  if (i == r)
    return entry;
  else if (i < r)
    return getIthEntry(entry.left, i);
  else
    return getIthEntry(entry.right, i-r);

}

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
        int size = 1;
   }

https://kerflyn.wordpress.com/2011/05/20/how-treemap-can-save-your-day/
How to find a reservation from a given date
I group a set of reservations in a class that I’ve called Planning. Once instantiated, you can add reservations (method add()) and you can get a reservation at a given date (method getReservationAt()).
There are two steps to get a reservation close to a date.


  1. I first use the method floorEntry(). It gets you the map entry which key is the greatest one less than the given date.
  2. Second, I check if the reservation (that is the value of the entry) contains the given date.
public class Planning {
    public final TreeMap<Date, Reservation> reservations;
    public Planning() {
        reservations = new TreeMap<Date, Reservation>();
    }
    public void add(Reservation reservation) {
        reservations.put(reservation.from, reservation);
    }
    public Reservation getReservationAt(Date date) {
        Entry<Date, Reservation> entry = reservations.floorEntry(date);
        if (entry == null) {
            return null;
        }
        Reservation reservation = entry.getValue();
        if (!reservation.contains(date)) {
            return null;
        }
        return reservation;
    }
}

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts