テンプレートを使用するハッシュマップを作成しようとしています。テンプレートは、ハッシュ関数 (hash ( int key, int size ) の形式) とプローブ関数 (probing および probe ( int key, int size ) の場合は probe ( int i ) の形式) を取ります。ダブルハッシュの場合. 私の言っていることを理解していただければ幸いです. これが私のメインです:
#include "generic_map.h"
inline int hash( int key, std::size_t M ) { return key % M; }
inline int hash2( int key, std::size_t M ) { return key % (M-1) + 1; }
inline int linear_probe( int i ) { return i; }
inline int quadratic_probe( int i ) { return i*i; }
int main() {
generic_map<int, char, int(*)(int,std::size_t), hash, int(*)(int), quadratic_probe, false> map1( 20);
generic_map<int, char, int(*)(int,std::size_t), hash, int(*)(int, std::size_t), hash2, true> map2( 20);
}
ご覧のとおり、プローブ関数として 2 つの異なるポインター関数型を渡しています。ダブルハッシュの場合、「Hash2」がプローブ関数として渡されます。これは、ヘッダー ファイル (つまり、クラス宣言、ノード宣言、および挿入メソッド) からのスニッパーです。
template <class KEY, class VALUE, class HASH_FUNC, HASH_FUNC hash, class PROBE_FUNC, PROBE_FUNC probe, bool double_hash>
//Hashmap Class
class generic_map {
private:
//Node Class
struct hashNode {
KEY key; //Stores the key of node
VALUE value; //Stores the value that associates to key
hashNode(KEY key, VALUE &value) : key(key), value (value) {} //hashNode constructor
};
public:
//Creates a new backing array with user inserted capacity
generic_map( int capacity ) {
M = capacity;
map = new hashNode * [capacity];
for(int i = 0; i < M; ++i) {
map[i] = NULL;
}
}
//Deletes the hashNodes in the list and the map
~generic_map() {
clear();
}
//If index that key hashes to is empty, insert. Else, replace value at hashed index.
int insert( KEY key, VALUE value ) {
int f = hash( key, M );
int p = 0;
int h = f;
while( map[h] != NULL ) {
if( p == M )
return -1 * p;
if( map[h]->key == key ) {
map[h]->value = value;
return p;
}
else {
++p;
if(double_hash) {
h = f + (p * probe(key, M)) % M;
}
else {
h = f + (probe( p )) % M; //This is throwing an error and will not compile,
} //saying, "too few arguments to function call.
}
}
私の挿入メソッドの "double_hash_ 条件の "else" 部分は、もちろん同じプローブ、テンプレート関数を 2 つの異なる引数番号で呼び出しているため、エラーにフラグを立てています。理由を知っています.私はこれに対する解決策を求めています-または回避策.ありがとう.