除了排序和排序之外,java中的treemap数据结构的优点

Question

除了排序和排序之外,java中的treemap数据结构有什么优势？treemap数据结构如何在内部工作？

Answer 1

Treemap的主要优点是它允许以排序顺序存储键值映射.Treemap内部使用红黑树.

来自javadocs:

基于红黑树的NavigableMap实现.地图根据其键的自然顺序进行排序,或者根据使用的构造函数在地图创建时提供的比较器进行排序.

此实现为containsKey,get,put和remove操作提供有保证的log(n)时间成本.算法是Cormen,Leiserson和Rivest的算法导论中的算法的改编.

来自Wiki 的红黑树:

红黑树是一种自平衡二叉搜索树,是计算机科学中使用的数据结构.通过用两种颜色中的一种(这些通常称为"红色"和"黑色",因此树的名称)绘制每个节点来提供自平衡,使得得到的绘制树满足某些属性.使它变得非常不平衡.修改树时,随后重新排列新树并重新绘制以恢复着色属性.这些属性的设计使得这种重新排列和重新着色可以有效地进行.树的平衡并不完美,但它足以保证在O(log n)时间内进行搜索,其中n是树中元素的总数.插入,

要了解有关Reb Black树的更多信息,请查看:http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

要了解有关树形图检查的更多信息,请访问:http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html