解读java集合框架源码-TreeMap

基于红黑树实现的NavigableMap实现类,迭代顺序依照key的Comparable进行排序。或者通过构造器提供一个Comparator类来进行排序。
提供了O(logn)时间复杂度的containsKey、get、put、remove操作,由于红黑树不是绝对的平衡,而是黑节点的平衡因此最坏时间复杂度为O(2logn)

JDK注释

类继承图

成员变量

构造器

元素添加


访问元素


总结

  1. TreeMap不允许key为null
  2. 提供有序性的遍历,遍历的顺序取决于key的Comparable#compareTo方法或者传入的Comparator#compare
  3. 主要难点在于红黑树的平衡性维护,这里就不详细分解了。比较复杂,有兴趣的可以从2-3树入手,扩展到红黑树的底层原理