staticメソッドしか持たないクラス
PHPやJavaで、staticメソッドしか持たないクラスを作るとき（例えばJavaのMathクラスのようなクラス）には、そのクラスのインスタンスが生成できないようにする必要がある（staticメソッドにインスタンス経由でメソッドにアクセスするのは明らかに無駄だ。だから、staticメソッドしか持たないクラスのインスタンスを生成する必要がない。無駄なことはできないようにした方が安全だ）。
インスタンスを生成できないクラスを作るためには、次のようにコンストラクタをprivateで定義すればいい。
<?php class TestClass { // コンストラクタをprivateで定義することで、インスタンスの生成を防ぐ。 private function __construct(){ } // TestClassの持つstaticメソッド。 public static function testMethod(){ } } ?>
public class TestClass { // コンストラクタをprivateで定義することで、インスタンスの生成を防ぐ。 private TestClass(){ } // TestClassの持つstaticメソッド。 public static void testMethod(){ } }
コンストラクタがprivateで定義されると、そのクラス外からコンストラクタを呼ぶことができなくなるので、インスタンスを生成することは不可能になる。
JavaScript関連リファレンス
JavaScript関連のサイトはたくさんあるが、ある程度信頼できるリファレンスのようなものがなかなか見つからない（JavaScript歴が短いせいかもしれないけど）。とりあえず見つけたものをメモ代わりに書いておく。
Core JavaScript 1.5 Reference - mozilla developer center
http://developer.mozilla.org/ja/docs/Core_JavaScript_1.5_Reference
Mozillaにあるリファレンス。未完成の部分も多い。
Core JavaScript Reference 1.5
http://www.webreference.com/javascript/reference/core_ref/contents.html
これはきちんとしたリファレンス。JSEclipseにも付属しているもの。ただし英語。
Gecko DOM Reference
http://developer.mozilla.org/ja/docs/Gecko_DOM_Reference
documentなんかを使うときに必要となるDOMのリファレンス。
Dynamic HTMLとXML：XMLHttpRequestオブジェクト
http://developer.apple.com/jp/internet/webcontent/xmlhttpreq.html
AJAXには欠かせないXMLHttpRequestの使い方やメソッド一覧など。
The XMLHttpRequest Object
http://www.w3.org/TR/XMLHttpRequest/
W3CのXMLHttpRequestのリファレンス。英語。
System.outの深淵
Javaでは、System.outを用いて標準出力を行う。このSystem.outはリファレンスを見るとPrintStream型の変数であることがわかる。PrintStreamは任意のOutputStreamをラッピングして、表示を簡単にするための機能（printlnとか）を提供する出力ストリームだ。つまり、内部になんらかのOutputStreamを保持していることになる。
では、System.outが内部に保持しているOutputStreamは一体どのようなOutputStreamなのだろうか？StandardOutputStreamのような隠れたクラスが存在しているのではないか？もしくは、デフォルトでは画面出力用のDisplayOutputStreamのようなものが用意されており、設定によってそれを切り替えて（例えば、サーブレットのときはHttpOutputStreamのようなものに）使われているのだろうか？
そのような期待を持ってSystem.outのお腹の中をさぐってみた。
まずは、JDKに付属しているSystemクラスのソースコードを見てみる。System.outは次のように定義されていた。
public final static PrintStream out = nullPrintStream();
どうやら、nullPrintStream()というメソッドによって初期化されているらしい。Systemクラスに、そんな名前の可視なメソッドはないので、おそらくprivateメソッドなのだろう。
Systemクラスの中を引き続き探してみると、やはりprivateなnullPrintStreamメソッドが見つかる。
private static PrintStream nullPrintStream() throws NullPointerException { if (currentTimeMillis() > 0) return null; throw new NullPointerException(); }
！！！！！！！！！！！！！！！！！
nullをreturnしている？？！
このメソッドの中に書かれているのは、nullをreturnするか、もしくはNullPointerExceptionをthrowする、ということだけだ。System.outはfinalで定義されているので、このコードを見ている限り、System.outがnull以外のものになる可能性はない。
しかし、もちろんそんなわけはない。System.outがnullならSystem.out.println()はぬるぽだ。
ソースコードからの解析は無理っぽいので、デバッガを使って調べてみることにしてみた。
デバッガを起動させてSystem.outの中身を覗いてみると、内部にoutという変数を保持していることがわかる。どうやらこのoutはBufferedOutputStreamのようだ。BufferedOutputStreamも、任意のOutputStreamにバッファリング機能を加える出力ストリームなので、まだその腹の中にOutputStreamを抱えているわけだ。
当然、次はBufferedOutputStreamの中を覗いてみる。そこにはやはり、変数outが用意されている。これこそが、System.outの奥深くに隠された、標準出力ストリームの真の姿！！！その正体は？！
え？FileOutputStream？
そっかー、そーだよなー。PHPでも
<?php $out=fopen('php://stdout', 'w'); ?>
とかやるもんなー。
・・・。
なんておもしろみのない結果だ・・・。
調べてみた結果、FileDescriptor.outが標準出力ストリームのファイル記述子となっているようだ。つまり、
// 最後のtrueはautoFlushをtrueにするため。 PrintStream out = new PrintStream(new BufferedOutputStream( new FileOutputStream(FileDescriptor.out)), true); out.println("Hello World!!");
とすることで、System.outと同じPrintStreamのoutを生成し、用いることができる。これを使わなければならないようなシチュエーションが思いつかないけど・・・。
ちなみに、FileDescriptor.outの正体をソースコードから探ってみると、
public static final FileDescriptor out = standardStream(1);
で定義されており、standardStreamメソッドは、
private static FileDescriptor standardStream(int fd) { FileDescriptor desc = new FileDescriptor(); desc.handle = set(fd); return desc; }
となっている。このsetメソッドを見ると、
private static native long set(int d);
となり、nativeメソッドの壁に阻まれてしまったことも併せて報告しておく。
（J2SE5での話です。他のバージョンではソースコードなどが異なるかもしれません）
Singleton 変則double-checked locking
問題の理解に誤りがあったので追記しました。(2008-07-27)
Singletonパターンを用いるときに、次のような書き方をすることがある。
public class SingletonA { // ただ一つのインスタンスを保持するためのフィールド。 private static SingletonA instance = null; // インスタンスを自由に生成させない。 private SingletonA() { } public static SingletonA getInstance() { // ただ一つのインスタンスが生成されていない場合だけ生成に進む。 if (instance == null) { // パフォーマンス低下を防ぐためにここでsynchronizedを使う。 synchronized (SingletonA.class) { // 一つ目のifを複数のスレッドがすり抜ける場合があるので再チェック。 if (instance == null) { // 一番初めにアクセスしたスレッドでのみインスタンスを生成。 instance = new SingletonA(); } } } // ただ一つのインスタンスを返す。 return instance; } }
これはdouble-checked lockingイディオムと呼ばれる手法だ。初めてこの手法を知ったときは、ifとsynchronizedの組み合わせ方が素晴らしく、なるほどなぁと思ったものだ。
しかし、実際にはこの方法はうまく動作しない。このことは先日知ったばかりなのだけど、アウトオブオーダー書き込みという現象が原因のようだ。
double-checked lockingの背景となっている理屈は申し分ありません。残念ながら、現実はまったく異なります。
（中略）
このメモリー・モデルは、いわゆる「アウトオブオーダー書き込み」を許し、それがこのイディオムの障害の主要な原因となっています。
http://www.ibm.com/developerworks/jp/java/library/j-dcl/
「double-checked lockingイディオム」と呼ばれており、完全な方法ではない。これはJavaのメモリモデルがアウトオブオーダー書き込みを許していることに起因している。
http://d.hatena.ne.jp/cxx03667/20071010/1191981355
※前者に詳細な説明が、後者に簡潔な説明と代替案がある。
さて、上記引用サイトの後者（http://d.hatena.ne.jp/cxx03667/20071010/1191981355）には様々な代替案が示されているが、どれも完全ではないようだ。そこで、double-checked lockingイディオムを改変した、変則double-checked lockingイディオムを考えてみた。
やっていることは単純で、booleanのフラグを使ってインスタンスが生成されたかをチェックしているだけだ。
public class SingletonB { // インスタンスが生成されたかどうかのフラグ。 private static boolean generated = false; // ただ一つのインスタンスを保持するためのフィールド。 private static SingletonB instance; // インスタンスを自由に生成させない。 private SingletonB() { } public static SingletonB getInstance() { // ただ一つのインスタンスが生成されていない場合だけ生成に進む。 if (!generated) { // パフォーマンス低下を防ぐためにここでsynchronizedを使う。 synchronized (SingletonB.class) { // 一つ目のifを複数のスレッドがすり抜ける場合があるので再チェック。 if (!generated) { // 一番初めにアクセスしたスレッドでのみインスタンスを生成。 instance = new SingletonB(); // インスタンスが生成されたのでフラグをtrueにする。 generated = true; } } } // ただ一つのインスタンスを返す。 return instance; } }
このようにすれば、インスタンスのメモリ領域が確保された瞬間にそのinstanceフィールドが非nullになっても、generatedフィールドはfalseのままなので大丈夫というわけだ。
JDK1.5以上であっても、Singletonパターンを使う場合はdouble-checked lockingを使わない方法を考えたほうがいいみたい。
http://d.hatena.ne.jp/skirnir/20080705/1215241339
などとも述べられているdouble-checked lockingイディオムだが、このような改変を加えることで使えないだろうか。
追記
問題の理解を誤っていた。
// 一番初めにアクセスしたスレッドでのみインスタンスを生成。 instance = new SingletonB(); // インスタンスが生成されたのでフラグをtrueにする。 generated = true;
の部分の1行目よりも先に2行目が実行されてしまうこともあるようだ。これではSingletonBはうまく機能しない。
しかし、この部分を次のように書き換えるとどうなるのだろう？最適化が行われるとは言え、これならインスタンス生成が行われてからしかgeneratedをtrueにできないように思える。
public class SingletonC { private static boolean generated = false; private static SingletonC instance; private SingletonC() { } // trueを返すメソッド。 private boolean getTrue() { return true; } public static SingletonC getInstance() { if (!generated) { synchronized (SingletonC.class) { if (!generated) { instance = new SingletonC(); // インスタンスが生成されてからしかgetTrueは実行できないのでは？ generated = instance.getTrue(); } } } return instance; } }
私の知識ではこれがうまくいくのかわからないのだが、このようにしても実行順序が入れ替わるようなことが起こり得るのだろうか？
PHPでセッションを完全に破棄する方法
PHPでセッションを破棄する方法について、きちんと解説されたものが見つからなかったので書いておく。
まず、PHPでセッションを破棄する方法自体はPHPのマニュアルの載っている。↓の部分だ。
<?php // セッション変数を全て解除する $_SESSION = array(); // セッションを切断するにはセッションクッキーも削除する。 // Note: セッション情報だけでなくセッションを破壊する。 if (isset($_COOKIE[session_name()])) { setcookie(session_name(), '', time()-42000, '/'); } // 最終的に、セッションを破壊する session_destroy(); ?>
問題は、このコードについてまともな説明がされていないことだ。よくわからないままに使っている人も多いように思える。例えば「PHP セッション 破棄」ではてなダイアリーを検索すると、次のような記事がヒットする。
これでセッションを破棄できるみたい。
http://d.hatena.ne.jp/purazumakoi/20071017/1192613461
$_SESSION = array();でブラウザ内で持っているパラメタを消して、
session_destroy();でサーバ内の/tmpとかに保存されてる実ファイルを消すといったイメージだろうか
もしかして
$_SESSION = array();
が正解？？？まあ、session_destroyすればいいだけの話なんだけどさ。。。
http://d.hatena.ne.jp/kidd-number5/20070312/1173691586
これらは大きな間違いを犯してしまっている。
セッションの仕組みをスポーツクラブの会員に例えてみよう。会員はクライアント、スポーツクラブはサーバだ。スポーツクラブは会員に会員番号与え、その会員番号の書かれたカードを発行する。スポーツクラブ側では、その会員についての情報（名前、年齢、電話番号など）を、会員番号に関連付けて保存している。
この場合、会員番号がセッションID、会員カードがブラウザに記録されているクッキー、スポーツクラブが所持している会員についての情報がセッション変数ということになる。
もしこのスポーツクラブを辞めることになったら、
- スポーツクラブの所持する会員の情報を破棄する
- 会員カードを破棄する
- その人の会員番号を無効なものとする
もし三つのすべてを行わずに、例えば2だけを行った状況を考えてみると、その人のカードを偽造した別の誰かがやってきたら、スポーツクラブ側は本人だと思って受け入れてしまうだろう（セッションで考えると、これはセッションハイジャックという攻撃になる）。
では、このスポーツクラブの例を交えながら処理の中身を見てみよう。
まず初めに、
<?php // セッション変数を全て解除する $_SESSION = array(); ?>
についてだが、これはセッション変数の破棄を行っている。これは、「スポーツクラブの所持する会員の情報を破棄する」に対応する。
PHPではセッション変数は連想配列の形で保持されている。array()は空の配列を生成するので、セッション変数を表す連想配列$_SESSIONは初期化されたことになる。参照をなくした元々の$_SESSIONの中身は、ガベージコレクションによって解放される。
次に、
<?php // セッションを切断するにはセッションクッキーも削除する。 // Note: セッション情報だけでなくセッションを破壊する。 if (isset($_COOKIE[session_name()])) { setcookie(session_name(), '', time()-42000, '/'); } ?>
についてだが、これはクライアントのブラウザにクッキーとして記録されているセッションIDの破棄を行っている。これは「会員カードを破棄する」に対応する。
セッションIDはクッキーで管理する場合と、POSTパラメータなどで管理する場合があるが、クッキーで管理する場合はそれを破棄しないと、クライアントのブラウザにセッションIDが残ったままになってしまう。
session_name()は、セッションID名を返す関数だ（初期状態では、セッションID名は'PHPSESSID'という文字列になっている。つまり、session_name()の戻り値は'PHPSESSID'となる）。クッキーには、PHPSESSID=1ab6309dのような形で値が記録されている。この場合、1ab6309dがセッションIDだ。サーバはこのセッションIDによって、誰からアクセスされたのかを判別している（この仕組みをセッションという）。
つまりここでやりたいのは、ブラウザのクッキーに記録されているPHPSESSID=1ab6309dを破棄するということだ。最初のif文は、PHPSESSIDという名前でクッキーが記録されているかを調べ（セッション管理にクッキーを用いていない場合はここでfalseとなり、ifの中に入らない）、ifの中に入った場合はPHPSESSIDというクッキーを破棄する。
setcookie()はクッキー変数を設定する関数だ。
一つ目の引数は、クッキー変数名（今はセッションIDを表すPHPSESSID）だ。
二つ目の引数は、そのクッキー変数に設定する値だ。これはどうせ破棄する変数なので何でもいい。何でもいいので''になっている。
三つ目のtime()-42000はクッキーの期限を設定している。ここで設定した時刻になればクッキー変数をブラウザが破棄してくれる。値は、1970年1月1日0時0分0秒（この時刻をエポックという）からの経過秒数で指定することになっている。
time()はエポックからの経過秒数を返す関数だ。もしここにtime()を入れれば、期限は今この瞬間、ということになる。これでも即座にクッキーが破棄されるだろうが、安全のために42000秒前に設定しているのだろう。別にtime()-1000だろうが、time()-100000だろうが同じように動作すると思われる。
四つ目の引数はあまり気にする必要はないかもしれない。もしwww.example.comというドメインのサイトを所持しているとして、そのドメイン下の全体に対してクッキーを設定するには'/'と設定すればいい。www.example.com/test/というディレクトリ下にだけクッキーを有効としたい場合は'/test/'と設定する。セッションをサイト全体で管理しているなら'/'としておけばいい。
最後に、
<?php // 最終的に、セッションを破壊する session_destroy(); ?>
だが、これはサーバ側での、セッションIDの破棄だ。これは「その人の会員番号を無効なものとする」に対応する。
サーバは与えられたセッションIDに対応したセッション変数を読み込み、$_SESSIONとして利用できるようにする。このsession_destroyを行わなければ、たとえセッション変数を破棄し、セッションIDのクッキーを破壊したとしても、別の誰かが1ab6309dというIDでアクセスしてきたならば、その人になりすませるということだ。
session_destroy()を行うことで、もし誰かが1ab6309dでアクセスしてきても、そんなIDの人はいませんよ、ということになる。
なお、session_unset()を使うように説明しているページが多く見つかるが、現在の$_SESSIONを用いる書き方をしている場合、session_unset()を使ってはいけない。
また、unset($_SESSION)などもしてはいけない。これをすると、セッション変数を格納する連想配列が消えてしまうことになり、セッション変数を登録できなくなってしまう。
セッション変数全体ではなく、あるセッション変数を消去したい場合にのみ、unset($_SESSION['セッション変数名'])を用いる。
質問サイトの良回答にすら、このような間違いがあるので注意が必要だ。
$_SESSIONそのものを消し去ってしまいたい場合は、
http://oshiete1.goo.ne.jp/qa3224862.html
unset($_SESSION);
の代わりに
session_unset();
をコールする必要があります。
このようなことをしてはいけない。
5分でわかるオブジェクト指向
プログラミングを勉強していて、オブジェクト指向でつまる人は多い。その理由は、実際のプログラミングでどのようにオブジェクト指向を使うかという、わかりやすい例が示されていないからだと思う。この記事では、必要最小限の実例でオブジェクト指向の使い方を説明する。
※ この記事はクラス、メソッド、フィールド、コンストラクタ、継承など、一度は勉強したけれど、オブジェクト指向がいまいちよくわからない、どのように使っていいのかわからないという人を対象としています。なお、言語はJavaで書いています。
生徒一覧、社員データベースなど、人のデータを扱うことは多い。ここでは、極力単純化して、姓（familyName）と名（firstName）と年齢（age）しかデータを持たないPersonクラスを考えてみよう。
Personのフルネームを取得することは非常に多い。毎回、姓、名と並べて表示するプログラムを書くよりも、フルネームを返すメソッドgetFullNameをPersonクラスに作っておいた方がよさそうだ。
でも、日本人なら姓、名の順のフルネームを書くけど、アメリカ人は名、姓の順にフルネームを書く。しかたがないのでJapanesePersonとAmericanPersonの二つのクラスを作成しよう。
JapanesePersonとAmericanPersonは、getFullNameメソッド以外の部分は共通のはずだ。同じことを2回書くのは面倒（変更があった場合に片方だけ直し忘れるなど、保守性の問題もある）なので、共通部分はPersonクラスで作ってしまい、JapanesePersonとAmericanPersonではPersonクラスを継承してgetFullNameメソッドだけを作ろう。
しかし、これだとPersonを継承したクラスにgetFullNameメソッドが作られるかは、それを作る人次第だ。Personを継承したクラスではgetFullNameメソッドを持つことを強制したい！！
どうするか。Personには、getFullNameの振る舞い（姓、名なのか、名、姓なのか）は書けない。書けるのは、Stringでフルネームを返すgetFullName()というメソッドがあることだけだ。中身がない（振る舞いを記述しない）メソッドは作れないのか。
このような、中身のないメソッドを抽象メソッド（abstractメソッド）と呼ぶ。
public abstract String getFullName();
というように書く。
抽象メソッドを持つクラスは抽象クラス（abstractクラス）として定義しなければならない。classの前にabstractをつければいい。抽象クラスのインスタンスは生成することができない（new Personができない）。抽象メソッドが呼ばれたときに困ったことになるからだ。
さて、これが今やりたいことだ。これに従って作ったプログラムが↓だ。上の説明は最小限のものなので、ソースコードをよく読んで理解してほしい。特にカプセル化とポリモーフィズムは重要だ（この二つは文章で説明するよりも、コードを見た方がわかりやすい）。
// 姓、名、年齢を持ったクラスPerson。getFullNameメソッドでフルネームを取得できる。 // フルネームを姓、名の順に書くか、名、姓の順に書くかは国によって違うため、 // getFullNameメソッドは抽象メソッドとして定義しておき、子クラスで実装する。 abstract class Person { // フィールドはpublicにしない。これはフィールドに直接アクセスできないようにするため。 // フィールドへのアクセスはアクセサメソッド（getter、setter）を用いて行う。（カプセル化） // 今回はフィールド子クラスからアクセスする必要があるので、privateではなくprotectedにする。 protected String firstName; // 姓 protected String familyName; // 名 protected int age; // 年齢 public Person(String firstName, String familyName, int age) { this.firstName = firstName; this.familyName = familyName; this.age = age; } // アクセサメソッド（getter）を使ってフィールドの値を得る。 public String getFirstName() { return this.firstName; } // アクセサメソッド（setter）を使ってフィールドの値を書き換える。 public void setFirstName(String firstName) { this.firstName = firstName; } public String getFamilyName() { return this.familyName; } public void setFamilyName(String familyName) { this.familyName = familyName; } public int getAge() { return this.age; } // setterで不正な値をチェックして対処する。 // カプセル化していなければ、毎回チェックしなければならない。 public void setAge(int age) { if (age >= 0) { this.age = age; } else { // 負の値が与えられた場合は0歳にする。 this.age = 0; } } // getFullNameは引数なしでStringを返す、ということだけを定義する。 // 中身の実装に関しては、子クラスに任せる。 public abstract String getFullName(); } // 日本人を表すクラス。getFullNameは姓、名の順に並べた文字列を返す。Personクラスを継承。 class JapanesePerson extends Person { // superで親クラスのコンストラクタを呼び出す必要がある。 public JapanesePerson(String firstName, String familyName, int age) { super(firstName, familyName, age); } // 姓、名の順に並べた文字列を作成して返す。 public String getFullName() { return this.familyName + " " + this.firstName; } } //アメリカ人を表すクラス。getFullNameは名、姓の順に並べた文字列を返す。Personクラスを継承。 class AmericanPerson extends Person { public AmericanPerson(String firstName, String familyName, int age) { super(firstName, familyName, age); } // 名、姓の順に並べた文字列を作成して返す。 public String getFullName() { return this.firstName + " " + this.familyName; } } // mainメソッドを持ったクラス。 public class ObjectOrientedProgramming { public static void main(String[] args) { // 子クラスのインスタンスは親クラス型変数に代入できる。 // 子クラスは親クラスのメソッドをすべて持っているので // 親クラスのように振舞うことができる。 Person aoi = new JapanesePerson("優", "蒼井", 23); Person tom = new AmericanPerson("Tom", "Cruise", 46); // アクセサメソッド（setter）を用いてフィールド値の設定を行う。（カプセル化） aoi.setAge(22); // アクセサメソッド（getter）を用いてフィールド値を取得する。（カプセル化） System.out.println(aoi.getAge()); System.out.println(); // Person型変数の振る舞いはその実体によって決まる。（ポリモーフィズム） // aoiの実体はJapanesePerson、tomの実体はAmericanPerson。 System.out.println(aoi.getFullName()); System.out.println(tom.getFullName()); System.out.println(); // JapanesePersonとAmericanPersonの入り混じった、Person型配列も作れる。 Person[] persons = { new JapanesePerson("駿", "宮崎", 67), new AmericanPerson("Steven", "Spielberg", 61), new JapanesePerson("俊二", "岩井", 45) }; // JapanesePersonもAmericanPersonも同じPersonとして扱える。 // ポリモーフィズムで、それぞれの実体から適切にgetFullNameメソッドが呼ばれる。 for (int personIndex = 0; personIndex < persons.length; personIndex++) { // 実体がJapanesePersonなら姓、名の順に、AmericanPersonなら名、姓の順に表示。 System.out.println(persons[personIndex].getFullName()); } } }
実行結果は次のようになる。
オブジェクト指向の三本柱はよく、カプセル化、継承、ポリモーフィズムだと言われる。でも、本当に大事なのは、それらを使って実現できる抽象化だと思う。
上のプログラムは、その抽象化を簡単な例で示そうとしたものだ。このプログラムが、少しでもオブジェクト指向の理解に役立てば幸いだ。
ハッシュは本当に遅いのか？いや、遅くない（反語）
この記事を簡潔にまとめた記事「ハッシュは二分木（ツリー）より速い」を掲載しました。（2008-08-04）
ハッシュと二分木（ツリー）*1では普通はハッシュの方が速いとされる（ハッシュは挿入、参照、削除の時間計算量がO(1)、二分木はO(log N)）。しかし、ハッシュは動作が複雑なため、実際はあまり二分木と速度が変わらないとも言われる。
それをC++で検証した記事を見つけた。結論は、二分木よりハッシュの方が遅いというものだ。
ハッシュは本当に速いのか? - S34
http://www.s34.co.jp/cpptechdoc/article/hash/
ハッシュは本当に遅いのか - 山に生きる
http://d.hatena.ne.jp/pmoky/20050502/1114966341
では、JavaのHashSetとTreeSet（またはHashMapやTreeMap）でも同じことが起こるのだろうかと思い、検証してみた。
データの数Nを、10000, 20000, ... , 640000と変化させて、そのときにかかったデータの挿入、参照、削除の時間を調べてみる。当然、データ数が多くなると繰り返しもそれだけ行われているわけで、1個あたりどれだけかかったのか、ということが重要なのでNで割った時間も計算する。
その結果が↓だ。
HashSetの結果
(挿入) hash(10000): 15 [ms], 1.5265906999999999 [ms/elements]
(参照) hash(10000): 6 [ms], 0.687322 [ms/elements]
(削除) hash(10000): 15 [ms], 1.5254732 [ms/elements]
(挿入) hash(20000): 13 [ms], 0.66115945 [ms/elements]
(参照) hash(20000): 7 [ms], 0.3906921 [ms/elements]
(削除) hash(20000): 10 [ms], 0.5364369 [ms/elements]
(挿入) hash(40000): 29 [ms], 0.7438585 [ms/elements]
(参照) hash(40000): 20 [ms], 0.522028625 [ms/elements]
(削除) hash(40000): 32 [ms], 0.8135810499999999 [ms/elements]
(挿入) hash(80000): 105 [ms], 1.3176360375 [ms/elements]
(参照) hash(80000): 93 [ms], 1.172062375 [ms/elements]
(削除) hash(80000): 125 [ms], 1.5711808250000001 [ms/elements]
(挿入) hash(160000): 163 [ms], 1.02348553125 [ms/elements]
(参照) hash(160000): 110 [ms], 0.690080725 [ms/elements]
(削除) hash(160000): 132 [ms], 0.82666058125 [ms/elements]
(挿入) hash(320000): 1011 [ms], 3.16175571875 [ms/elements]
(参照) hash(320000): 224 [ms], 0.700526359375 [ms/elements]
(削除) hash(320000): 263 [ms], 0.82408169375 [ms/elements]
(挿入) hash(640000): 2686 [ms], 4.198237834375 [ms/elements]
(参照) hash(640000): 481 [ms], 0.7527174375 [ms/elements]
(削除) hash(640000): 553 [ms], 0.86452459375 [ms/elements]
TreeSetの結果
(挿入) tree(10000): 14 [ms], 1.4922847 [ms/elements]
(参照) tree(10000): 15 [ms], 1.5876599 [ms/elements]
(削除) tree(10000): 24 [ms], 2.4928586999999998 [ms/elements]
(挿入) tree(20000): 25 [ms], 1.2912255499999998 [ms/elements]
(参照) tree(20000): 38 [ms], 1.9112065999999999 [ms/elements]
(削除) tree(20000): 42 [ms], 2.1247393 [ms/elements]
(挿入) tree(40000): 54 [ms], 1.368253525 [ms/elements]
(参照) tree(40000): 109 [ms], 2.7254651 [ms/elements]
(削除) tree(40000): 106 [ms], 2.664130475 [ms/elements]
(挿入) tree(80000): 117 [ms], 1.46314685 [ms/elements]
(参照) tree(80000): 313 [ms], 3.914603675 [ms/elements]
(削除) tree(80000): 303 [ms], 3.7911208 [ms/elements]
(挿入) tree(160000): 334 [ms], 2.09372804375 [ms/elements]
(参照) tree(160000): 718 [ms], 4.49078025625 [ms/elements]
(削除) tree(160000): 720 [ms], 4.50348263125 [ms/elements]
(挿入) tree(320000): 982 [ms], 3.068847609375 [ms/elements]
(参照) tree(320000): 1715 [ms], 5.360803540625 [ms/elements]
(削除) tree(320000): 1710 [ms], 5.346012028125 [ms/elements]
(挿入) tree(640000): 2017 [ms], 3.152671115625 [ms/elements]
(参照) tree(640000): 4580 [ms], 7.156315868750001 [ms/elements]
(削除) tree(640000): 4120 [ms], 6.437939825 [ms/elements]
おおおおおおおおお！！！！！
HashSetの方が速いじゃないか！！（参照、削除は）Nの影響も受けていないように見える（つまりO(1)）。一方TreeSetはNの増加に従って遅くなっている。その時間もO(log N)っぽい。教科書通りの結果だ。
とりあえずJavaではHashSetの方が速いようだ。
おいおい、ちょっと待った。HashSetだって挿入にかかった時間は長くなっていってるじゃないか。
そんな声が聞こえてきそうだか、これはHashSetの動作原理を考えれば当たり前だ。HashSetはデフォルトでは初期容量16、負荷係数0.75のハッシュテーブルを作成する。つまり、ハッシュテーブルのサイズが16で、ハッシュテーブルに16*0.75=12個分を超えるのデータが挿入されたら、ハッシュテーブルは2倍のサイズ（この場合は32）に拡張される。このときに、配列の生成、ハッシュの再計算などのコストが発生するわけだ。
この結果、「データ数が多い→テーブルの拡張がたくさん行われる→挿入は遅くなる」、ということになる。
挿入が遅いんじゃ、結局HashSetも大して変わらないんじゃないか。
そんなことはない。ハッシュテーブルの拡張を行わないようにするには次のようにすればいい。
Set set = new HashSet<String>(n * 4 / 3 + 1);
これで、ハッシュテーブルの初期容量がn*4/3に設定される。4/3をかけるのは、負荷係数を考慮してのことだ。こうしておけば、n個のデータが一切ハッシュの衝突を起こさずにハッシュテーブルに格納されたとしても、容量*0.75がnを超えることはない（4/3*0.75=1なので。+1してるのは、n*4/3が割り切れず切り捨てられたときのため）。
さて、ではこの設定(hash2とする）でHashSetの時間を計測してみると・・・。
HashSetの結果（テーブル拡張なし）
(挿入) hash2(10000): 12 [ms], 1.2928179 [ms/elements]
(参照) hash2(10000): 5 [ms], 0.5780344000000001 [ms/elements]
(削除) hash2(10000): 8 [ms], 0.8285130999999999 [ms/elements]
(挿入) hash2(20000): 12 [ms], 0.6072420000000001 [ms/elements]
(参照) hash2(20000): 8 [ms], 0.40608515 [ms/elements]
(削除) hash2(20000): 10 [ms], 0.506475 [ms/elements]
(挿入) hash2(40000): 24 [ms], 0.6130457749999999 [ms/elements]
(参照) hash2(40000): 20 [ms], 0.5092407 [ms/elements]
(削除) hash2(40000): 30 [ms], 0.759384225 [ms/elements]
(挿入) hash2(80000): 58 [ms], 0.7295305750000001 [ms/elements]
(参照) hash2(80000): 56 [ms], 0.7091613625 [ms/elements]
(削除) hash2(80000): 64 [ms], 0.8034331124999999 [ms/elements]
(挿入) hash2(160000): 119 [ms], 0.7443561249999999 [ms/elements]
(参照) hash2(160000): 147 [ms], 0.9210598 [ms/elements]
(削除) hash2(160000): 132 [ms], 0.82502280625 [ms/elements]
(挿入) hash2(320000): 253 [ms], 0.791681446875 [ms/elements]
(参照) hash2(320000): 224 [ms], 0.7015600093750001 [ms/elements]
(削除) hash2(320000): 272 [ms], 0.8514306624999999 [ms/elements]
(挿入) hash2(640000): 529 [ms], 0.8271747875 [ms/elements]
(参照) hash2(640000): 475 [ms], 0.7435184671875 [ms/elements]
(削除) hash2(640000): 567 [ms], 0.8864233281250001 [ms/elements]
速い！！なんて理想的な結果なんだ・・・。
こう考えると、一番最初に上げた二つの記事では、ハッシュへの挿入、削除を合計して時間を計算しているので、挿入時のハッシュテーブル再構築の負荷がハッシュのパフォーマンスを低下させているように思える（もしかするとC++固有の特性（最適化の結果、ライブラリの設計ミスなど）なのかもしれないが）。
結局、初期容量を的確に設定してやれば、時間計算量は教科書どおりハッシュはO(1)、二分木はO(log N)になるみたいだ（↓横軸はlogスケール。Hashは横ばい、Treeは直線的に増加しているのがわかる）。
結論。やっぱりハッシュは二分木よりも速い。
最後に、今回作成したプログラムを載せておく。
import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.TreeSet; public class HashVsTreeMain { public static void main(String[] args) { String typeName; typeName = "hash"; //typeName = "tree"; //typeName = "hash2"; for (int n = 10000; n < 1000000; n *= 2) { // setを生成。 Set<String> set; if ("hash".equals(typeName)) { // HashSetを生成。 set = new HashSet<String>(); } else if ("tree".equals(typeName)) { // TreeSetを生成。 set = new TreeSet<String>(); } else { // HashSetを、データ挿入時にテーブルの拡張が行われないように // 初期容量を設定して生成。 set = new HashSet<String>(n * 4 / 3); } // 挿入、参照、削除にかかる時間を表示。 time(set, typeName, n); } } static void time(Set<String> set, String typeName, int n) { // 重複のないn個のランダムな文字列を生成して、stringListに格納する。 List<String> stringList = new ArrayList<String>(); Set<String> strings = new TreeSet<String>(); while (strings.size() < n) { strings.add(getRandomString(8)); } for (String string : strings) { stringList.add(string); } // 時間を計るための変数begin, endを生成。 long begin; long end; // 挿入にかかる時間を測定して表示。 begin = System.nanoTime(); for (String string : stringList) { set.add(string); } end = System.nanoTime(); System.out.print("(挿入) "); show(typeName, begin, end, n); // 挿入順に取り出すと平均的なパフォーマンスが得られない場合があるので // 一応stringListをシャッフルしておく。 Collections.shuffle(stringList); // 参照にかかる時間を測定して表示。 begin = System.nanoTime(); for (String string : stringList) { set.contains(string); } end = System.nanoTime(); System.out.print("(参照) "); show(typeName, begin, end, n); // 削除にかかる時間を測定して表示。 begin = System.nanoTime(); for (String string : stringList) { set.remove(string); } end = System.nanoTime(); System.out.print("(削除) "); show(typeName, begin, end, n); // 空行を表示。 System.out.println(); } // 長さlengthのランダムな文字列を生成して返す。 static String getRandomString(int length) { if (length > 0) { char[] chars = new char[length]; int digit; for (int charIndex = 0; charIndex < chars.length; charIndex++) { digit = (int) (26 * Math.random()); chars[charIndex] = (char) ('a' + digit); } return new String(chars); } else if (length == 0) { return ""; } else { throw new IllegalArgumentException(Integer.toString(length)); } } // 結果を表示 static void show(String type, long begin, long end, int n) { System.out.print(type); System.out.print("("); System.out.print(n); System.out.print("): "); System.out.print((end - begin) / 1000000); System.out.print(" [ms], "); System.out.print(((end - begin) / 1000.0) / n); System.out.println(" [ms/elements]"); } }
※実行環境: Windows XP, Pentium4 3.33GHz, JRE5.0
*1:JavaのTreeSet、TreeMapが用いているのは、正確にはRed-Black treeというアルゴリズムらしい。
