【Java】コレクション - リスト/セット/マップ/スタック/キュー

リスト

• 配列のように要素順序があるコレクション
  • ArrayList
  • LinkedList
  • Vector（ArrayListを優先的に使う）

ArrayList

• 後からでも要素追加削除可能
  • cf:配列は不可
• インデックス値による値の読み書き(ランダムアクセス)は、位置によらず一定時間でアクセス可能
• 値の頻繁な挿入削除は低速
• 挿入時に確保していたメモリの領域を超えると自動でメモリ再割り当てが発生する
• →あらかじめ要素数が想定される場合サイズ宣言しよう
  var data = new ArrayList<String>(30);

import java.util.ArrayList;
import java.util.Arrays;
public class Main {
  public static void main(String[] args) {
    var list = new ArrayList<Integer>(Arrays.asList(10, 15, 30, 60));
    var list2 = new ArrayList<Integer>(Arrays.asList(1, 5, 3, 6));
    var list3 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));

    for (var i : list) {
      System.out.println(i / 5); //2,3,6,12
    }
    //要素数
    System.out.println(list.size()); //4
    //0番目の要素取得
    System.out.println(list.get(0)); //10
    //指定の要素を含むか？
    System.out.println(list.contains(30)); //true
    //位置を検索
    System.out.println(list.indexOf(30));  //2
    //位置を後ろから検索
    System.out.println(list.lastIndexOf(30)); //2
    //リストが空か
    System.out.println(list.isEmpty());    //false
    //0番目の要素削除
    System.out.println(list.remove(0));   //10
    System.out.println(list);             //[15, 30, 60]
    //コレクション挿入
    list.addAll(list2);
    System.out.println(list); //[15, 30, 60, 1, 5, 3, 6]
    //コレクション内の要素全削除
    list.removeAll(list3);
    System.out.println(list); //[15, 30, 60, 5, 6]
    //0番目の要素セット
    list.set(0, 100);
    var data = list.toArray();
    System.out.println(Arrays.toString(data)); //[100, 30, 60, 5, 6]
  }
}

LinkedList

• 要素同士を双方向のリンクで参照
• インデックス値で要素を読み書きするのに不向き
• 要素の挿入/削除は高速
  • 要素の移動不要、前後リンクの付け替えのみ
• 連続して要素の挿入が発生、リストに順にアクセス：LinkedList
• 既存要素の取得や書き換え：ArrayList

import java.util.Arrays;
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {

    var list = new LinkedList<String>(Arrays.asList("丑", "寅", "卯"));
    list.addFirst("子");
    list.addLast("辰");
    System.out.println(list); //[子, 丑, 寅, 卯, 辰]
    System.out.println(list.getFirst()); //子
    System.out.println(list.getLast()); //辰
    System.out.println(list.removeFirst()); //子
    System.out.println(list.removeLast()); //辰
    System.out.println(list); //[丑, 寅, 卯]
  } 
}

セット

• 要素の重複不可。要素の包含関係に関心がある場合使用
  • HashSet
  • LinkedHashSet
  • TreeSet

HashSet

• 並び順を管理しない

import java.util.Arrays;
import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    //重複した要素は無視
    var hs = new HashSet<Integer>(Arrays.asList(1, 20, 30, 10, 30, 60, 15));
    var hs2 = new HashSet<Integer>(Arrays.asList(10 ,20 ,99));

    //System.out.println(hs);
    System.out.println(hs.size()); //6
    System.out.println(hs.isEmpty()); //false
    //指定要素を含むか
    System.out.println(hs.contains(1)); //true  
    //指定要素を全部含むか
    System.out.println(hs.containsAll(hs2)); //false
    //指定した要素を削除
    System.out.println(hs.remove(1)); //true 
    System.out.println(hs); //[20, 10, 60, 30, 15]
    //指定要素がセットに含まれない場合全部追加（和集合）
    hs.addAll(hs2);
    System.out.println(hs); //[99, 20, 10, 60, 30, 15]
    //コレクション内要素でないものを全削除（積集合）
    hs.retainAll(hs2);
    System.out.println(hs); //[99, 20, 10]

    var hs3 = new HashSet<Integer>(Arrays.asList(1, 10 , 20));
    //指定要素を全部削除(差集合)
    hs.removeAll(hs3);
    System.out.println(hs);  //[99]
  }
}

TreeSet

• ソート済みのセット
• 追加要素は自動でソートされる

import java.util.Arrays;
import java.util.TreeSet;

