[Tools.h++] 13.7 オブジェクトを見つける方法
次の点に留意することにより、手間を省くことができます。ターゲットを等しいかどうか調べるときは、ターゲットの関数ではなく、コレクション内のオブジェクトの仮想関数が呼び出されます。
次のコード例は、この点を分かりやすく示したものです。
SortedCollection sc; RWCollectableString member; sc.insert(&member); RWCollectableString target; RWCollectableString* p = (RWCollectableString*)sc.find(&target);
この例では、target の仮想関数ではなく、コレクション RWCollectableString 内の member の仮想関数が呼び出されます。言い換えると、次のようになります。
member.compareTo(&target); //これが呼び出される target.compareTo(&member); //これではない
13.7.1 ハッシング
ハッシングは、コレクションの中からオブジェクトを検索する効果的な手法です。ハッシングを使用するすべてのコレクションクラスは、同じ一般的戦略に従います。まず、ターゲットのメンバ関数 hash() が呼び出され、ハッシュ表内に適切なバケットを見つけます。バケットは一重リンクリストとして実装されています。バケット内のすべてのメンバが同じハッシュ値を持つので、バケットを線形探索を行って完全な一致を見つけます。これは、バケットの各メンバを引数に持つ候補者 (上記参照) のメンバ関数 isEqual() を呼び出して行います。TRUE を返す最初の引数が目的のオブジェクトです。isEqual() に対して true の値を持つ 2 個のオブジェクトが異なるハッシュ値を持つようなクラスを設計しないように注意してください。このアルゴリズムは、そのようなオブジェクトでは失敗します。
一般に、多くのハッシュアルゴリズムの複雑さに加え、このハッシュおよび線形探索の組み合わせのため、ハッシュコレクション内のオブジェクトの順序は意味を成しません。そのため、関数 apply() または反復子がハッシュ表を走査するとき、オブジェクトはランダム順で検査されているようにみえます。