PDF版：『Java 2 Standard Edition 5.0 Tiger』

Java 2 Standard Edition 5.0 Tiger―拡張された言語仕様について

• 作者: 柴田 芳樹
• 出版社/メーカー: ピアソンエデュケーション
• 発売日: 2005/04
• メディア: 単行本

PDF版を修正しました。以前公開して、赤字になっていた部分を黒に戻したのと、内容を見直しています。

ＰＤＦ版『Java 2 Standard Edition 5.0 Tiger―拡張された言語仕様について』

ハッシュコードの衝突の増加

Effective Java 第2版 (The Java Series)

• 作者: Joshua Bloch
• 出版社/メーカー: ピアソンエデュケーション
• 発売日: 2008/11/27
• メディア: 単行本（ソフトカバー）

項目9「equalsをオーバーライドする時は、常にhashCodeをオーバーライドする」では、ハッシュコードの計算方法がp.47に示されています。そして、計算の最初のステップとして、次のようにのべられています。

1. 何らかのゼロではない定数、たとえば、17を、resultという名のint変数に保存します。

この17を使用することに関して、p.48には次のように述べられています。

ゼロでない初期値がステップ1で使用されていますので、ステップ2aで計算された結果ゼロとなるハッシュ値を持つ最初のフィールドから、ハッシュ値は影響を受けます。もし、ステップ1で初期値としてゼロが使用されたら、全般的なハッシュ値は、そのような最初のフィールドから影響を受けないことになり、衝突が増加することになります。値17は、任意の値です。

この衝突が増加するということに関しては、ハッシュコードの計算対象となるフィールドが固定数であれば、値が0であっても衝突は増加しません。たとえば、次のようなPointクラスにhashCodeメソッドを実装すると、計算対象のフィールドはxとyの2つです。

public class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

この場合、初期値がゼロでもハッシュコード値の衝突が増えることはありません。では、次のようなクラスではどうでしょうか。

public class IntArray {
    private int[] data;

    public IntArray(int[] data) {
        this.data = data.clone();
    }
    ....
}

このIntArrayクラスは、intの配列を保持することになります。したがって、ハッシュコードの計算対象は、配列の個々の要素となります。そして、その要素の個数はインスタンスごとに異なります。もし、ハッシュコードの初期値としてゼロを使用すると、簡単にハッシコードが衝突します。次の二つのインスタンス生成で作成されたインスタンスは、ハッシュコードの初期値としてゼロが使用されると、どちらもハッシュコード値がゼロとなり、衝突することになります。

new IntArray(new int[] {0});
new IntArray(new int[] {0, 0});

HashMapの大きさ

Javaのソースコードをレビューしていると、HashMapを作成して、キーと値の組を数個しか入れていないものを見かけたりしています。実際、マッピングとして、3個のキーと値の組しか入れていなくて、そのようなHashMapを3個作成しているコードがありました。

そこで、HashMapのオブジェクトの大きさを調べてみました。HashMapを作成すると、そのインスタンスには、以下のインスタンスフィールドが含まれます。

　（配列）参照型 1個、int型　3個、float型 1個

これだけで、5個×4バイト=20バイトです。参照型は、ネストしたクラスであるEntry型の配列となっており、最初にデフォルトでは大きさ16の配列が生成されています。つまり、16×4バイト=64バイトの大きさの配列です。したがって、デフォルトのままでHashMapを生成すると、84バイトは最低限消費します。

そこに、3個のキーと値の組を入れたとすると、ネストしたクラスであるEntryクラスは4個のフィールドを持ちますので、4×4バイト×3個=48バイトを消費します。HashMapとの合計で84バイト+48バイト=132バイト。

そして、このようなHashMapを3個作ると、132バイト×3個=396バイトとなります。さらにキーがIntegerクラスで値がBooleanクラスであり、個別にインスタンスを生成していました。つまり、キーと値の9個の組だけで、9×2×4バイト=72バイト。すべてを合計すると、396バイト+72バイト=468バイト。

これに対して、大きさ3の配列と大きさ3×3の配列で書き直したので、12×4バイト=48バイト。元々の3個のHashMapで表を構築しようとしているコードは非常に可読性が悪かったのですが、すっきりと書き直すことができ、使用するメモリー量も1/10になりました。

