如何实现各种类型的密钥的哈希函数？

Question

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

我有一个模板类的元素，以便我可以使用各种变量类型的哈希映射。 这是我的代码元素。

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] != '\0') 
     { 
      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

你的散列函数应该是关键类型的模板功能，你的容器类外实现。 然后，您可以针对您实际使用哈希映射的每个键类型专门化模板函数。 这将类型检查从运行时转换为编译时，使其更快更安全。

// 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); 
}