public class Main {
  public static void main(String[] args) {
    var ts = new TreeSet<Integer>(Arrays.asList(1, 20, 30, 10, 60, 15));
    System.out.println(ts); //[1, 10, 15, 20, 30, 60]
    //逆順並びかえ
    System.out.println(ts.descendingSet()); //[60, 30, 20, 15, 10, 1]
    //指定要素以上で最小のものを取得
    System.out.println(ts.ceiling(15));     //15
    //指定要素より小さく最大のものを取得
    System.out.println(ts.lower(15));       //10
    //指定要素以上を取得
    System.out.println(ts.tailSet(15));     //[15, 20, 30, 60]
    //指定要素より小さいものを取得、第2引数trueで等しいものも含む
    System.out.println(ts.headSet(30, true)); //[1, 10, 15, 20, 30]
  }
}

マップ

• 一意のキーと値のペアで管理
• インデックスではなくキーで情報にアクセス
• Collectionインターフェースを継承してない（マップをそのまま拡張forに渡せない）
  • HashMap
  • IdentityHashMap
  • WeakHashMap
  • LinkedHashMap
  • TreeMap
  • HashTable（HashMapを優先）

HashMap

• キーの順番は保証しない
• 内部のハッシュデーブルでオブジェクトを管理
• ハッシュ値はオブジェクト値をもとに算出した任意のint
  • オブジェクトが等しいとハッシュ値も等しい
• 注1：hashCodeメソッドの実装
  • オブジェクトのハッシュ値を求める求めるメソッド
  • 同じ値のオブジェクトは同じハッシュ値を返す
  • 重複発生しにくいよう適切に分布している
• 注2：ハッシュ表のサイズ
  • 格納する要素数に対し十分大きいこと
  • 要素が一定サイズを超えたらハッシュ表の再割り当てが発生
  • var data = new HashMap<String,String>(30, 0.8F)

import java.util.HashMap;
import java.util.Map;


public class Main {
  public static void main(String[] args) {
    var map = new HashMap<String, String>(Map.of("Cat", "ねこ",
      "Dog", "いぬ", "Bird", "とり"));
    //指定キーが含まれるか
    System.out.println(map.containsKey("Dog")); //true
    //指定値が含まれるか
    System.out.println(map.containsValue("ねこ")); //true
    //マップが空か
    System.out.println(map.isEmpty()); //false
    //全キー取得
    for (var key : map.keySet()) {
      System.out.println(key); //Dog Bird Cat
    }
    //全値取得
    for (var value : map.values()) {
      System.out.println(value); //いぬ とり ねこ
    }
    //指定キーの値をvalueに変更
    map.replace("Cat", "neko");
    //指定キーの値/値(old)をvalue(new)に変更
    map.replace("Bird", "とり", "tori");
    //全ての要素取得
    for (var entry : map.entrySet()) {
      System.out.println(entry.getKey() + ":" + entry.getValue()); //Dog:いぬ Bird:tori Cat:neko
    }
  }
}

IdentityHashMap

• IdentityHashMapではキーを同一性（==演算子）で判定
  • cf:標準的なHashMapは同値性（equalsメソッド）で判定

//HashMapの場合、valueが同じなら上書きされ、エントリは１つしか登録されない
//IdentityHashMapの場合、key1,2はオブジェクトとして別物なのでそれぞれ異なるキーとみなす
import java.util.HashMap;
import java.util.IdentityHashMap;
public class Main {
  public static void main(String[] args) {
    var key1 = Integer.valueOf(256);
    var key2 = Integer.valueOf(256);

    //var data = new HashMap<Integer, String>() {
    var data = new IdentityHashMap<Integer, String>() {
      {
        put(key1, "Hoge");
        put(key2, "Foo");
      }
    };  
    //System.out.println(data); //{256=Foo} 
    System.out.println(data);   //{256=Foo, 256=Hoge}
  }
}

WeakHashMap

• キーを弱参照で管理
  • 現在のMap以外でキーが参照されないとガベージコレクションの対象になる
• cf:標準のHashMapは強参照
  • マップがキーを維持している限りガベージコレクション対象外

TreeMap

• 順序を保証
  • キーをRed-Black Tree(赤黒木)で管理
  • ノード(節点)
    • 1ノードに最大2子ノード
    • 左の子ノード<現在のノード<右の子ノード
    • 最終的にノードの大小関係を満たす箇所に追加

//キーが辞書順に並べ変えられる
import java.util.Map;
import java.util.TreeMap;

public class Main {
  public static void main(String[] args) {
    var data = new TreeMap<String, String>(Map.of("Cat", "ねこ",
        "Dog", "いぬ", "Bird", "とり"));
    for (var key : data.keySet()) {
      System.out.println(key); //Bird Cat Dog
    }
  }
}

キーの順番

• TreeMap標準では文字列は辞書、数値は大小でソート
• ラムダ式でカスタマイズ可能

