FURYU Tech Blog - フリュー株式会社

フリュー株式会社の開発者が技術情報を発信するブログです。

JavaOne 2016 サンフランシスコに参加しました！（その3） #javaone #j1jp

Hello world! コンテンツ・メディア第1事業部のjyukutyoこと阪田です。

前回はAngular 2とGWTのチュートリアルセッションをレポートしました。今日はJDKの開発者であるStuart Marksさんのセッション”Collections Refueled”をレポートします。

Collections Refueled

スライドはこちらにあります。

https://stuartmarks.files.wordpress.com/2016/09/collectionsrefueled-final.pdf

タイトルの通り、Javaのコレクションフレームワークについての話です。その歴史とJava 8での拡張、Java 9での拡張と将来の作業についてでした。

内容

JDK 1.0はレガシーコレクション、VectorやHashtableなどである。1.2はコレクションフレームワークが導入された。インタフェースとしてCollection、List、Set、Map、Iteratorが、具象クラスとしてArrayList、HashSet、HashMap、TreeSet、TreeMapがある。5.0ではジェネリクス、java.util.concurrentパッケージが追加された。

Java 8

Java 8ではラムダとストリームが追加され、インタフェースにデフォルトメソッドとstaticメソッドが定義できるようになった。15年経って初めての変更だ。

// Java 7 
List list = ...;
for(String str : list)
System.out.println(str);
// Java 8
list.forEach(System.out::println);

CollectionはIterableのサブインタフェースなので、これはすべてのコレクションで動作する。

Iteratorインタフェースでは、ほとんどのイテレータは削除をサポートしていない。そのためこう書く必要があった。

@Override
public void remove() {
    throw new UnsupportedOperationException();
}

remove()のデフォルトメソッドがまさにこれだ。削除できないイテレータを作るときは、単にremove()を省くだけでよい。削除できるものを書くときは、remove()メソッドをオーバーライドするだけだ。

Collectionインタフェースでは、removeIfでバルク更新ができるようになった。

// Java 7
for (Iterator it = coll.iterator(); it.hasNext();) {
    String str = it.next();
    if (str.startsWith("A"))
        it.remove();
}
// Java 8
coll.removeIf(str -> str.startsWith("A"));

もしコレクションがArrayListなら、7の場合の計算量はO(n2)であり、8の場合はO(n)となる。

List

ListインタフェースのreplaceAllもバルク処理だ。

// Java 7
for (ListIterator it = list.listIterator(); it.hasNext();)
    it.set(it.next().toUpperCase());
for(int i=0; i<list.size(); i++)
    list.set(i, list.get(i).toUpperCase());
// Java 8
list.replaceAll(String::toUpperCase);

ただし、要素の型を変更することはできない。そうしたいときはStreamを使う。

List.sortはCollections.sortよりなぜよいのか？Collections.sortは3つのステップを使う。

  • 一時的な配列にコピーする
  • 配列をソートする
  • リストにコピーして戻す

List.sortはデフォルトでは上記と同じだが、ArrayList.sortはオーバーライドしてin-placeでソートするため、コピーはしない。Collections.sortは現在単にList.sortを呼び出すだけだ。

Map

MapインタフェースにもforEachがある。

// Java 7
for (Map.Entry<String,String> entry : map.entrySet())
    System.out.println(entry.getKey() + entry.getValue());
// Java 8
map.forEach((k, v) -> System.out.println(k + v));

replaceAllもある。

// Java 7
for (Map.Entry<String,String> entry : map.entrySet())
    entry.setValue(entry.getValue().toUpperCase());
// Java 8
map.replaceAll((k, v) -> v.toUpperCase());

Java 7までMulti-mapはとても扱いづらかった。Multi-mapはキーに対して複数の値があるマップだ。

Java 8ではこうなる。

// put(str, i)
multimap.computeIfAbsent(str, x -> new HashSet<>()).add(i);
// remove(str, i)
multimap.computeIfPresent(k, (k1, set) -> set.remove(v) && set.isEmpty() ? null : set);
// contains(str, i)
multimap.getOrDefault(str, Collections.emptySet()).contains(i);
// size()
multimap.values().stream().mapToInt(Set::size).sum();
// values()
multimap.values().stream().flatMap(Set::stream);

Comparator

Comparatorを書いて楽しい人はいる？Comparatorは多くの条件とコードの繰り返しだ。Java 8はComparatorにstaticとデフォルトメソッドを追加した。名字とnullがある名前でソートし、nullを最初に持ってくる2レベルのソートのサンプルを見てみよう。まずはJava 7から。

Collections.sort(students, new Comparator<Student>() {
  @Override 
  public int compare(Student s1,    Student s2) {
    int r = s1.getLastName().compareTo(s2.getLastName());   
    if (r != 0)
      return r; 
    String f1 = s1.getFirstName();  
    String f2 = s2.getFirstName();  
    if (f1 == null) {   
      return f2 == null ? 0 : -1;   
    } else {    
      return f2 == null ? 1 : f1.compareTo(f2); 
    }   
  } 
});

Java 8ではこうできる。

students.sort(comparing(Student::getLastName) 
                      .thenComparing(Student::getFirstName, 
                                     nullsFirst(naturalOrder())));

Java 9

JEP 269: Convenience Factory Methods for Collectionsだ。こういったAPIが追加される。

