バナーをクリックすれば目次に戻ります

Copyright 1999 Rogue Wave Software
Copyright 1999 Sun Microsystems, Inc.

RWHashTable

RWHashTable RWCollection RWCollectable

形式 

#include <rw/hashtab.h>
RWHashTable h ;

説明

このクラスは、RWCollectable から継承したオブジェクトの単純なハッシュテーブルです。チェーン (クラス RWSlistCollectables により実装) を使用してハッシュの衝突を解決します。重複するオブジェクトは許されます。

このクラスによって格納されるオブジェクトは、仮想関数 hash() および isEqual() を適切に定義した、抽象基底クラス RWCollectable から継承しなければなりません (RWCollectable を参照してください)。

キーと一致するオブジェクトを見つけるには、キーの仮想関数 hash() を最初に呼び出して、オブジェクトの存在するバケットを判定しなければなりません。次に、各オブジェクトに対し、キーを引数として仮想関数 isEqual() を呼び出し、そのバケットを線形探索します。TRUE を返した最初のオブジェクトを返します。

ハッシュテーブルの初期バケット数はコンストラクタで設定します。これには、デフォルト値があります。コレクション内の項目数がバケット数よりもずっと多い場合は、各バケットを線形探索するため、効率は下がります。バケット数は、メンバー関数 resize() を呼び出して変更できます。変更するためには、すべてのオブジェクトを再ハッシュする必要があります。

このクラスの反復子は、RWHashTableIterator です。

持続性

なし

例

hashtab.cpp

#include <rw/hashtab.h>
#include <rw/colldate.h>
#include <rw/rstream.h>

main(){
 RWHashTable table;
 RWCollectableDate *july
      = new RWCollectableDate(7, "July", 1990);
 RWCollectableDate *may
      = new RWCollectableDate (1, "May", 1977);
 RWCollectableDate *feb
      = new RWCollectableDate (22, "Feb", 1983);
 RWCollectableDate *aug
      = new RWCollectableDate (2, "Aug", 1966);

 table.insert(july);
 table.insert(may);
 table.insert(feb);
 table.insert(aug);

 cout << "Table contains " << table.entries() << " entries.\n";
 RWCollectableDate key(22, "Feb", 1983);
 cout << "It does ";
 if (!table.contains(&key)) cout << "not ";
 cout << "contain the key " << key << endl;

 delete july;
 delete may;
 delete feb;
 delete aug;
 return 0;
}

プログラム出力: 

Table contains 4 entries.
It does contain the key February 22, 1983

公開コンストラクタ 

RWHashTable(size_t N = RWCollection::DEFAULT_CAPACITY);

N 個のバケットを持つ空のハッシュテーブルを作成します。 

RWHashTable(const RWHashTable& t);

コピーコンストラクタ。テーブル t のシャローコピーとして新しいハッシュテーブルを作成します。作成されたテーブルは、コピー元のテーブルと同じ数のバケットを持ちます。したがって、メンバーは将来も再ハッシュする必要がありません。

公開演算子 

void
operator=(const RWHashTable& t);

代入演算子。自分自身に t のシャローコピーを設定します。両方のテーブルはバケット数が同じになります。したがって、メンバーを将来とも再ハッシュする必要はありません。 

RWBoolean
operator==(const RWHashTable& t) const;

自分自身と t が同じ要素数を持っていて、自身の各キーに対して isEqual である対応キーが t 内に存在する場合に TRUE を返します。 

RWBoolean
operator<=(const RWHashTable& t) const;

自分自身が t の部分集合である場合、つまり自身のすべての要素について、t 内に isEqual な要素がある場合に TRUE を返します。標準 C++ ライブラリが存在する状態で RWBTree から継承する場合、この演算子を変更し、明示的に関数を呼び出すことをお薦めします。C++ の多重定義による解決方法では、継承されたクラスメンバーを対象とする、標準ライブラリが提供する大域演算子を選択します。これらの大域定義は、部分集合関係のような半順序付けには適していません。 

RWBoolean
operator!=(const RWHashTable&) const;

上記、operator==() の結果の否定を返します。

メンバー関数 

virtual void
apply(RWapplyCollectable ap, void*);

クラス RWCollection から再定義した関数。コレクション内の各メンバーに対して ap が指す関数を呼び出します。コレクションハッシュの性質上、呼び出しは特定の順序では行われません。この関数では、オブジェクトのハッシュ値や同等特性を変更するようなことをしてはいけません。 

virtual RWspace
binaryStoreSize() const;

クラス RWCollection から継承した関数。 

virtual void
clear();

クラス RWCollection から再定義した関数。 

virtual void
clearAndDestroy();

クラス RWCollection から継承した関数。 

virtual int
compareTo(const RWCollectable*) const;

クラス RWCollection から継承した関数。 

virtual RWBoolean
contains(const RWCollectable*) const;

クラス RWCollection から継承した関数。 

virtual size_t
entries() const;

クラス RWCollection から再定義した関数。 

virtual RWCollectable*
find(const RWCollectable*) const;

クラス RWCollection から再定義した関数。 

virtual unsigned
hash() const;

クラス RWCollection から継承した関数。 

virtual RWCollectable*
insert(RWCollectable* a);

クラス RWCollection から再定義した関数。成功すれば a を、失敗すれば NULL を返します。 

virtual RWClassID
isA() const;

クラス RWCollection から再定義した関数で、__RWHASHTABLE を返します。 

virtual RWBoolean
isEmpty() const;

クラス RWCollection から再定義した関数。 

virtual RWBoolean
isEqual(const RWCollectable*) const;

クラス RWCollection から再定義した関数。 

virtual RWCollectable*
newSpecies() const;

クラス RWCollection から再定義した関数。 

virtual size_t
occurrencesOf(const RWCollectable*) const;

クラス RWCollection から再定義した関数。 

virtual RWCollectable*
remove(const RWCollectable*);

クラス RWCollection から再定義した関数。 

virtual void
removeAndDestroy(const RWCollectable*);

クラス RWCollection から継承した関数。 

virtual void
resize(size_t n = 0);

n 個のバケットを持てるよう、内部ハッシュテーブルのサイズを変更します。変更するには、コレクションのメンバー全部を再ハッシュする必要があります。n がゼロの場合は、自動的に適切なサイズに決まります。 

virtual void
restoreGuts(RWvistream&);
virtual void
restoreGuts(RWFile&);
virtual void
saveGuts(RWvostream&) const;
virtual void
saveGuts(RWFile&) const;

クラス RWCollection から継承した関数。 

RWStringID
stringID();

(仮想関数として動作) クラス RWCollectable から継承した関数。