如何實現各種類型的密鑰的哈希函數？

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