template < typename KeyType, typename ValueType >
class MapLinear {
KeyType key;
ValueType value;
...
}
template < typename KeyType, typename ValueType >
MapLinear<KeyType,ValueType>::MapLinear( )
{
...
}
...
int main( )
{
MapLinear<string,string> pr;
....
}
|
以下の例はテンプレートになっているが、 最初からテンプレートを作ろうとするとデバッグが大変である。 まず、「キー」も「値」も int 型にしてプログラムを完成させ、その 後にテンプレート化すること。
#include<iostream>
#include<string>
using namespace std;
template< typename KT, typename VT >
class HashSeparate
{
MapLinear<KT,VT>* table; // MapLinear の配列を動的に確保するためのポインタ
int table_size; // ハッシュ表のサイズ
// インデックスは 0 .. table_size-1 の範囲になる
int ndata; // 実際に登録されているデータ数
public:
HashSeparate( int n );
~HashSeparate( );
bool Insert( KT key, VT value );
bool Find( KT key, VT & value ) const;
bool Erase( KT key );
private:
int hash( int i ) const { return i % table_size; };
// ハッシュ関数の一例。ハッシュ値は 0 .. table_size - 1 になる。
};
template< typename KT, typename VT>
HashSeparate<KT,VT>::HashSeparate( int size )
{
table = new MapLinear<KT,VT>[size]; //「MapLinear の配列」を生成
table_size = size;
ndata = 0;
}
template< typename KT, typename VT >
HashSeparate<KT,VT>::~HashSeparate( )
{
delete [] table;
}
template< typename KT, typename VT >
bool HashSeparate<KT,VT>::Insert( KT k, VT v )
{
// これを作成せよ。
// 適切なリストを選んでデータを追加。
// ndata を必要に応じて更新せよ。
// 同じキーがあれば、追加はせずに false を返す。
}
template< typename KT, typename VT >
bool HashSeparate<KT,VT>::Find( KT k, VT & v ) const
{
// これを作成せよ。
// 適切なリストを選んでデータを探索し、結果を返す。
}
template< typename KT, typename VT >
bool HashSeparate<KT,VT>::Erase( KT k )
{
// これを作成せよ。
// 適切なリストを選んでデータを削除し、結果を返す。
// ndata を必要に応じて更新せよ。
}
int main()
{
HashSeparate<int,int> score(10);
score.Insert(100,100);
score.Insert(23,23);
score.Insert(33,33);
score.Insert(0,0);
score.Insert(3,3);
int i;
cout << score.Find(33,i) << endl;
cout << score.Erase(30) << endl;
cout << score.Erase(33) << endl;
cout << score.Find(33,i) << endl;
}
|
キーが string の場合のハッシュ関数 int hash( string s ) を作り。 以下のような main 関数で string をキーとするハッシュ表をテストせよ。
int main()
{
HashSeparate<string,int> staff(10);
staff.Insert( "mino", 10 );
staff.Insert( "yoshi", 20 );
staff.Insert( "nabe", 30 );
staff.Insert( "masaki", 40 );
int dummy;
cout << staff.Find( "mino", dummy ) << endl;
staff.Erase("mino");
cout << staff.Find( "mino", dummy ) << endl;
return 0;
}
|
string をキーとするハッシュ関数は自分で自由に作って良いが、 文字に対応する数値を得る方法としては次のプログラムを 参考にせよ。
#include<iostream>
#include<string>
using namespace std;
int main ()
{
string str = "YamanashiUniv";
for ( int i = 0; i < str.length(); i ++ ) {
cout << str[i] << ":" << (int) str[i] << endl;
}
}
|
最初は、「キー」の型を string、「値」の型を int にしてプログラムを完成させ、その後にテンプレート化すること。
#include <iostream>
#include <string>
#include <new>
using namespace std;
template< typename KT, typename VT >
class HashTable
{
enum EntryType { ACTIVE, EMPTY, ERASED }; // 列挙型 EntryType の定義
// 列挙型については教科書 336ページ(11.2節)を参考にせよ。
class HashEntry // key, value, status をセットで扱う。
{ // 一組のデータが一つの HashEntry に格納される。
KT key;
VT value;
EntryType status; // status ( EntryType 型変数 ) は
// ACTIVE, EMPTY, ERASED のいずれかの値を取る。
public:
HashEntry( ){ status = EMPTY; }; // 最初は EMPTY 状態
friend class HashTable;
};
HashEntry* table; // HashEntry の配列を動的に確保するためのポインタ
int table_size;
int nempty; // EMPTY 状態 HashEntry の数
public:
HashTable( int n );
~HashTable( );
bool Insert( KT key, VT value );
bool Find( KT key, VT & value ) const;
bool Erase( KT key );
private:
int hash( int i ) const { return i % table_size; };
int hash( const string & s ) const ;
// ハッシュ値が衝突した場合に使われる「次のハッシュ値」
int nexthash ( int h ) const { return (h+1) % table_size; };
};
template< typename KT, typename VT >
HashTable<KT,VT>::HashTable( int size )
{
table_size = size;
table = new HashEntry[table_size];
nempty = table_size;
}
// 文字列用のハッシュ関数（一例）
template< typename KT, typename VT >
int HashTable<KT,VT>::hash( const string & key ) const
{
int x = 0;
for( int i=0; i < key.length(); i ++ )
x = ( x * 128 + key[i] ) % table_size;
return x;
}
template< typename KT, typename VT >
HashTable<KT,VT>::~HashTable( )
{
delete [] table;
}
template< typename KT, typename VT >
bool HashTable<KT,VT>::Insert( KT k, VT v )
{
if ( Find( k, v ) ) // 同じキーが存在するときの処理
return false; // 能率的ではないが、今回は簡単さを優先。
if ( nempty <= 1 )
throw " Hash table is full ";
/* オープンアドレッシングではハッシュ表のサイズより多いデータを
格納することはできない。ハッシュ表の動的な拡大はアルゴリズム
とデータ構造IIで行う。
*/
int h = hash(k);
while ( table[h].status == ACTIVE ) // ハッシュ値衝突時の処理
h = nexthash( h );
table[h].key = k;
table[h].value = v;
if ( table[h].status == EMPTY )
nempty--;
table[h].status = ACTIVE;
return true;
}
// Find, Erase を作成せよ。
// status( EMPTY, ACTIVE, ERASED )を適切に設定、利用することが重要。
// bool Find( KT key, VT & value ) const;
// key が見つからなければ false を返す。
// key が見つかれば、それに対応する値を 参照引数 value に代入して、
// true を返す。
// bool Erase( KT key );
// key が存在しなかったら false を返す。
// そうでなければ key をもつデータを削除し true を返す。
int main()
{
// 以下は十分なテストとは言えない。
try {
HashTable<string, int> score(10);
score.Insert( "mino", 10 );
score.Insert( "yoshi", 20 );
score.Insert( "nabe", 30 );
score.Insert( "masaki", 40 );
score.Insert( "ysuzuki", 50 );
int i;
if ( score.Find( "mino", i ) )
cout << i << endl;
else
cout << " not found" << endl;
score.Erase( "mino" );
if ( score.Find( "ysuzuki", i ) )
cout << i << endl;
else
cout << " not found" << endl;
if ( score.Find( "mino", i ) )
cout << i << endl;
else
cout << " not found" << endl;
}
catch ( bad_alloc ba ) {
cout << " memory allocation error." << endl;
}
catch ( const char* msg ) {
cout << msg << endl;
}
return 0;
}
|