« #Script プロトタイプベース? | トップページ | メモ »

2007年1月21日 (日)

ハッシュテーブルの実装

SSCLI 2.0 の System.Collections.Generic.Dictionary のソースコードを眺めていたら、辞書 (ハッシュテーブル) が面白い方法で実装されていることに気付いた。

一般的なハッシュテーブルの実装の仕方にはオープンハッシュ (連鎖法 = chaining) とクローズドハッシュ (開番地法 = open addressing) の二つがあるが、SSCLI のソースは二つを融合したようなやり方を使っている。なんというか、クローズドハッシュの中でオープンハッシュをやっている感じ。要素を追加するたびにメモリを確保しなければならないというオープンハッシュの欠点と、衝突確率が高くなると空いているところを探すのに時間が掛かるというクローズドハッシュの欠点を両方とも解決している。

|

« #Script プロトタイプベース? | トップページ | メモ »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/169172/13601909

この記事へのトラックバック一覧です: ハッシュテーブルの実装:

« #Script プロトタイプベース? | トップページ | メモ »