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

Question

除了排序和排序之外，java中树形图数据结构的优势是什么？树形图数据结构在内部如何工作？

Answer 1

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

从javadocs：

基于红黑树的 NavigableMap 实现。地图根据其键的自然顺序排序，或者由地图创建时提供的比较器排序，具体取决于使用的构造函数。

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。

来自 Wiki的红黑树：

红黑树是一种自平衡二叉搜索树，是计算机科学中使用的一种数据结构。自平衡是通过用两种颜色中的一种（这些颜色通常称为“红色”和“黑色”，因此树的名称）以这样的方式绘制每个节点来提供的，使得生成的绘制树满足某些属性t 让它变得明显不平衡。当树被修改时，新树随后被重新排列并重新绘制以恢复着色属性。这些属性的设计方式使得这种重新排列和重新着色可以有效地执行。树的平衡并不完美，但足以保证在 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

Answer 2

如果您的意思是 TreeMap 优于 HashMap，则没有。事实上 HashMap 比 TreeMap 有一个优势——它更快。至于内部 impl，您可以从 Oracle 站点下载标准 lib src，或者从这里http://sourceforge.net/projects/jdk7src/