Map--TreeMap

本篇文章是基于JDK1.8分析的，在学习之前，我们先看一下TreeMap的继承链

继承链

我们从继承链上可以看到，相比于HashMap，TreeMap实现了NavigableMap接口，那么这个接口有什么用呢，我们看一下NavigableMap的签名

public interface NavigableMap<K,V> extends SortedMap<K,V> 

我们看到它实现了SortedMap<K,V>，如果仅从名称上来看，它的名称直接表达了它是一个有序的Map集合，事实上，它的有序性是由Comparable接口提供的keys自然序列，也可以是在创建SortedMap实例时，指定一个Compartor。

1、TreeMap的数据结构

TreeMap是基于红黑树结构实现的的一种Map，在前面我们已经详细讲解了，这里只给出红黑树的具体规则，如果不熟悉，建议仔细看一下这两篇文章

集合算法基础--二叉树(上)

集合算法基础--二叉树(下)

红黑树的基本规则

• 每个结点要么是黑色，要么是红色

• 根结点是黑色

• 每个叶子结点(Null)是黑色

• 每个红色结点的两个子结点一定都是黑色，即从每个叶子到根的所有路径不能有连续的红色结点

• 任意结点到叶子结点的路径都包含数量相同的黑结点

红黑树的结点很简单，存储了父结点、左右子结点以及红黑色，元素的key和value值

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;// 其他省略
}

2、成员属性

final Comparator<? super K> comparator:排序规则，如果为null，则按照key的自然顺序进行排序

transient Entry<K,V> root:红黑树的根结点

transient int size:红黑树结点的个数，默认为0

transient int modCount:TreeMap修改次数。

//  排序规则，如果为null，则按照key的自然顺序进行排序
private final Comparator<? super K> comparator;
//红黑树的根结点private transient Entry<K,V> root;
//红黑树结点的个数，默认为0private transient int size = 0;
//TreeMap修改次数。private transient int modCount = 0;

3、构造函数

• TreeMap()

按照自然排序构造一个空的TreeMap集合

public TreeMap() {comparator = null;}

• TreeMap(Comparator<? super K> comparator)

使用给定的构造器构造一个空的TreeMap

 public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}

• TreeMap(Map<? extends K，? extends V> m)

按照给定的map键值对并以key的自然排序构造一个TreeMap

 public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);}

• TreeMap(SortedMap<K，？extends V> m)

使用指定的sortedMap来构造TreeMap，TreeMap中含有sortedMap中的所有键值对

    public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {}}

4、核心方法

4.1、put方法

将指定参数的key和value插入到map中，如果key已经存在，用新的value值替换旧value值，否则返回null，

具体的代码解析

public V put(K key, V value) {Entry<K,V> t = root;//判断根结点if (t == null) {//检查key是否为nullcompare(key, key); // type (and possibly null) check//创建一个根结点root = new Entry<>(key, value, null);//设置树的大小和修改次数均为1size = 1;modCount++;return null;}//记录比较结果int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;//判断comparator，不为null时，用比较器比较if (cpr != null) {//循环比较do {parent = t;//当前结点和key比较cmp = cpr.compare(key, t.key);//<0,走左子树if (cmp < 0)t = t.left;//>0,走右子树else if (cmp > 0)t = t.right;//等于0时，则证明找到，用新值替换旧值，并返回旧值elsereturn t.setValue(value);} while (t != null);}//如果comparator为null,使用key作为比较器进行比较，但是key要实现Comparable接口else {//key为null,抛出异常if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {//循环查找key要插入的位置parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}//找到新结点的父结点后，创建节点对象Entry<K,V> e = new Entry<>(key, value, parent);//判断新结点的key值与父结点的key值，小于0则插入在父结点的左侧if (cmp < 0)parent.left = e;else//否则插入右侧parent.right = e;//插入新的结点后，需要对红黑树调整以保持平衡fixAfterInsertion(e);size++;modCount++;return null;}

4.2、get方法

TreeMap查找操作和二叉查找树是一致的，它的目标是根据key值找到对应的value，若value为null,则返回null

具体代码解析

public V get(Object key) {//调用getEntryz找到键值对Entry<K,V> p = getEntry(key);//找到则返回对应的value，找不到则返回nullreturn (p==null ? null : p.value);}

我们来看一下具体的getEntry方法源码的实现

/**
*getEntry(Object key)方法
*/final Entry<K,V> getEntry(Object key) {// Offload comparator-based version for sake of performance//判断comparator是否为nullif (comparator != null)//不为null时，调用getEntryUsingComparator(key)方法return getEntryUsingComparator(key);//key为null时，则抛出异常if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")//comparator为null时，调用Comparable中的compareTo方法Comparable<? super K> k = (Comparable<? super K>) key;Entry<K,V> p = root;//从红黑树中循环查找并返回，如果不存在，则返回nullwhile (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}return null;}

4.3、remove方法

按照指定的key值删除结点并返回原结点的vale，不存在时，则返回null

public V remove(Object key) {//根据key获取对应结点,getEntry方法在上面已经讲解过了Entry<K,V> p = getEntry(key);//判断结点是否为nullif (p == null)return null;//否则，则删除，并返回旧值V oldValue = p.value;deleteEntry(p);return oldValue;}

参考文献

[1]https://blog.csdn.net/panweiwei1994/article/details/77530819

[2]JDK1.8开发手册

集合文章精选

集合--Map

Map--HashMap

Hashtable源码解析

在公众号回复success领取独家整理的学习资源

看了这篇文章，你是否「博学」了

「扫码关注我」，每天博学一点点。