边读边写【3】 ----java 集合包之各个集合性能分析

上次主要看了Map接口，以及Map的选择地址：
。http://jiuyuehe.iteye.com/blog/1480386
这次看的是Set接口。还有一个总结，到这里java常用的集合基本就这些了。总结下，分析分析性能。

Set 跟List 最明显的区别就是 Set 不允许元素重复，而List 可以。
Set中主要是HashSet 跟TreeSet

HashSet
api 中对它如下解释：

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

此类为基本操作提供了稳定性能，这些基本操作包括 add、remove、contains 和 size，假定哈希函数将这些元素正确地分布在桶中。对此 set 进行迭代所需的时间与 HashSet 实例的大小（元素的数量）和底层 HashMap 实例（桶的数量）的“容量”的和成比例。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

从源码中也可以看的出来

  private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
	map = new HashMap<E,Object>();
    }

他就是用了一个Map 把key弄能了一个new Object() hash 到他实际的地址中，原来就是HashMap嘛。那具体还是回到了Map中  。点击看HashMap

-----------------------------------分割线------------------------------------------------

TreeSet
这个HashSet 就是由HashMap 实现，TreeSet 是不是TreeMap 呢。

 private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    /**
     * Constructs a new, empty tree set, sorted according to the
     * natural ordering of its elements.  All elements inserted into
     * the set must implement the {@link Comparable} interface.
     * Furthermore, all such elements must be <i>mutually
     * comparable</i>: {@code e1.compareTo(e2)} must not throw a
     * {@code ClassCastException} for any elements {@code e1} and
     * {@code e2} in the set.  If the user attempts to add an element
     * to the set that violates this constraint (for example, the user
     * attempts to add a string element to a set whose elements are
     * integers), the {@code add} call will throw a
     * {@code ClassCastException}.
     */
    public TreeSet() {
	this(new TreeMap<E,Object>());
    }

还真是-。那继续点击看TreeMap

========================================大分割线=======================================================
点击看List
点击看Map

这里将java集合包里面常用的集合以及他的实现都过了一下，这些集合各有各的特点，各有各的缺点。那么什么时候选什么集合，这里总结下：

性能测试： 单线程下，测试集合大小分别为100，1000，10000.情况下的add remove get 测试10次取平均.

以下数据来自《分布式java应用》
A=ArrayList  L= LinkedList HS= HashSet HM = HashMap TS = TreeSet V =Vector S =Stack TM = TreeMap
元素100时候（单位ns）
集合            增加        查找        删除
A              3756        2873         2444
L              3251        2829         2330
V              2402        2846         2704  
S              2180        2572         2277   
HS             2930        1559         1720
TS             5662        1846         4413
HM             3004        1579         1726
TM             5410        1840         4123


元素1000时候
集合            增加        查找        删除
A              4156        8873         9444
L              3251        12829        12330
V              2802        10846        9704  
S              1880        10572         9277   
HS             2130        1559         2720
TS             3062        1846         4413
HM             1995       1579          1726
TM             3410        1840         4123


元素10000时候
集合            增加        查找        删除
A             8156        88873         99444
L              3251        152829        152330
V             8802        95846        95704  
S              1880        96572         99277   
HS             2130        1559         2720
TS             3062        1846         4413
HM             1995       1579          1726
TM             3410        1840         4123



随着元素的增加 add 所以集合基本变动不大 List还是有所下降。 所有List 的删除，查找 性能 大幅度下降。  Set Map 基本不受元素的数量影响。

总结： 对于查找和删除较为频繁，元素量较多的情况（超过10000）Set /Map 才是更好的选择