TreeMap相关

JAVA基础

1.TreeMap底层结构？

• 红黑树

2.TreeMap如何去重，处理冲突？

• 如果在比较过程中，调用对象本身实现的comparable的compareTo(t.key)方法或指定的comparatord的compare(key,t.key)，找到对应的元素比较相等，则直接替换，不会发生冲突。若没有找到对应的元素，则寻找合适的位置添加元素。

3.与HashMap性能效率相比如何？

• TreeMap查找时间复杂度为O(logN)
• HashMap无冲突的hash table复杂度是O(1)，一般是O(c)，c为哈希关键字冲突时查找的平均长度，最坏情况仍然是O(N)

4.TreeMap添加一个元素的过程。

• 在TreeMap的put()的实现方法中主要分为两个步骤
  第一：构建排序二叉树，第二：平衡二叉树。
  对于排序二叉树的创建，其添加节点的过程如下：
  1、以根节点为初始节点进行检索。
  2、与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。
  3、循环递归2步骤知道检索出合适的叶子节点为止。
  4、将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。

• 找到正确位置后将插入即可，这样做了其实还没有完成，因为TreeMap的底层实现是红黑树，红黑树是一棵平衡排序二叉树，普通的排序二叉树可能会出现失衡的情况，所以下一步就是要进行调整。fixAfterInsertion(e);
  调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。

• 对于新节点的插入有如下三个关键地方：
  1、插入新节点总是红色节点 。
  2、如果插入节点的父节点是黑色, 能维持性质 。
  3、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。
  为了保证下面的阐述更加清晰和根据便于参考，我这里将红黑树的五点规定再贴一遍：
  1、每个节点都只能是红色或者黑色
  2、根节点是黑色
  3、每个叶节点（NIL节点，空节点）是黑色的。
  4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
  5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

参考：http://blog.csdn.net/chenssy/article/details/26668941