前回では2次元にキーを持つMapというものを紹介しました。
しかし、2分木を2段構成にするデータ構造でしたので、データへのアクセスにはそれなりのオーバーヘッドがあります。
今回紹介するコードはそのハッシュテーブル版です。
仕組み
まず、ハッシュテーブルの仕組みから入りましょう。
ハッシュテーブルでは格納する際にキーとなる値からなんらかの方法で格納位置を算出し、配列の該当インデックスにデータを格納します。
「なんらかの方法」というところが曖昧なのですが、これはキーとなるオブジェクトの実装に依存します。
イメージしやすい例を挙げると、伝票などをアイウエオ順に棚に格納するようなイメージです。
「ア」から始まるものは「ア」の棚に入っていますよね。その棚というだけで走査対象となるデータが一気に減ります。
ざっくり減らしたところでキーと合致するものを探すというわけです。
プログラム的には「アイウエオの棚」ではなく、配列です。そして、同じ棚に集中すると効率が悪いですから、
できるだけ均一にばらけるようにすることが望ましいですね。この配列のインデックスは
Object#hashCode()
によって返される値を利用します。
自前でオブジェクトを作った際にMapのキーとして使いたいのであればこのメソッドをオーバーライドしておく必要があります。
さて、1次元の場合は以上の通りですが、2次元となると格納する棚を2次元にしてやる必要が出てきます。
つまり、2次元配列にしてやるわけです。
その上で、1つ目のキーはX方向の位置決めに使い、2つ目のキーはY方句の位置決めに使うようにします。
こうすることで同じXのキーを持つデータは縦に並び、同じYのキーを持つデータは横に並びます。
すると、XとYを両方指定してピンポイントでデータを取り出すことも出来るうえに、
片方のキーだけ同じものを取り出すこともできます。
Mapを格納したMapの場合だと、外側のMapのキーが同じものを並べることはできますが、
内側のMapのキーが同じものを並べるのは容易ではありません。
この点、2次元Mapでは縦横無尽にデータにアクセスできるわけですね。
と、いったところでコードの解説は次回以降としましょう。
投稿日時 : 2007年9月25日 18:18