.NET & Control > ハッシュ(Hash)値を活用しよう!
のぶ亭『プログラミングの相談窓口』 … 様々なプログラミング問題を個別対応致します |
ハッシュ(Hash)値を活用しよう!
文字列などの可変長なデータが複数あった場合を想像してみましょう。
- "Windowsプログラミング .NET Framework C#、VB [、個人レッスン] "
- "サンプルで学ぶ『カスタムコントロールの基本と作り方』 Visual Studio 2005/2008 『C#/VB』"
- "カスタムコントロール入門(Visual Studio 2008 C#/VB)"
- "「実践 データベース プログラミング入門講座」 Visual Studio 2008 .NET C# & ADO.NET"
- "「実践 データベース プログラミング入門講座」 詳細"
- " .NET GDI+ グラフィック入門(Visual Studio 2008)『C#/VB』"
- "プログラムのデスクトップ・アイコン作成方法と登録方法(Visual Studio 2008)"
- "(動画)リモートデバッグ(Remote Debug) セットアップと利用方法 (Visual Studio 2008)"
- "初心者が効率よくプログラミングを学ぶための入門講座 C#/VB"
文字列の部分検索ではなく、この文字列群から一致する文字列を見つける場合です。
この程度の文字列数であれば文字列として比較しても問題はありません。
これが、何万、何十万という文字列の中から見つけるとすればどうでしょう。さらに、見つける文字列も同様の数だとすれば、文字列比較は効率が悪い(遅い)のです。
ハッシュ値(コード)は、オブジェクトの基本
intでもStringでもObjectクラスがベースです。
そして、Objectクラスには GetHashCode() メソッドが標準装備されています。また、必要に応じて、オブジェクト独自のGetHashCode() メソッドが容易されている場合もあります。
この GetHashCode() メソッドはハッシュ関数とも呼ばれ、対応オブジェクトのハッシュ値(コード)int型を返します。
Stringオブジェクトは、文字列以外にもハッシュ値を持っていると考えることができます。
ハッシュ値(コード)は、ほぼユニーク(一意)な値
ハッシュ値とは、可能な限りユニーク性のある数値です。
はじめの文字列比較の場合、文字列同士を比較するのではなく、ハッシュ値(int型)で比較すれば高速に行うことができます(逆にこれ以上の方法はありません)。
気をつけなければならないのは、ハッシュ値は完全にユニークな値ではないということです。
そのため、異なる文字列でも同じ値になるケースが存在するということを考慮しておかなければ、プログラムとしては非常に危険です。
回避策の方法としては
- まず文字列群のハッシュテーブル群を作成します。
- ハッシュテーブルより検索します。
ハッシュテーブルに同一値が二つ以上存在していないことを確認します。
もし、存在していた場合、該当の文字列だけを文字列比較します。 - 先頭から探索すると効率が悪いため、ハッシュテーブルをソートして、2分岐探索アルゴリズムを用いて行います。そうすると同一のハッシュ値が存在するかどうかは、前後のハッシュ値を確認すれば簡単に判断することができます。
実際のアプリケーションでは(1万件程度のデータ)全てがユニークでした。が、それはたまたまだと理解しています。
同じ値(文字列)であれば、同じハッシュ値になります。これを利用すれば、重複のチェックを行うこともできます。.NET Framework Class Libraryでは、Hashtable クラスが用意されていますので是非活用してください。