Hashset对树木

问题:

我一直喜欢树,那个漂亮的O(n * lg(n))和它们的整洁。不过,我所知道的每一位软件工程师都尖锐地问我为什么要使用TreeSet。从CS的背景来看,我并不认为这是很重要的,而且我并不在乎乱七八糟的功能和桶(在Java的情况下)。
在这种情况下,我应该使用HashSet超过TreeSet

回答:

 HashSet比TreeSet快得多(对于大多数操作(如add,remove和contains),常量时间与日志时间相比),但不提供像TreeSet这样的排序保证。

HashSet

  • 类提供了基本操作(添加,删除,包含和大小)的恒定时间性能。
  • 它不能保证元素的顺序随时间保持不变
  • 迭代性能取决于HashSet的initial capacityload factor

     

    • It’s quite safe to accept default load factor but you may want to specify an initial capacity that’s about twice the size to which you expect the set to grow.

TreeSet

  • 保证基本操作的日志(n)时间成本(添加,删除和包含)
  • 确保集合的元素将被排序(升序,自然或由您通过其构造函数指定的元素)(实现SortedSet
  • 不提供迭代性能的任何调整参数
  • 提供了一些方便的方法来处理first()last()headSet()tailSet()等有序集

重点:

  • 两者都保证无重复的元素收集
  • 将元素添加到HashSet中通常更快,然后将集合转换为TreeSet以进行无重复的分类遍历。
  • 这些实现都不同步。也就是说,如果多个线程同时访问一个集合,并且至少有一个线程修改该集合,那么它必须在外部进行同步。
  •  LinkedHashSet在某种意义上介于HashSetTreeSet之间。不过,它提供了与TreeSet保证的排序遍历不同的插入顺序迭代实现为一个带有链表的散列表。

所以选择使用完全取决于你的需求,但我觉得,即使你需要一个有序的集合,那么你应该更喜欢HashSet来创建Set,然后把它转换成TreeSet。

  • 例如SortedSet<String> s = new TreeSet<String>(hashSet);

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: Hashset vs Treeset

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

− 1 = 3