【第六回】C#におけるCollectionsの基本のキを理解する【Dictionary<​TKey,​TValue>】

はい第六回です。
第五回目はこちらです。
今回は実際にC#のプログラミングで連想配列を使ってみたいと思います。
ただし例のごとく、僕のプログラミング歴は約3ヶ月と短いので、間違っている可能性山のごとしです。
その点だけご留意ください。

連想配列とはなんぞ

配列は普通、添え字(インデックスのこと)に数字を使いますよね。
連想配列の場合、この添え字に特定の名前をつけることができます
ただそれだけです(たぶん)。
で、「ハッシュテーブル」という言葉を聞いたことがある方もいるかなと思います。
連想配列とハッシュテーブルは何が違うのかと言えば、連想配列を実現するための仕組みの一つがハッシュテーブルなのです。
例えばこれから紹介するDictionary<​TKey,​TValue>にもハッシュテーブルが使われています。
が、全ての言語の連想配列で必ずハッシュテーブルが使われているかと言えば、そうでないようです(ハッシュテーブル以外でも連想配列は実装できるのですね)。

ハッシュテーブルは高速

Dictionary<​TKey,​TValue> Classを見てみましょう。

原文:

The Dictionary<TKey,TValue> generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key.

翻訳:

ジェネリッククラスのDictionary<TKey,TValue>を用いると、各キーから各値への関連付けをおこなうことができます。辞書へのそれぞれの追加は、値と、値に関連付けられたキーによって構成されます。

要は連想配列として使うことができますよーということですね。
そして原文は以下のように続きます。

Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey,TValue> class is implemented as a hash table.

翻訳:

Dictionary<TKey,TValue>はハッシュテーブルとして実装されているため、キーを使って値を取得するのは非常に高速です(具体的には、O(1)に近い速さです)。

ここでO(1)という用語が出てきましたね。
これが一体なにを意味するのか、僕は初め全くわかりませんでした。
ぐぐってみると、どうも数学の用語のようです。
僕は数学なんて全くの門外漢であり、小卒並の算数知識しかありません(冗談ではなく、本当に)。
そこでさらにグーグル先生を頼り、O(1) 操作という書き込みのあるサイトでこんな説明を見かけました。

引用:

O(1)は、個数によらず一定の時間や手間がかかる操作、という意味です。
O(n)は、個数(n)に比例して時間や手間がかかる操作、という意味です。

引用終わり

つまり、Dictionary<TKey,TValue>はハッシュテーブルを用いているため、「個数によらず一定の時間や手間がかかる操作」に近い速度でキーから値を取得できるのですね。
これの素晴らしさは一見すると理解しにくいかもしれませんので、例え話をしてみます。

家族写真を検索してみる

あなたはすでに結婚していて、大好きな家族との思い出を記録するのが趣味です。「家族写真」フォルダには、なんと100万ものファイルが保存されています
この「家族写真」フォルダの中から手動で目的の写真を見つけようと思ったら、それはもう大変ですよね。検索機能を使っても、結構な時間がかかることが予想されます。
ところがO(1)に近い速さで検索できるハッシュテーブルを用いていたなら、写真がいくら増えようとも、操作にかかる時間も手間も常に一定なのです。
これってすごくないですか?
僕はちょっぴり興奮するくらい感動を覚えましたよ。
ただし、個数が少ない場合は、むしろ普通に検索するより遅いのかなー? なんてのは思いましたが(検証してないのでわかりません)。

注*原文に“The speed of retrieval depends on the quality of the hashing algorithm of the type specified for TKey. ”とあるように、実際の検索速度はTKeyで指定された型のハッシュアルゴリズムの品質に依存するようです。全ての型で一定の速度がでるとは限らない、ということなのですね。

順序は保証されない

これまで紹介してきたList<T>やStack<T>などは、値の保存されている順番が大切でしたよね。
たとえばStack<T>を使っていて、Push(T)した順番通りにPop()されなかったらスタックの意味がなくなっちゃいます
これはList<T>やQueue<​T>でも同じことです。
これらのクラスは要素の順番が保証されていなければならないし、また実際に保証されています(プログラムにバグがない限りね)。

ところがDictionary<​TKey,​TValue>はどうでしょうか。
連想配列を使いたい場合、順序を保証する必要が普通あるでしょうか?
答えは、保証する必要はない、です。
キーで値にアクセスするのですから、値が格納されている順序なんてどうでもいいんですね。
仮に順序を保証させたい場合、連想配列は使うべきではありません

Dictionary<​TKey,​TValue> Classも見てみましょう。

原文:

For purposes of enumeration, each item in the dictionary is treated as a KeyValuePair<TKey,TValue> structure representing a value and its key. The order in which the items are returned is undefined.

翻訳:

列挙する目的があったとして、辞書の各アイテムは、KeyValuePair<TKey,TValue>(値と、値のキーを表す構造のこと)として扱われます。アイテムが返される順番は定義されていません。

ここで大事なのは、「アイテムが返される順番は定義されていない」ということです。
つまり、例えばforeachでDictionary<​TKey,​TValue>をぶん回したとしても、どれが最初に取り出されるのかはわからない、ということなのですね。

