Java的TreeMap底层实现原理?( 三 )

输出结果:
热词排行榜:#100 淘宝崩了#90 钉钉崩了#80 阿里云崩了#70 支付宝崩了#60 闲鱼崩了-----------firstEntry: 100=淘宝崩了lastEntry: 60=闲鱼崩了higherEntry: 60=闲鱼崩了lowerEntry: 80=阿里云崩了ceilingEntry: 70=支付宝崩了floorEntry: 70=支付宝崩了其他方法的还包括:
作用方法签名 获取第一个键K firstKey()获取最后一个键K lastKey()获取大于指定键的最小键K higherKey(K key)获取小于指定键的最大键K lowerKey(K key)获取大于等于指定键的最小键K ceilingKey(K key)获取小于等于指定键的最大键K floorKey(K key)获取第一个键值对Map.Entry<K,V> firstEntry()获取最后一个键值对Map.Entry<K,V> lastEntry()获取并删除第一个键值对Map.Entry<K,V> pollFirstEntry()获取并删除最后一个键值对Map.Entry<K,V> pollLastEntry()获取大于指定键的最小键值对Map.Entry<K,V> higherEntry(K key)获取小于指定键的最大键值对Map.Entry<K,V> lowerEntry(K key)获取大于等于指定键的最小键值对Map.Entry<K,V> ceilingEntry(K key)获取小于等于指定键的最大键值对Map.Entry<K,V> floorEntry(K key)获取子map,左闭右开SortedMap<K,V> subMap(K fromKey, K toKey)获取前几个子map , 不包含指定键SortedMap<K,V> headMap(K toKey)获取前几个子mapNavigableMap<K,V> headMap(K toKey, boolean inclusive)获取后几个子map,不包含指定键SortedMap<K,V> tailMap(K fromKey)获取后几个子mapNavigableMap<K,V> tailMap(K fromKey, boolean inclusive)获取其中一段子mapNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey,   boolean toInclusive) put源码再看一下TreeMap的put源码:
/** * put源码入口 */public V put(K key, V value) {    Entry<K,V> t = root;    // 1. 如果根节点为空,则创建根节点    if (t == null) {        compare(key, key);        root = new Entry<>(key, value, null);        size = 1;        modCount++;        return null;    }    int cmp;    Entry<K,V> parent;    // 2. 判断是否传入了排序方式,如果没有则使用默认    Comparator<? super K> cpr = comparator;    if (cpr != null) {        // 3. 如果传入了排序方式,使用do-while循环,找到目标值所在位置,并赋值        do {            parent = t;            cmp = cpr.compare(key, t.key);            // 4. 利用红黑树节点左小右大的特性,进行查找            if (cmp < 0) {                t = t.left;            } else if (cmp > 0) {                t = t.right;            } else {                return t.setValue(value);            }        } while (t != null);    } else {        // 5. TreeMap不允许key为null        if (key == null) {            throw new NullPointerException();        }        // 6. 如果没有传入排序方式,则使用Comparable进行比较        Comparable<? super K> k = (Comparable<? super K>) key;        // 7. 跟上面一致,使用do-while循环,利用红黑树节点左小右大的特性,查找目标值所在位置,并赋值        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);    }    // 8. 如果没有找到,则创建新节点    Entry<K,V> e = new Entry<>(key, value, parent);    if (cmp < 0) {        parent.left = e;    } else {        parent.right = e;    }    // 9. 插入新节点后 , 需要调整红黑树节点位置,保持红黑树的特性    fixAfterInsertion(e);    size++;    modCount++;    return null;}


推荐阅读