List.of() 
List.of(e1) 
List.of(e1, e2)          // fixed-arg overloads up to ten elements 
List.of(elements...)     // varargs supports arbitrary number of elements 
Set.of() 
Set.of(e1) 
Set.of(e1, e2)           // fixed-arg overloads up to ten elements 
Set.of(elements...)      // varargs supports arbitrary number of elements 
Map.of() 
Map.of(k1, v1) 
Map.of(k1, v1, k2, v2)   // fixed-arg overloads up to ten key-value pairs 
Map.ofEntries(entry(k1, v1), entry(k2, v2), ...)     // varargs
// Java 8 
List<String> stringList = Arrays.asList("a", "b", "c"); 
Set<String> stringSet = new HashSet<>(Arrays.asList("a", "b", "c")); 
Map<String,Integer> stringMap = new HashMap<>(); 
stringMap.put("a", 1); 
stringMap.put("b", 2); 
stringMap.put("c", 3); 
// Java 9 
List<String> stringList = List.of("a", "b", "c"); 
Set<String> stringSet = Set.of("a", "b", "c"); 
Map<String,Integer> stringMap = Map.of("a", 1, "b", 2, "c", 3);

設計と実装の課題としては以下のものがあった。

  •  Immutability
  •  Iteration Order
  •  Nulls Disallowed
  •  Duplicate Handling
  •  Space Efficiency
  •  Serializability

新しいstaticファクトリメソッドが返すコレクションはイミュータブルとなる。これは従来の不変性であり、不変の永続性ではない（addなどはUnsupportedOperationExceptionをスローする）。不変性はよいものである。一般的な場合、コレクションは既知の値で初期化した後、変更することはない。不変であれば自動的にスレッドセーフになる。効率、とくにスペースについて改善するチャンスがある。JDKには一般的な目的のための不変コレクションはない。

Setの要素とMapのキーのイテレーションの順序については、HashSetやHashMapであれば公式には順序が保証されないとしていたが、長い間たいてい一貫していた。これを変更すると、順序に依存しているコードは動作が変わってしまう。適用するのは新しいコレクション実装だけにする。既存のコレクションは同じままとなるだろう。

ListやSetの要素、Mapのキーや値にnullを許可しない。NullPointerExceptionをスローする。1.2でコレクションにnullを許可したのは失敗だった。Java 5以降コレクションではnullを許可していない。とくにjava.util.concurrentのコレクションではそうだ。nullはNullPointerExceptionの原因だからだ。

Setの要素やMapのキーで重複したときはIllegalArgumentExceptionをスローする。”コレクションのリテラル”で重複があるのはプログラミングのエラーである可能性が高い。理想的にはこれをコンパイル時に検出する。値はコンパイル時の定数ではない。次にいいのは、実行時の生成においてフェイルファストにする。

2つの文字列の要素を持つSetを考えてみる。

Set<String> set = new HashSet<>(3); // 3 is the number of buckets    
set.add("foo"); 
set.add("bar"); 
set = Collections.unmodifiableSet(set);

どのぐらいスペースを使っているのか？オブジェクトを数えてみる。

  • unmodifiableなラッパーが1つ
  • HashSetが1つ
  • HashMapが1つ
  • 長さが3のObject配列のテーブルが1つ
  • Nodeオブジェクトが2つ、各要素に1つずつ

サイズの見積もりとしては、オブジェクトごとに12バイトのヘッダーがある（64ビットJVMで32GB未満のヒープ、OOP圧縮あり）。int、float、参照フィールドごとにプラス4バイトだ。ということは、先ほどのオブジェクトを合計すると152バイトになる。

 

  • unmodifiableなラッパー: ヘッダー + 1フィールド = 16バイト
  • HashSetが1つ : ヘッダー + 1フィールド = 16バイト
  • HashMapが1つ: ヘッダー + 6フィールド = 36バイト
  • 長さが3のObject配列のテーブル: ヘッダー + 4フィールド = 28バイト
  • Nodeオブジェクトが2つ、各要素に1つずつ: (ヘッダー + 4フィールド) * 2 = 56バイト

フィールドベースのSet実装だとオブジェクト1つとフィールド2つで20バイトとなる。

Set<String> set = Set.of("foo", "bar");

 

実装はすべてstaticファクトリの背後にあるプライベートなクラスとしている。

コレクションはすべてシリアライズできる。ただ、デフォルトのシリアライズ形式は内部実装について漏らしてしまっていた。新しいコレクションの実装は、カスタマイズしたシリアライズ形式となる。

将来的な作業

これらはまだ計画されていない将来的な作業だ。

VectorやHashtableといったレガシーなコレクションは非推奨にする。LinkedListもそうするかもしれない。

コアなコレクションのイテレーション順序をランダムにする。新しいミューテータのデフォルトメソッドを追加する。ArrayDequeへのインデックスアクセスを追加する。

JEP 269のコレクション拡張では、パフォーマンスの改善と、順序があるSet/Mapを追加する。

Project ValhallaでのValue typesなど。

感想

Stuartさんのセッションは熱い感じで印象深かったです。これはStuartさんの最後のセッションでしたが、他2つ、Stuartさんのすべてのセッションを聴きました。

このセッションの内容としては、Javaプログラミングで使わないことはほぼないであろう、コレクションについて歴史をたどれ、興味深いものでした。

JEP 269については、以前私は個人ブログにて動作確認していました。

そのためAPIの追加は知っていました。しかしほかにも数多くの改善があり、とくにコレクションが使うスペースについて理解が深まったのはうれしいです。