TreeSet研究

TreeSet所有とSetのベース属性:重複できません.
また、非表示ソート機能も備えています.
 

public class RandomTest {

    public static void main(String[] args) {
        Random random = new Random();
        Set<Integer> set = new TreeSet<Integer>();

        while (set.size() != 6) {
            //  
            int randomValue = random.nextInt(33) + 1;
            
            System.out.print(randomValue + " ");
            
            //  TreeSet 
            set.add(randomValue);
        }
        System.out.println("
------------");
        Iterator it = set.iterator();
        
        //  TreeSet 
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

 
しゅつりょく
 
 

15 4 23 4 9 19 8 
------------
4 8 9 15 19 23

 
 
 
乱数をTreeSetに入れた後、再出力時に並べ替えた.
TreeSetのソースコードのadd方法を見る
 

public boolean add(E o) {
	return m.put(o, PRESENT)==null;
}

 
mとPRESENTが何なのか見てみましょう
 
 

private transient SortedMap<E,Object> m; // The backing Map
private static final Object PRESENT = new Object();

 
mの初期化を見て
 

public TreeSet() {
	this(new TreeMap<E,Object>());
}

 
基本的には、TreeSetは実際にソート機能を含むTreeMapを使用して格納されたデータであり、keyはSetセットの要素であり、valueは仮想Objectであることがわかります.
 
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;
                }
            }
        }
    }

ソートされますが、ソートの鍵はcompareメソッドで、TreeMapのkey値の順序、すなわちTreeSetの要素の順序を設定します.

    private Comparator<? super K> comparator = null;

    private int compare(K k1, K k2) {
        return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
                                 : comparator.compare((K)k1, (K)k2));
    }

TreeSetのソートを変更する場合は、TreeMapのcomparateメソッド、すなわちカスタムcomparatorを書き換える必要がありますが、TreeMapとTreeSetはすでにエントリを提供しています.

    public TreeSet(Comparator<? super E> c) {
		this(new TreeMap<E,Object>(c));
    }
    public TreeMap(Comparator<? super K> c) {
        this.comparator = c;
    }

前のコードを修正して、Comparatorをカスタマイズして、TreeSetの要素を逆順に出力させます.

public class RandomTest {

    public static void main(String[] args) {
        Random random = new Random();
        //  Comparater
        MyComparater comparater = new MyComparater();
        
        //  
        Set<Integer> set = new TreeSet<Integer>(comparater);

        while (set.size() != 6) {
            //  
            int randomValue = random.nextInt(33) + 1;
            
            System.out.print(randomValue + " ");
            
            //  TreeSet 
            set.add(randomValue);
        }
        System.out.println("
------------");
        Iterator it = set.iterator();
        
        //  TreeSet 
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}


class MyComparater implements Comparator<Integer>{

    public int compare(Integer o1, Integer o2) {
        int val1 =  o1.intValue();
        int val2 =  o2.intValue();
        return (val1 > val2 ? -1 : (val1 == val2 ? 0 : 1));
    }

}

出力:

3 16 16 25 5 3 21 11 
------------
25 21 16 11 5 3