Java--TreeMap的使用和底层实现

  TreeMap是红黑二叉树的典型实现。我们打开TreeMap的源码，发现里面有一行核心代码：

private transient Entry<K, V> root = null;

  root用来存储整个树的根节点。我们继续跟踪Entry(是TreeMap的内部类)的代码：

Entry底层源码.png

  可以看到里面存储了本身数据、左节点、右节点、父节点、以及节点颜色。TreeMap的put()/remove()方法大量使用了红黑树的理论。本书限于篇幅，不再展开。需要了解更深入的，可以参考专门的数据结构书籍。

  TreeMap和HashMap实现了同样的接口Map，因此，用法对于调用者来说没有区别。HashMap效率高于TreeMap;在需要排序的Map时才选用TreeMap。