天天看點
傳回

Java集合 HashSet 和 TreeSet的了解

HashSet

HashSet實作了 Set 接口，底層是一個HashMap。源碼如下：

public class HashSet<E>
    {
        private transient HashMap<E,Object> map;

        public HashSet() {
            map = new HashMap<>();
        }
    }

通過以上源碼可以發現，建立一個HashSet對象實際上是建立了一個HashMap對象。

HashSet中的元素是無序的。這裡的無序指的是進出集合的順序。如下：

public class HashSetTest {
    public static void main(String[] args) {
        HashSet<String> hashSet = new HashSet<>();

        hashSet.add("1.Java");
        hashSet.add("2.HashSet");
        hashSet.add("3.元素");
        hashSet.add("4.進出");
        hashSet.add("5.無序");

        // 使用增強for循環變量元素
        for(String str : hashSet){
            System.out.println(str);
        }
    }
}

周遊結果為：

4.進出
2.HashSet
3.元素
1.Java
5.無序

從周遊的結果來看，元素周遊時的順序和添加時的順序不同。

HashSet中的元素是唯一的。多次添加相同的元素，隻會有一個元素加入HashSet。通過檢視HashSet中add方法的源碼發現，這依賴于底層的hashCode方法和equals方法。如下：

// HashSet中的add方法，其中又調用了HashMap中的put方法
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

從以上可以看出： add方法隻是作了一個判斷，添加元素真正起作用的還是HashMap中的put方法，元素是作為key存儲的。

// HashMap中的put方法，這裡的key是HashSet中的元素
 public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e =  e.next) {
        Object k;
        if (e.hash==hash && ((k=e.key)==key||key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
         }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

// put方法中調用的hash方法，傳回值與key（即元素）的hashCode方法有關
final int hash(Object k) {
    int h = hashSeed;
    if ( != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();
    h ^= (h >>> ) ^ (h >>> );
    return h ^ (h >>> ) ^ (h >>> );
}

從put方法的源碼中可以知道，判斷元素是否唯一，取決于表達式e.hash==hash && ((k=e.key)==key||key.equals(k))的值。其中hash值的計算與元素的hashCode方法有關；而((k=e.key)==key||key.equals(k)) 與元素的equals方法有關。如果元素的hash值相同，且元素相等（對于基礎資料類型而言）或内容相同（對于引用類型而言），表達式結果為true，說明HashSet中已有這個元素，則不會繼續添加該元素。綜上，說明HashSet中元素的唯一性與元素中的hashCode方法和equals方法有關。要保證HashSet中元素的唯一性，就需要保證這兩個方法正常判斷。是以，當HashSet中的元素為自定義類的對象時，自定義類就需要重寫hashCode方法和equals方法。如下：

public class Student {
    private String name;
    private int age;
    private String sex;

    Student(){
    }

    Student(String name, int age, String sex){
        this.name = name;
        this.age = age;
        this.sex = sex;
    }

    public int hashCode() {
        final int prime = ;
        int result = ;
        result = prime * result + age;
        result = prime * result + 
                 ((name == null) ?  : name.hashCode());
        result = prime * result + 
                 ((sex == null) ?  : sex.hashCode());
        return result;
    }

    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Student other = (Student) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        if (sex == null) {
            if (other.sex != null)
                return false;
        } else if (!sex.equals(other.sex))
            return false;
        return true;
    }
}

TreeSet

TreeSet的底層是TreeMap。如下：

public class TreeSet<E> 
{
    private transient NavigableMap<E,Object> m;

    // 這裡的NavigableMap是接口
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    //TreeMap實作了NavigableMap接口
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
}

TreeSet的元素很有特點，元素是唯一的，而且集合會根據元素的自然順序對元素排序，但元素的進出仍然是無序的。如下：

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet();

        // 添加元素
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();

        // 周遊元素
        for(Integer number : treeSet){
            System.out.print(number + );
        }
    }
}

周遊結果為：

1 3 4 5 7

這說明TreeSet中的元素不重複，按自然順序排序，且進出無序。實際上，TreeSet中元素的自然排序和元素的唯一性依賴于compareTo或compare方法。如下：

//TreeSet 中的add方法，元素仍然是作為key 存儲的
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
}

// TreeMap 中的put方法
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); 
        root = new Entry<>(key, value, null);
        size = ;
        modCount++;
        return null;
    }

    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    // TreeSet中的構造TreeSet(Comparator<? super E> comparator)
    // 實際上是調用了TreeMap中的同參構造方法，即：
    // TreeMap(Comparator<? super K> comparator)
    // 此時，指定了comparator（排序比較器），就按比較器的規則進行比較
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < )
                t = t.left;
            else if (cmp > )
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }

    // TreeSet中的無參構造方法，實際上是調用TreeMap的空參構造方法
    // 此時沒有指定comparator(排序比較器)，comparator 為null，
    // 比較時調用元素中的compareTo方法
    else {
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < )
                t = t.left;
            else if (cmp > )
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < )
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

從以上源碼可知：TreeSet在添加元素時，會對元素進行自然順序的比較。如果TreeSet的構造方法中指定了排序比較器comparator，元素的比較就使用排序比較器中的compare方法；如果沒有指定，元素的比較就使用元素中的compareTo方法。是以，要在TreeSet 中添加自定義類的對象作為元素時，要麼在TreeSet的構造方法中指定排序比較器；要麼在自定義類中實作Comparable接口，重寫compareTo方法。如下：

// 重寫compareTo方法
public class Person implements Comparable<Person>
{
    private String name;
    private String sex;
    private int age;

    Person(String name, String sex, int age){
        this.name = name;
        this.sex = sex;
        this.age = age;
    }

    public int compareTo(Person p) {
        int result1 = this.name.compareTo(p.name);
        int result2 = this.sex.compareTo(p.sex);
        int result3 = this.age - p.age;

        return result1== ?
              (result2== ? 
              (result3== ? result3 : result3)
              : result2 ) : result1;
    }
}

或者指定比較器comparator

public class TreeSetTest {
    public static void main(String[] args) {
    // 建立TreeSet對象時，在構造方法中使用匿名類的方式指定comparator
        TreeSet<Person> treeSet = 
            new TreeSet<>(new Comparator<Person>(){
            public int compare(Person p1, Person p2) {
               int result1 =   p1.getName().compareTo(
                               p2.getName());
                int result2 = p1.getSex().compareTo(p2.getSex());
                int result3 = p1.getAge() - p2.getAge();

                return result1== ?
                      (result2== ? 
                      (result3== ? result3 : result3)
                      : result2 ) : result1;
            }
        });

        treeSet.add(new Person("John","male",));
        treeSet.add(new Person("Michle","male",));
        treeSet.add(new Person("Lucy","female",));
        treeSet.add(new Person("John","male",));
        treeSet.add(new Person("Lucy","female",));
        treeSet.add(new Person("Adam","male",));

        for(Person person : treeSet){
            System.out.println(person + " ");
        }
    }
}
java學習 HashSet treeset 元素唯一 hashCode java
上一篇: 集合------Set集合（HashSet/LinkedHashSet）Set接口HashSet集合LinkedHashSet
下一篇: Java中的集合HashSet、LinkedHashSet、TreeSet和EnumSet

繼續閱讀