//キーの長さでソート
import java.util.TreeMap;
// import java.util.Comparator;

public class Main {
  public static void main(String[] args) {
    var data = new TreeMap<String, String>(
        (x, y) -> x.length() - y.length()
      );
//    匿名クラスの場合
//    var data = new TreeMap<String, String>(new Comparator<String>(){
//      @Override
//      public int compare(String x, String y) {
//        return x.length() - y.length();
//      }
//    });

      data.put("Cat", "ねこ");
      data.put("Shiba inu", "しばいぬ");
      data.put("Bird", "とり");
      System.out.println(data); //{Cat=ねこ, Bird=とり, Shiba inu=しばいぬ}
  }
}

配列/リストのソート

• sortメソッド

//文字列長で昇順ソート
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) {  

    var data = new String[] { "Cat", "Shiba inu", "Bird", "Poodle" };
    Arrays.sort(data, (x, y) -> x.length() - y.length());
    System.out.println(Arrays.toString(data)); //[Cat, Bird, Poodle, Shiba inu]

    var list = new ArrayList<String>(Arrays.asList("Cat", "Shiba inu", "Bird", "Poodle"));
    list.sort((x, y) -> x.length() - y.length());
    System.out.println(list); //[Cat, Bird, Poodle, Shiba inu]
  }
}

あいまい検索

• NavigateMapインターフェースでそのキーにい近いキーを取得

import java.util.TreeMap;

public class Main {
  public static void main(String[] args) {
    var data = new TreeMap<String, String>() {
      {
        put("nekko", "ねっこ");
        put("nezumi", "鼠");
        put("night", "夜");
        put("nature", "自然");
      }
    };

    var key = "neko";

    if (data.containsKey(key)) {
      System.out.println(key + "は" + data.get(key) + "です。");
    } else {
      System.out.print("検索中の単語は");
      //指定のキーより小さいキーで最大のエントリを取得
      System.out.print(data.lowerKey(key) + "または");
      //指定のキーより大きいキーで最小のエントリを取得
      System.out.print(data.higherKey(key));
      System.out.println("ですか？");
    }
  }
}

LinkedHashMap

• リンクリストでキーを管理

import java.util.LinkedHashMap;

public class Main {
  public static void main(String[] args) {
    //第三引数=trueはアクセス順
    //第三引数=falseは挿入順
    var data = new LinkedHashMap<String, String>(10, 0.7f, false) {
      {
        put("aaa", "あいうえお");
        put("bbb", "かきくけこ");
        put("ccc", "さしすせそ");
        put("ddd", "たちつてと");
      }
    };
    System.out.println(data.get("ccc"));
    System.out.println(data.get("aaa"));
    System.out.println(data.get("bbb"));
    System.out.println(data.get("ddd"));
    //true
    System.out.println(data); //{ccc=さしすせそ, aaa=あいうえお, bbb=かきくけこ, ddd=たちつてと}
    //false
    //System.out.println(data); //{aaa=あいうえお, bbb=かきくけこ, ccc=さしすせそ, ddd=たちつてと}
  }
}

スタック/キュー

• リストの両端からの値の出し入れに特化
• スタック：後入れ先出し (LIFO:Last In First Out/ 先入れ後出し (FILO:First In Last Out)
  • 最後に行った操作から取り出す (Undo操作など)
• キュー：先入れ先出し (FIFO:First In First Out)
  • 最初に入った要素から順に取り出す (待ち行列)
• Dequeインターフェース：両端キュー
  • リストの先頭/末尾から要素を追加/取得できる
  • ArrayDeque
  • LinkedList
  • Stack

ArrayDeque

• 内部は循環配列
  • 配列内の任意の範囲(head~tail)に要素を格納
  • 要素の挿入/削除で要素は変えず先頭/末尾位置のみ移動する
  • 挿入で末尾位置が配列末尾を超えたら配列先頭に循環
  • 先頭要素へのアクセスが高速
• DequeはQueueのサブインターフェースなのでQueueメソッドも使用可能

import java.util.ArrayDeque;

public class Main {
  public static void main(String[] args) {
    //スタック
    var data = new ArrayDeque<Integer>();
    data.addLast(10);
    data.addLast(15);
    data.addLast(30);

    System.out.println(data); //[10, 15, 30]
    System.out.println(data.removeLast()); //30
    System.out.println(data); //[10, 15]
    //キュー
    var data2 = new ArrayDeque<Integer>(); 
    data2.addLast(10);
    data2.addLast(15);
    data2.addLast(30);

    System.out.println(data2); //[10, 15, 30]
    System.out.println(data2.removeFirst()); //10
    System.out.println(data2); //[15, 30]
  }
}