大量のデータを取り扱う場合に、O(1)の計算スピードを得るためにHashMapを利用します。しかし、データが3個しかない場合には、O(N)であるアルゴリズムでも問題ない訳です。通常のプログラミングでは、HashMapの大きさを気にすることはありませんが、単純な配列で表現できる小さなデータをHashMapで表現しようとすると、コードの可読性が低くなり、不必要にメモリを消費する可能性もあるということです。

Java 7のArrays.sort(Object[])

Java 7のEarly Access版をダウンロードしました。昨日、Joshua Bloch氏にProject Coinへ彼が提案している言語仕様の変更はすでに実装されているのかと聞いたところ、まだプロトタイプされていないということでした。で、その話のついでに、ソートの話になり、Java 7にはTimSortが入っているということで、調べてみました。

従来、コレクションフレームワークのArraysクラスのsort(Object[])は、今まではマージソートで実装されていました。しかし、Java 7にはパッケージプライベート宣言されているTimSortクラス（TimSort.java）が追加されており、Arrays.sort(Object[])（と関連する他のsortメソッド）はデフォルトでTimSortクラスのsortメソッドを使用するように書き換えられています。

TimSort.javaクラスのソースコードに書かれているJavadocコメントは以下のようになっています。

A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.

This implementation was adapted from Tim Peters's list sort for Python, which is described in detail here:

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

Tim's C code may be found here:

http://svn.python.org/projects/python/trunk/Objects/listobject.c

The underlying techniques are described in this paper (and may have even earlier origins):

"Optimistic Sorting and Information Theoretic Complexity"
Peter McIlroy
SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
pp 467-474, Austin, Texas, 25-27 January 1993.

Tim Peters氏の実装に基づいているので、TimSortと呼ばれているようです。

200万個のデータでベンチマークしてみました。ランダムなデータ、ソートされたデータ、逆順にソートされたデータの3種類で従来のマージソートと比較してみました。結果は、マージソートの処理時間を100とすると、ランダムなデータの場合は109.3。ソートされたデータでは44.4。逆順にソートされたデータでは27.3でした。

ランダムなデータに関しては、従来のマージソートの方が早いですが、ソートされたデータや逆順にソートされたデータの場合には、TimSortの方が圧倒的に早いようです。

ランダムなデータに関しても、（環境がないので測定していませんが）HotSpot Server VMで遜色ないスピードが出れば、ほとんどのデータでに関しては、スピードアップが図られることになると思います。また、Collections.sort(List)も内部的には、Arrays.sort(Object)を使用していますので、Java 7ではソートの高速化が行われることになります。

今回のJavaへのTimSortの移植作業は、Joshua Bloch氏が行っています。

Java言語のenum型（2）

昨日、青葉台のブックファーストでまた何冊かのJavaの入門書を調べてみましたが、やはり、enumをきちんと説明している本はないですね。入門書を卒業したら、その後は、何を読んで勉強されているのでしょうか。それとも、何も考えることなく、そう書くものだとということで、前任者のコードをCopy&Pasteしながら、日々の開発業務をされているのでしょうか。

ソースコードを読むと、その人の技術レベルがある程度分かります。技術レベルの低い人ほど、良く分かります。なぜならば、詳細に注意を払ったコードになっていないからです。あるいは、本質を理解していないので、無駄なコードを書いていたりします。

入門書を卒業したら、時間がかかっても以下の2冊は、きちんと読んでJavaでプログラミングしてもらいたいものです。

Effective Java 第2版 (The Java Series)

• 作者: Joshua Bloch
• 出版社/メーカー: ピアソンエデュケーション
• 発売日: 2008/11/27
• メディア: 単行本（ソフトカバー）

プログラミング言語Java (The Java Series)

• 作者: ケン・アーノルド
• 出版社/メーカー: ピアソンエデュケーション
• 発売日: 2007/04
• メディア: 単行本

先日PDFを公開しました『Java 2 Standard Edition 5.0 Tiger』ですが、現在、読み直して内容の修正を行っています。大幅な修正ではなく、細かな修正です。修正版は、来月には公開できるのではないかと思います。

（「Java言語のenum型」、「PDF版：『Java 2 Standard Edition 5.0 Tiger』」）

"polygenelubricants" ?

Joshua Blochがプログラムを書いて、英単語を組み合わせて見つけた文字列です。

Math.abs("polygenelubricants".hashCode())

ということで、この結果の値は？

関連するパズルは、パズル33とパズル44です。

Java Puzzlers 罠、落とし穴、コーナーケース

• 作者: ジョシュア・ブロック
• 出版社/メーカー: ピアソン・エデュケーション
• 発売日: 2005/11/14
• メディア: 大型本

