如何为各种类型的密钥实现散列函数？

Question

我已经用 C++ 实现了哈希映射。一切正常，除了哈希函数。

我有一个元素模板 class，这样我就可以为散列映射使用各种变量类型。这是我的元素代码。

template <class KeyType, class ValType>
class MapElem
{
public:
    typedef KeyType ktype;
    typedef ValType vtype;

    KeyType key;
    ValType val;

    MapElem* link;  // singly linked list
};

和哈希函数代码。

template <class HashMapElemType>
unsigned int 
HashMap<HashMapElemType>::hashfunction(const KeyType k)
{
    unsigned int hashIndex = 0;



    if (typeid(KeyType).name() == typeid(std::string).name())
    {
        unsigned int hashIndex = 0;

        const char* c = k.c_str();

        unsigned int i = 0;
        int index = 0;
        int shift = 0;

        while (c[index] != '[=11=]')
        {
            if (shift == 32)
                shift = 0;
            i += ((int) c[index++]) << shift;
            shift += 8;
        }

        hashIndex = i;
    }
    else if (typeid(KeyType).name() == typeid(float).name())
    {   
        float f = k;
        hashIndex = (unsigned int) f;
    }
    else if (typeid(KeyType).name() == typeid(int).name())
    {
        int i = k;
        hashIndex = (unsigned int) i;
    }
    else
    {
        hashIndex = k;
    }

    hashIndex = hashIndex % divisor;

    return hashIndex;
}

哈希函数中的类型转换存在编译错误。我明白为什么会出现错误，但我不知道如何解决。我想知道如何从不同类型的键值中得到哈希值。

哦，这是错误 enter image description here

Answer 1

您的散列函数应该是密钥类型的模板函数，在您的容器外实现 class。然后，您可以为实际使用哈希映射的每个键类型专门化模板函数。这将类型检查从运行时间转变为编译时间，使其更快、更安全。

// hash function prototype, no implementation
template<typename T> unsigned int CalculateHash( const T& v );

// hash function specialization for std::string
template<> unsigned int CalculateHash( const std::string& v )
{
  // your hash function for std::string ...
}

在您的容器实现中，您可以使用通用哈希函数为您的密钥生成哈希值。

template <class HashMapElemType>
unsigned int HashMap<HashMapElemType>::hashfunction(const KeyType& k)
{
  // delegate to global hash function template
  return ::CalculateHash<KeyType>( k ); 
}

如何为各种类型的密钥实现散列函数？

How to implement the hash function for the various type of key?

c++

hash

templates

hash-function