对于如下代码:
TreeMap<String,Double> map = new TreeMap<String,Double>(); map.put("ccc",89.0); map.put("aaa",80.0); map.put("bbb",89.0); map.put("bbb",89.0);如上代码所示，程序向TreeMap放入四个值。根据”红黑数”的定义，程序会把”ccc,89.0”这个Entry做为该”红黑数”的根节点，然后执行put(“aaa”,”80.0”)时会将其作为新的节点添加到已存在的红黑树中。也就是说，以后每次向TreeMap中放入一个key-value对，系统都需要将Entry当成一个新的节点，添加到存在的”红黑数”中，通过这种方式就可以保证TreeMap中所有的key都是按一定顺序地排列的。
我们简单总结一下HashMap，HashSet与TreeMap，TreeSet两类集合。
HashMap，HashSet的存储集合元素的方式为不同的东西放在不同的位置，需要时就可以快速的找到它们。
TreeMap,TreeSet的存储方式为根据一个排序规则来为所有的元素排序，然后该集合存储的就是排序好的元素。
由于TreeMap底层采用一颗”红黑数”来保存集合中的Entry。所以TreeMap添加元素，取出元素的性能都比HashMap低。当TreeMap添加元素时，需要通过循环找到新增的Entry的插入位置，因为比较耗性能。当取出元素时，也需要通过循环才能找到合适的Entry一样比较耗性能。但并不是说TreeMap性能低于HashMap就一无是处，TreeMap中的所有Entry总是按key根据指定的排序规则保持有序状态。
备注:红黑数是一种自平衡二叉查找树 , 它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
现在我们来观察TreeMap的put(K key,V value)方法，该方法将Entry放入TreeMap的Entry链，并维护该Entry链的有序状态。下面列出源码:
public V put(K key, V value) { //定义一个t来保存根元素 Entry<K,V> t = root; //如果t==null，表明是一个空链表 if (t == null) { //如果根节点为null，将传入的键值对构造成根节点（根节点没有父节点，所以传入的父节点为null） root = new Entry<K,V>(key, value, null); //设置该集合的size为1 size = 1; //修改此时+1 modCount++; return null; } // 记录比较结果 int cmp; Entry<K,V> parent; // 分割比较器和可比较接口的处理 Comparator<? super K> cpr = comparator; // 有比较器的处理，即采用定制排序 if (cpr != null) { // do while实现在root为根节点移动寻找传入键值对需要插入的位置 do { //使用parent上次循环后的t所引用的Entry // 记录将要被掺入新的键值对将要节点(即新节点的父节点) parent = t; // 使用比较器比较父节点和插入键值对的key值的大小 cmp = cpr.compare(key, t.key); // 插入的key较大 if (cmp < 0) t = t.left; // 插入的key较小 else if (cmp > 0) t = t.right; // key值相等，替换并返回t节点的value(put方法结束) else return t.setValue(value); } while (t != null); } // 没有比较器的处理 else { // key为null抛出NullPointerException异常 if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; // 与if中的do while类似，只是比较的方式不同 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); } // 没有找到key相同的节点才会有下面的操作 // 根据传入的键值对和找到的“父节点”创建新节点 Entry<K,V> e = new Entry<K,V>(key, value, parent); // 根据最后一次的判断结果确认新节点是“父节点”的左孩子还是又孩子 if (cmp < 0) parent.left = e; else parent.right = e; // 对加入新节点的树进行调整 fixAfterInsertion(e); // 记录size和modCount size++; modCount++; // 因为是插入新节点，所以返回的是null return null; }