PDF版：『Java 2 Standard Edition 5.0 Tiger』

Java 2 Standard Edition 5.0 Tiger―拡張された言語仕様について

• 作者: 柴田 芳樹
• 出版社/メーカー: ピアソンエデュケーション
• 発売日: 2005/04
• メディア: 単行本

2005年4月に発売してからすでに4年が経過し、絶版となっているため入手が困難になっている本書のPDF版を公開します。

ＰＤＦ版『Java 2 Standard Edition 5.0 Tiger―拡張された言語仕様について』

第8章の8.2節「アノテーション処理ツール（apt）」の内容は古いため役立ちませんが、それ以外は、今でも十二分に役立つ内容だと思います。リリース1.5以降の新たな言語仕様で開発している人は、一度目を通してもらえれば、Java言語に対する理解が深まるかと思います。

8.2節を書き直し、他の部分に加筆・修正した版を作成して公開したいと思っていますが、あまり、期待しないでください。

ElvisクラスのleaveTheBuilding()メソッド

『Effective Java 第2版』の項目3 「privateのコンストラクタかenum型でシングルトン特性を強制する」（17頁）のElvisクラスには、初版にはなかったleaveTheBuidling（）メソッドが追加されています。翻訳した時は、メソッドが追加されているなという程度で深く気にしなかったのですが、調べてみました。

Wikipediaの"Elvis has left the buidling"よれば、次のように説明されています。

"Elvis has left the building!" is a phrase that was often used by public address announcers following Elvis Presley concerts to disperse audiences who lingered in hopes of an Elvis encore. Al Dvorin, a concert announcer who traveled with Elvis throughout the performer's career, made the phrase famous when his voice was captured on many recordings of Elvis' performances.

Elvis Presleyのコンサートで、アンコールを期待して帰らない聴衆に対して使われた言葉のようです。Elvisクラスに追加されたleaveTheBuilding()メソッドを見て、分かる人にはすぐに分かるのでしょうが・・・・

このようなpun（駄洒落）は、英語のネイティブスピーカーではない私にとっては、翻訳者泣かせです。今回のような例は、特に翻訳する必要もないので問題ないのですが、『Java Puzzlers』を翻訳した時は、かなり苦労しました。

Java Puzzlers 罠、落とし穴、コーナーケース

• 作者: ジョシュア・ブロック、ニール・ガフター
• 出版社/メーカー: ピアソン・エデュケーション
• 発売日: 2005/11/14
• メディア: 大型本

この本では、とにかくパズルのタイトルが駄洒落や語呂合わせだらけでした。最初は著者のJoshua Blochに都度問い合わせして、訳注を追加していました。しかし、あまりにも多いので、訳注では無理と判断しました。それで、日本語版に向けて特別に付録Ｃ「語呂合わせとポップカルチャー参照」という解説のための付録を書いてもらって、それを翻訳したものを日本語版に含めたのです。

ところで、この『Java Puzzlers』ですが、タイトルが良くないのかあまり売れていないです。一度、その点に関してJoshua Blochと話した時に、『Defective Java』の方が良かったかもと冗談を彼は言っていました。内容としては、Javaでプログラミングする人にとっては、『Effective Java 第2版』と同様に必読だと私は思っています。Javaでプログラミングする上で知っておくべきことを、パズル形式で教えてくれる内容です。発売からすでに3年以上経過していますが、内容は陳腐化していません。

訂正：可変長パラメータと配列パラメータの互換性

以前、可変長パラメータと配列パラメータの互換性として解説を書きました。最後に、コンパイルエラーになるサンプルコードを掲載していますが、そのコードをJoshua Blochにパズルとしてどうかということで以前送りました。

JavaOneに向けて「Java Puzzlers」セッションの準備を彼は行っているのですが、私の書いたサンプルコードをNeal Gafterに彼が見せたところ、コンパイラーのバグということでバグ登録されたようです。

本来ならば、b.f(1,2,3)の呼び出しもコンパイルエラーにならなければいけないということでした。

つまり、可変長パラメータとしてのメソッド呼び出しが可能かどうかは、オブジェクトの実際の型ではなく、それを参照している型の宣言において該当メソッドが可変長パラメータとされている必要があることになります。

More Effective Java With Google's Joshua Bloch

Joshua Blochへのインタビュー記事をたまたま見つけました。

http://java.sun.com/developer/technicalArticles/Interviews/bloch_effective_08_qa.html