本文共 2901 字，大约阅读时间需要 9 分钟。

TreeMap的内部维护了一个红黑树，从而来确保传入进去的元素都是按顺序保存的，我们查询出来的数据也是排序过得

关于红黑树的基本操作可以参考我之前的一篇文章

先来看添加元素操作

public V put(K key, V value) {        Entry
   
     t = root;        if (t == null) { //如果root节点为null,            compare(key, key); // type (and possibly null) check            root = new Entry<>(key, value, null); //创建一个新的entry作为root节点            size = 1;            modCount++;            return null;        }        int cmp;        Entry
    
      parent;        // split comparator and comparable paths        Comparator
      cpr = comparator;        if (cpr != null) {  //获取到比较器            do {                parent = t;                cmp = cpr.compare(key, t.key); //对比key的大小                if (cmp < 0)    // 如果小于0                    t = t.left;  // 从左子树中查询                else if (cmp > 0)                    t = t.right; //从右子树中查询                else                    return t.setValue(value); //如果key相同，直接替换掉            } while (t != null);        }        else { // 如果没有设置比较器，直接使用key值原生的比较方法，同样也是进行比较，找到相同的值，更新，找不到的话，可以定位到父节点            if (key == null)                throw new NullPointerException();            @SuppressWarnings("unchecked")                Comparable
      k = (Comparable
     ) 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
     
       e = new Entry<>(key, value, parent); //基于上面查找到的父节点，创建一个新的entry        if (cmp < 0)            parent.left = e;// 如果比父节点小，放在左节点        else            parent.right = e; // 入股偶比父节点大，放在父节点的右子节点        fixAfterInsertion(e); // 调整红黑二叉树平衡        size++; // size值加1        modCount++;        return null;    }
     
    
   

根据key进行查询某个元素

final Entry
   
     getEntry(Object key) {        // Offload comparator-based version for sake of performance        if (comparator != null)            return getEntryUsingComparator(key); //使用比较器，遍历红黑二叉树，找到元素        if (key == null)            throw new NullPointerException(); // key为null 抛出NPE异常        @SuppressWarnings("unchecked")            Comparable
     k = (Comparable
    ) key; // 如果没有比较器        Entry
    
      p = root;         while (p != null) { //从root开始遍历，直到找到相同的元素            int cmp = k.compareTo(p.key);            if (cmp < 0)                p = p.left;            else if (cmp > 0)                p = p.right;            else                return p;        }        return null;    }
    
   

移除某个元素

public V remove(Object key) {        Entry
   
     p = getEntry(key); //获取到key对应的元素        if (p == null)            return null;        V oldValue = p.value; // 获取到元素对应的value        deleteEntry(p); // 删除指定元素，并调整红黑树平衡        return oldValue;    }
   

以上就是关于TreeMap的源码分析，如果之前对红黑树有过了解的话，看TreeMap会比较简单

转载地址：http://nlvti.baihongyu.com/