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

我已經在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

來源

2016-11-18 Uni

那麼......哪裏出錯？ – George

您不能只是將任意類型轉換爲某種東西，因爲typeid表示它有一個名稱。如果語句在運行時運行 - 它們不會在編譯時影響類型系統。所有這些代碼路徑必須爲每個鍵類型編譯，並且它們並不總是有效的。你可能會想做部分專用的函子。或者也許你的錯誤是完全不同的...... – xaxxon

你的散列函數應該是關鍵類型的模板功能，你的容器類外實現。然後，您可以針對您實際使用哈希映射的每個鍵類型專門化模板函數。這將類型檢查從運行時轉換爲編譯時，使其更快更安全。

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

來源

2016-11-18 10:12:26 smocoder

它確實有幫助，並且運作良好。非常感謝你。 – Uni

不客氣。我很高興它有幫助。 – smocoder

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

回答

相關問題