0

我正在尝试创建一个使用模板的哈希图。在探测和探测的情况下，模板将接受一个哈希函数（hash (int key, int size) 的形式）和一个探测函数（probe (int i) 的形式）（int key, int size）在双重哈希的情况下。我希望你明白我在说什么。这是我的主要内容：

#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);

}

如您所见，我传入了两种不同的指针函数类型作为探测函数。在双重哈希的情况下，“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”部分标记了一个错误，因为我当然是在使用两个不同的参数号调用同一个探针、模板函数。我不是在问为什么它会抛出错误，因为我已经知道为什么。我正在寻求解决方案 - 或解决方法。谢谢。

4

1 回答 1

1

以下是我可以考虑的一些解决方案：

  1. 一个快速而肮脏的解决方法是声明一个虚拟的默认第二个参数，该参数将不会用于单参数探测功能，例如

    inline int linear_probe( int i, int dummy = 0 ) { return i; }

    现在 linear_probe 实际上有 2 个参数，但默认情况下已初始化一个，因此您将能够使用 2 参数函数指针指向它。但是这个解决方案并不是最优雅的，可能你应该考虑改变你的设计。为什么不创建 2 个单独的类，一个用于简单散列，一个用于双精度？或者也许使双重哈希继承自简单哈希。

  2. 使用模板专业化

    您需要专门generic_map针对true和的课程false。保留您的通用定义，但只专门化 2 个版本，例如template<typename types (omit bool here as we specialize)> generic_map<types, true>. 看看这里例如： http ://cprogramming.com/tutorial/template_specialization.html

于 2014-11-29T20:51:50.587 回答