如何在C++中實現泛型哈希函數

我想通過模板在C++中實現HashTable。下面是簽名：如何在C++中實現泛型哈希函數

template<class T1, class T2> 
class HashTable { 

public: 
void add(T1 a, T2 b); 

void hashFunction(T1 key, T2 value) 
{ 

// how to implement this function using key as a generic 
// we need to know the object type of key 

} 
};

所以，我無法與執行涉及通用鍵向前移動。

在Java中，我可以很容易地將鍵轉換爲字符串，然後很高興將鍵的哈希實現爲字符串。但是，在C++中，我所知道的是有一個RTTI的概念，它可以動態地將對象轉換爲所需的對象。

如何實現動態轉換，如果此方法正確呢？

如果使用模板不是這種情況下實現泛型的正確方法，那麼請建議一些更好的方法。

來源

2013-04-26 Sankalp

就強制約束'T1'有「可哈」。即一個給你散列鍵的方法必須存在。 – millimoose 2013-04-26 19:23:39

（Java解決這個問題的方法是讓所有對象都可排序） – millimoose 2013-04-26 19:23:56

你知道C++ 11中有['std :: unordered_set']（http://en.cppreference.com/w/cpp/container/unordered_set）？它是標準庫中的一個哈希表。 – dyp 2013-04-26 19:28:07

爲此，您通常會使用std::hash，並讓類型實現者根據需要專門設置該模板。

size_t key_hash = std::hash<T1>()(key);

沒有辦法一般地實現你給定的隨機類型的散列函數。如果兩個對象相等，則它們的哈希碼必須相同。你可以簡單地通過散列函數運行對象的原始內存，但是這些類型可能會實現忽略某些對象數據片段（比如同步對象）的重載。在這種情況下，你可能（很容易）爲相同的對象返回不同的散列值。

來源

2013-04-26 19:21:46 cdhowie

但是，我想爲通用密鑰實現我自己的散列表。在STL中必須有某種方式來實現它。這裏的實現是在現實生活中使用的情況。 – Sankalp 2013-04-26 19:24:39

@Sankalp有，我已經給你了：'std :: hash'。例如，你可以使用'std :: hash '。如果當你的HashTable模板被實例化時沒有專門的'T1'，編譯器會給出一個錯誤。如果你不是'T1'給出的類型的作者，那麼你*不可能*希望爲它實現正確的哈希算法。 – cdhowie 2013-04-26 19:25:43

@PeterBecker謝謝你的編輯......我顯然沒有足夠的咖啡因。 – cdhowie 2013-04-26 19:29:14

奇怪的是，你想散列鍵和值。你如何能夠通過只有鑰匙才能獲得價值？

如果您使用C++ 11，最好的辦法是使用爲某些類型（整數，字符串，指針）提供的std::hash<T1>，並且可能專門用於其他類。此外，允許使用第三個模板參數類來更改它是個好主意。怎麼看unordered_map完成

template<typename K, typename V, typename H = std::hash<T>> 
class HashTable { 
    //... 
    void hashFunction(const T1& key) { 
     hash = H()(key); 
     //process hash somehow, probably you need get reminder after division to number of buckets or something same 
     return hash % size; 
    } 
}

這似乎是不可能寫你自己的散列器，這將適用於大多數類型的確定，因爲運營商的平等在一些複雜的方式也許覆蓋

來源

2013-04-26 19:25:31 RiaD

+1爲建議提供哈希實現作爲模板參數。 – cdhowie 2013-04-26 19:29:59

如何在C++中實現泛型哈希函數

回答

相關問題