Collection之Set学习

<!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter" /> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0" /> <v:f eqn="sum @0 1 0" /> <v:f eqn="sum 0 0 @1" /> <v:f eqn="prod @2 1 2" /> <v:f eqn="prod @3 21600 pixelWidth" /> <v:f eqn="prod @3 21600 pixelHeight" /> <v:f eqn="sum @0 0 1" /> <v:f eqn="prod @6 1 2" /> <v:f eqn="prod @7 21600 pixelWidth" /> <v:f eqn="sum @8 21600 0" /> <v:f eqn="prod @7 21600 pixelHeight" /> <v:f eqn="sum @10 21600 0" /> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" /> <o:lock v:ext="edit" aspectratio="t" /> </v:shapetype><v:shape id="图片_x0020_0" o:spid="_x0000_i1025" type="#_x0000_t75" alt="Collection_Set.jpeg" style='width:415.5pt;height:275.25pt;visibility:visible; mso-wrap-style:square'> <v:imagedata src="file:///C:\Users\yingkh\AppData\Local\Temp\msohtmlclip1\01\clip_image001.jpg" o:title="Collection_Set" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]-->

TreeSet和HahSet的区别：

 

HashSet 是哈希表实现的，无序的结合,表现为检索(contains)的时间复杂度是 o(0)
TreeSet 是红黑树实现的，排序的集合

 

 

 

 

TreeSet：

public class TreeSet<E>

    extends AbstractSet<E>

    implements SortedSet<E>, Cloneable, java.io.Serializable

{

    private transient SortedMap<E,Object> m; // The backing Map

 

 

Add方法：

public boolean add(E o) {

    return m.put(o, PRESENT)==null;

}

 

M是一个TreeMap,treeMap的put方法如下：

public V put(K key, V value) {

        Entry<K,V> t = root;

 

        if (t == null) {

            incrementSize();

            root = new Entry<K,V>(key, value, null);

            return null;

       }

 

        while (true) {

            int cmp = compare(key, t.key);

            if (cmp == 0) {

                return t.setValue(value);

            } else if (cmp < 0) {

                if (t.left != null) {

                    t = t.left;

                } else {

                    incrementSize();

                    t.left = new Entry<K,V>(key, value, t);

                    fixAfterInsertion(t.left);

                    return null;

                }

            } else { // cmp > 0

                if (t.right != null) {

                    t = t.right;

                } else {

                    incrementSize();

                    t.right = new Entry<K,V>(key, value, t);

                    fixAfterInsertion(t.right);

                    return null;

                }

            }

        }

    }

显然，TreeSet判断是否重复，是通过TreeMap的compare方法。

 

 

再看HashSet：

HashSet：

实现的接口和集成的类如下；

public class HashSet<E>

    extends AbstractSet<E>

    implements Set<E>, Cloneable, java.io.Serializable

{

    static final long serialVersionUID = -5024744406713321676L;

 

    private transient HashMap<E,Object> map;

可见，HashSet持有一个HashMap。

 

Add方法：

public boolean add(E o) {

    return map.put(o, PRESENT)==null;

    }

 

HashMap的put方法：

  public V put(K key, V value) {

    K k = maskNull(key);

        int hash = hash(k);

        int i = indexFor(hash, table.length);

 

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            if (e.hash == hash && eq(k, e.key)) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

 

        modCount++;

        addEntry(hash, k, value, i);

        return null;

    }

 

可见，HashSet主要是通过hashcode和equals方法来判断是否重复的。