# Java TreeMap源码分析

### 前言

A Red-Black tree based {@link NavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the {@code containsKey}, {@code get}, {@code put} and {@code remove} operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.

### put方法

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

put函数如果存在相同的key，则会替换原来的旧值；

put函数其实也比较好理解，跟平衡二叉树的逻辑差不多，难点在于进行红黑树变化

### get()方法

Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the key.

### 迭代遍历

• 有右子树的节点，节点的下一个节点，肯定在右子树中，而右子树中“最左”的那个节点则是右子树中最小的一个，那么当然是右子树的“最左节点”，就好像下图所示：

• 无右子树的节点，先找到这个节点所在的左子树(右图)，那么这个节点所在的左子树的父节点(绿色节点)，就是下一个节点，如下图所示：

REFERENCE