かなり前に書いたハッシュのクラスファイル（http://yamablo.com/2008/11/14-005442.php）の訂正版になります。訂正版を公開するのを忘れてました。

想定は、2項目からなるデータをハッシュとして保持する状況を考えてます。2項目のうち1つはキーとなる項目で、残りの1項目は非キー項目です。

Hash.cpp

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. #define     DATA_SIZE   256 
6. #define     TABLE_SIZE  200
8. // ハッシュ表に格納するデータの構造
9. typedef struct data {
10.     char    key[DATA_SIZE];       // 格納するキーのデータ
11.     char    value[DATA_SIZE];     // 格納する非キーのデータ
12.     int     flg;                  // 格納状態のフラグ
13. } data;
15. class Hash {
16.     public:
17.         data    HashTable[TABLE_SIZE];  // ハッシュ表
18.         int     collision;              // データ格納時にコリジョンが発生した回数
19.         int     stored;                 // データの格納数
20.         double  StoredPerAll;           // データの格納率
22.     private:
23.         // ハッシュ値を求める
24.         int HashValue( char *str ) {
25.             int     idx;        // インデックスカウンタ
26.             int     length;     // 文字列の長さを格納
27.             int     h = 0;      // ハッシュ値を格納
29.             length = strlen( str );
30.             for( idx=0; idx<length; idx++ ) {
31.                 h = h * 37 + str[idx];
32.             }
33.             h = h % TABLE_SIZE;
34.             return abs(h);
35.         }
37.     public:
38.         /* ******************************************
39.          * データstrの格納場所を求める
40.          * もし存在しなければ、-1を返す
41.          * ****************************************** */
42.         int where( char *str ) {
43.             int         h;
45.             h = this->HashValue( str );
47.             // 該当場所のデータが空で、削除もしていないとき
48.             if( this->HashTable[h].flg == 0 ) {
49.                 return -1;
50.             }
52.             // ハッシュ表の該当場所をチェックし、
53.             // その場所から目的のデータを探す
54.             while( strcmp(this->HashTable[h].key, str)!=0 ) {
55.                 h++;
56.                 if( h == TABLE_SIZE ) {
57.                     h = 0;
58.                 } else if( h == this->HashValue( str ) ) {
59.                     // ハッシュ表を全て見てもなかった場合、Not Found
60.                     return -1;
61.                 }
62.             }
63.             return      h;
64.         }
67.         // コンストラクタ
68.         Hash() {
69.             int idx;
70.             for( idx=0; idx<TABLE_SIZE; idx++ ) {
71.                 this->HashTable[idx].key[0] = ’\0′;
72.                 this->HashTable[idx].value[0] = ’\0′;
73.                 this->HashTable[idx].flg = 0;
74.             }
76.             this->collision = 0;
77.             this->stored = 0;
78.         }
80.         // デストラクタ
81.         ~Hash() {
82.             // Do Nothing
83.         }
85.         /* ******************************************
86.          * ハッシュ表にデータを追加する
87.          * ****************************************** */
88.         void Add( data str ) {
89.             int     h;          // ハッシュ値を格納
91.             if( this->where( str.key ) == -1 ) {
92.                 // ハッシュ値を計算しhに保存
93.                 h = this->HashValue( str.key );
95.                 // ハッシュ表の該当場所をチェックし、
96.                 // 衝突していれば衝突回避するようにhを設定
97.                 while( this->HashTable[h].flg == 1 ) {
98.                     this->collision++;
99.                     h++;
100.                     if( h == TABLE_SIZE ) {
101.                         h = 0;
102.                     }
103.                 }
105.                 // データをハッシュ表に追加
106.                 strcpy( this->HashTable[h].key, str.key );
107.                 strcpy( this->HashTable[h].value, str.value );
108.                 this->HashTable[h].flg = 1;
109.                 this->stored = this->stored + 1;
110.                 this->StoredPerAll = this->stored * 100 / TABLE_SIZE;
111.             }
112.         }
114.         /* ******************************************
115.          * データstrがこのハッシュで表現された集合に含まれるか
116.          * @return  0なら含まれない、1なら含まれる
117.          * ****************************************** */
118.         int member( char *str ) {
119.             if( this->where( str ) == -1 ) {
120.                 return 0;
121.             } else {
122.                 return 1;
123.             }
124.         }
126.         /* ******************************************
127.          * データstrをこのハッシュで表現された集合から削除
128.          * もし最初から存在しなければ、何もしないで終了
129.          * ****************************************** */
130.         void deletes( char *str ) {
131.             if( this->member( str ) == 1 ) {
132.                 // データを削除する
133.                 this->HashTable[this->where(str)].key[0] = ’\0′;
134.                 this->HashTable[this->where(str)].value[0] = ’\0′;
135.                 this->HashTable[this->where(str)].flg = -1;
136.                 this->stored = this->stored - 1;
137.                 this->StoredPerAll = this->stored * 100 / TABLE_SIZE;
138.             }
139.         }
140.  
141.         /* ******************************************
142.          * ハッシュからデータを取り出す
143.          * ****************************************** */
144.         data Get( char *keys ) {
145.             int     idx;        // キーkeysの格納場所
146.             data    ret;        // 戻り値として返すデータ
147.             
148.             idx = this->where( keys );
149.             strcpy( ret.key, HashTable[idx].key );
150.             strcpy( ret.value, HashTable[idx].value );
151.             return ret;
152.         }
154.         /* ******************************************
155.          * ハッシュの再構築
156.          * ****************************************** */
157.        void refresh() {
158.             int     idx;
159.             int     k = 0;
160.             data    SwapTable[TABLE_SIZE];
162.             // データを退避用変数に格納する。
163.             for( idx=0; idx<TABLE_SIZE; idx++ ) {
164.                 if( this->HashTable[idx].flg == 1 ) {
165.                     strcpy( SwapTable[k].key, this->HashTable[idx].key );
166.                     strcpy( SwapTable[k].value, this->HashTable[idx].value );
167.                     SwapTable[k].flg = 1;
168.                     k++;
169.                 }
170.             }
172.             // テーブルをリセットする
173.             for( idx=0; idx<TABLE_SIZE; idx++ ) {
174.                 this->HashTable[idx].flg = 0;
175.                 this->HashTable[idx].key[0] = ’\0′;
176.                 this->HashTable[idx].value[0] = ’\0′;
177.             }
178.             this->collision = 0;
179.             this->stored = 0;
180.             this->StoredPerAll = 0;
182.             // 退避したデータを格納する
183.             for( idx=0; idx<k; idx++ ) {
184.                 this->Add( SwapTable[idx] );
185.             }
186.         }
187. };

関連記事

• [C++] Hashクラス
• ハッシュについて
• [PHP] MySQLクラス
• [C++] Dimensionクラス
• [PHP] Queueクラス

[PR]

トラックバック

http://yamablo.com/2008/12/19-103002.php/trackback

One Response to “[C++]Hashクラス・改訂版,”

1. yamablo » [C++] Hashクラス Says:
   11月 5th, 2009 at 12:38 AM

   [...] http://yamablo.com/2008/12/19-103002.phpの記事にHashクラスの改訂版があります。 [...]

コメント

Name

Mail (will not be published)

Website