注*でも僕が実際に試したところ、普通に追加した順で取り出されました。要素が増えると順番がへんちくりんになるんでしょうかね。よくわかりません。が、いずれにせよ、順序を保証しなければならない場合はDictionary<​TKey,​TValue>の利用を避けたほうがよいでしょう。だって「保証されない」ってはっきり書いてますからね。

とりあえず使ってみる

実は僕、この記事を書くまで連想配列を使ったことがありませんでした。
ハッシュテーブルについても偉そうに書いていますが、調べたてのことばかりです。
というわけで、ここで色々と試してみましょう。

Dictionary<string, string> dict_books = new Dictionary<string, string>();

はい、これでとりあえず、Dictionary<​TKey,​TValue>のインスタンスへの参照がdict_booksに代入されました。
Add(​TKey, ​TValue)で要素を追加できるようなので、試してみます。

dict_books.Add(“C#はじめの一冊”,”『独習C#』”);
dict_books.Add(“JavaScriptはじめの一冊”, “『JavaScript本格入門』”);
dict_books.Add(“C#の応用”, “『実践で役立つC#プログラミングのイディオム 定石&パターン』”);
dict_books.Add(“JavaScriptの応用”, “『オブジェクト指向JavaScriptの原則』”);

デバッグ画面で内容を確認してみたところ、きちんと追加されていました。

注*実際に書籍の情報で連想配列を使用するなら、ISBNコードなんかをキーとして利用するのでしょうが、まあここはお試しということで。

要素を取得する

まずは全てのキーと値を取得してみましょう。
foreachでぶん回すだけです。

foreach (var book in dict_books)
{
Console.WriteLine(“{0} : {1}”, book.Key, book.Value);
}

ここでvarと使っているのは、KeyValuePair<TKey,TValue>型のことです。
型名が長いので暗黙的に型を指定できるvarを使いました。
深い意味はありません。

全てのキーを列挙する(値は不要)場合は、こんな感じ。

foreach (var book in dict_books.Keys)
{
Console.WriteLine(book);
}

値がほしければ、KeysをValuesに変えればよいようですね。

存在しないキーを取得してみる

ふと「存在しないキーを指定した場合はどうなるのか?」という疑問が頭をもたげました。
疑問は解消せねばなりません。さっそく実験してみましょう。
foreach文を消し、代わりにこんなコードを追加してみます。

Console.WriteLine(dict_books[“スーパーハッカーツミオ君~伝説はそのとき始まった~”]);

結果は……
「System.Collections.Generic.KeyNotFoundException: ‘指定されたキーはディレクトリ内に存在しませんでした。」
はい、もうそのままのエラーですね。
存在しないキーを指定した場合は例外エラーが発生するようです。

キーや値の存在をチェックする

例外エラーは発生させたくないですよね。
try-catch構文で例外を補足してもよいのですが、Dictionary<​TKey,​TValue>にはキーや値が存在しているかどうかをチェックするメソッドが用意されています

Contains​Value(​TValue)
Contains​Key(​TKey)

この二つですね。
どちらのメソッドもブール値を返すので、事前のチェックに使えるでしょう。

キーと値を削除する

もちろん、キーと、それに関連付けられている値を削除する方法も用意されています。Remove(​TKey)です。
「あれ? 値は指定しなくていいの?」と思うかもしれませんが、キーと値は一つのペアになっているので、キーを指定するだけで値も削除できるのです。
実際、メソッドの説明の欄にはこんな一文が書かれています。
原文:

Removes the value with the specified key from the Dictionary<TKey,TValue>.

翻訳:

Dictionary<TKey、TValue>から、引数で指定されたキーと、キーに関連付けられている値を削除します。

ちなみにですが、全てのキーと値を削除したい場合はClear()を使用してください。

Dictionary<TKey,TValue>の紹介終わり

Dictionary<TKey,TValue>はこれまでに一切使ったことがなく、この記事を書くために調べたと言っても過言ではありません(そもそも連想配列自体、使ったことなかったのです)。
他のものに比べたら記事にするのにやや苦労しましたが、なんとかDictionary<TKey,TValue>の基礎はわかったかなーと思います。
みなさんはいかがでしたでしょうか?

全六回で終了

「C#におけるCollectionsの基本のキを理解する」はこれにて終了です。
全六回という短い記事でしたが、僕自身はCollectionsに対する理解が大いに深まったと思っています(プロの方から見れば「まだまだ甘いよ」と思うかもしれませんがw)。
この記事は誰かのために、というよりは自分のために書いた側面が強いので、わかりづらい部分があったらすみません。

理解できていない機能がC#にはまだたくさんあるので、こんな感じで定期的に書いていけたらいいなあと思っています。
具体的には以下の3つでしょうか。
・デリゲート(イベント)
・ラムダ式
・LINQ
どれもこれもまだ実際のプログラミングで活用できるところまで行っていないので、ぜひとも習得したいですね。
では、また。

あ、番外編で「Selecting a Collection Classを読む」を書くかもしれません。
第一回目で紹介してそのままでしたねw

フォローする