HashSet & TreeSet

1898 ワード

HashSet


  • Setインタフェースを持つ典型的な集合クラス:シーケンスX,繰返しX

  • 順序を維持する場合はLinkedHashSet classを使用します.

  • オブジェクトを保存する前に、既存のオブジェクトが同じであることを確認します.
    ->同じオブジェクトがない場合は保存し、ある場合は保存しません.

  • boolean add(Object o)は、保存するオブジェクトのequals()とhashCode()を呼び出すことで、重複するかどうかを決定します.
    ->作成するクラスはequals()とhashCode()で上書きする必要があります.
    ->equals()iv間の比較
    ->hashCode()はObjectsです.hash()を使用して作成
  • // ex
    public boolean equals(Object obj) {
    	if (!(obj instanceof Person)) return false;
        
        // Person 클래스의 iv를 사용하기 위해, obj 형변환
        Person tmp = (Person) obj;
        
        // this와 obj 비교
        return name.equals(tmp.name) && age == tmp.age;
    }
    
    public int hashCode() {
    	return (name + age).hashCode();	// String 클래스의 해쉬코드 호출
        
        // 요즘엔 이렇게 작성한다.
        return Objects.hash(name, age);
       
    }

    TreeSet


  • 範囲検索(バイナリナビゲーション)とソートに有利な集合クラス

  • データが多ければ多いほど、HashSetではなく、データの追加/削除時間が長くなります.(比較回数が増えるため)

  • バイナリ検索ツリーを使用して実装します.範囲のナビゲーションとソートに役立ちます.

  • このツリーには、ノードごとに最大2つのサブノードがあります.(0個、1個、2個)

  • 各要素(ノード)はツリーとして接続されます.(LinkedListのバリエーション)
  • class TreeNode {
    	TreeNode left;
        Object element;
        TreeNode right;
    }

  • ≪バイナリ・ナビゲーション・ツリー|Binary Navigation Tree|ldap≫:親ノードより小さい値は左側ノードに、大きな値は右側ノードに格納されます.

  • ストレージデータ:boolean add(Object o)
    addメソッドでは、equals()とhashCode()が呼び出されます.(繰り返しは許されないので)
    ストレージを順番に比較します.

  • TreeSet()には比較基準が必要です.
    オブジェクトにCompareableがあるかどうか.
    比較基準をTreeSet()に渡す必要があります.

  • バイナリツリー内のすべてのノードを一度に読み込む->ツリーを巡る
    前衛ツアー:preorder.まず親を読み,後で子供を読む.
    後列巡り:postorder.まず子供を読み,後で親を読む.
    中尉巡り:inorder.親を基準に左から読み、親から読み、右から読みます.
    等級順:1階1階、左から順番に読みます.
    ->中尉順に読むと昇順に並んだ結果が出ます.