c++中std::hash以及萬能hash的使用方式

更新時間：2023年08月07日 10:05:07 作者：米安r

這篇文章主要介紹了c++中std::hash以及萬能hash的使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

c++ std::hash以及萬能hash的使用

首先是標準庫中的std::hash函數(shù)，對于內(nèi)置的類型，標準庫中是已經(jīng)提供了的（包括std::string），但是若是自己自定義的類型想要求其哈希值的話，就需要自己定義其哈希值的求值方式。

下面是簡單示范

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using std::cout;
using std::endl;
class MyClass 
{
public:
    MyClass():str("hello"), data(0) {}
    bool operator==(const MyClass& rhs) const{return (data == rhs.data) && (str == rhs.str); }  //注意要重載這個==，
                                                                                                //因為unordered_set或者unordered_map
                                                                                                //中需要對元素是否相同進行判斷
public: //
    int data;
    std::string str;
};
//注意這里是將自己寫的偏特化也同樣加入到std中，因為他的模板是在std里面的，
//具體形式可以自己簡單查看一下源碼中的實現(xiàn)形式
//然后照著寫一個自己的版本就行了。
namespace std	
{
    template<>
    struct hash<MyClass>: public __hash_base<size_t, MyClass>   //標準庫中有這個繼承，查看一下其實只是繼承兩個typedef而已，
                                                                //所以不寫這個繼承在這個例子中也是可以運行的
                                                                //但為了更好的使用這個hash，寫上去會比較好
    {
        size_t operator()(const MyClass& rhs) const noexcept    //這個const noexpect一定要寫上去
        {
            return (std::hash<int>()(rhs.data)) ^ (std::hash<std::string>()(rhs.str) << 1); //當然，可以使用其他的方式來組合這個哈希值,
                                                                                            //這里是cppreference里面的例子，產(chǎn)生的數(shù)夠亂就行。
        }
    };
}
int main()
{
    MyClass c;
    std::hash<MyClass> myHash;  //創(chuàng)建一個函數(shù)對象
    std::cout << myHash(c) << std::endl;
	//注意這第三個參數(shù)是typename _Hash = hash < _Value >， 是可寫可不寫的，因為他是有默認形式的，寫出來就是這樣
    std::unordered_map<MyClass, char, std::hash<MyClass>> m;	//這第三個參數(shù)
    std::unordered_set<MyClass> s;	//和上面的是一個意思，第二個參數(shù)是typename _Hash = hash < _Value >，可寫可不寫， 這里我是沒寫的。
    s.insert(c);
    s.insert(c);
    std::cin.get();
}

另外一種方式是使用侯捷老師在講的“萬能哈希函數(shù)”原理只要明白可變模板參數(shù)的使用方法就不會太難，下面是他課上使用的代碼

#include <string>
using std::string;
class Customer
{
public:
    string mFirstName;
    string mLastName;
    string mAge;
    Customer(string firstName, string lastName, string age):mFirstName(firstName),mLastName(lastName),mAge(age){}
    bool operator ==(const Customer& c) const
    {
        return (mFirstName == c.mFirstName && mLastName == c.mLastName && mAge == c.mAge);
    }
};
class CustomerHash
{
public:
    std::size_t operator()(const Customer& c) const
    {
        return hash_val(c.mFirstName, c.mLastName, c.mAge);
    }
    template <typename... Types>
    size_t hash_val(const Types&... args)const
    {
        size_t seed = 0;
        hash_value(seed, args...);
        return seed;
    }
    template <typename T, typename... Types>
    void hash_value(size_t& seed,
                         const T& firstArg,
                         const Types&... args) const
    {
        hash_combine(seed, firstArg);
        hash_value(seed, args...);
    }
    template <typename T>
    void hash_value(size_t& seed,
                         const T& val) const
    {
        hash_combine(seed, val);
    }
    template<typename T>
    void hash_combine(size_t& seed,
                             const T& val) const
    {
        seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
};
int main()
{
    std::unordered_multiset<Customer, CustomerHash> set;
}

c++11中std::hash用法

哈希的定義

Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入（又叫做預映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。

這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。

簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

哈希簡介

Hash算法可以將一個數(shù)據(jù)轉(zhuǎn)換為一個標志，這個標志和源數(shù)據(jù)的每一個字節(jié)都有十分緊密的關系。
Hash算法還具有一個特點，就是很難找到逆向規(guī)律?；静豢赡軓慕Y果推算出輸入，所以又稱為不可逆的算法
Hash算法是一個廣義的算法，也可以認為是一種思想，使用Hash算法可以提高存儲空間的利用率，可以提高數(shù)據(jù)的查詢效率，也可以做數(shù)字簽名來保障數(shù)據(jù)傳遞的安全性。所以Hash算法被廣泛地應用在互聯(lián)網(wǎng)應用中。
Hash算法也被稱為散列算法，Hash算法雖然被稱為算法，但實際上它更像是一種思想。Hash算法沒有一個固定的公式，只要符合散列思想的算法都可以被稱為是Hash算法

常見的哈希算法

MD4
MD5
SHA-1及其他

哈希的用途

文件校驗
數(shù)字簽名
鑒權協(xié)議

std::hash的測試示例

對于內(nèi)置的類型，C++標準庫中已經(jīng)提供了std::hash函數(shù)計算哈希值，但如果是自己自定義的類型想求哈希值的話，則需要自己定義哈希值的求值方式。

#include <iostream>
#include <functional>
#include <string>
#include <iomanip>
int main()
{
	std::string strInput = "Peaceful in the present world, quiet in the years";
	std::hash<std::string> szHash;
	size_t hashVal = szHash(strInput);
	std::cout << std::quoted(strInput) << "'s hash=" << hashVal << "\n";
	//
	char buffer1[] = "Everything is fine";
	char buffer2[] = "Everything is fine";
	std::string strBuffer1(buffer1);
	std::string strBuffer2(buffer2);
	std::hash<char*> ptrHash;
	std::hash<std::string> strHash;
	//C++14引入std::quoted用于給字符串添加雙引號
	std::cout << std::quoted(buffer1) << "'s hash<char*>=" << ptrHash(buffer1) << std::endl;
	std::cout << std::quoted(buffer2) << "'s hash<char*>=" << ptrHash(buffer2) << std::endl;
	std::cout << std::quoted(strBuffer1) << "'s hash<std::string>=" << strHash(strBuffer1) << std::endl;
	std::cout << std::quoted(strBuffer2) << "'s hash<std::string>=" << strHash(strBuffer2) << std::endl;
	//boolalpha是使bool型變量按照false、true的格式輸出,如不使用該標識符,則會按照1、0的格式輸出
	std::cout << "same hashes:\n" << std::boolalpha;
	std::cout << "buffer1 and buffer2: " << (ptrHash(buffer1) == ptrHash(buffer2)) << '\n';//false
	std::cout << "strBuffer1 and strBuffer2: " << (strHash(strBuffer1) == strHash(strBuffer2)) << '\n';//true
	return 0;
}

輸出結果：

"Peaceful in the present world, quiet in the years"'s hash=1772844349
"Everything is fine"'s hash<char*>=3806338771
"Everything is fine"'s hash<char*>=1493957927
"Everything is fine"'s hash<std::string>=1559491232
"Everything is fine"'s hash<std::string>=1559491232
same hashes:
buffer1 and buffer2: false
strBuffer1 and strBuffer2: true

C++ 官方提供的 demo

鏈接地址：https://en.cppreference.com/w/cpp/utility/hash

#include <iostream>
#include <iomanip>
#include <functional>
#include <string>
#include <unordered_set>
struct S {
    std::string first_name;
    std::string last_name;
};
bool operator==(const S& lhs, const S& rhs) {
    return lhs.first_name == rhs.first_name && lhs.last_name == rhs.last_name;
}
// custom hash can be a standalone function object:
struct MyHash
{
    std::size_t operator()(S const& s) const noexcept
    {
        std::size_t h1 = std::hash<std::string>{}(s.first_name);
        std::size_t h2 = std::hash<std::string>{}(s.last_name);
        return h1 ^ (h2 << 1); // or use boost::hash_combine
    }
};
// custom specialization of std::hash can be injected in namespace std
template<>
struct std::hash<S>
{
    std::size_t operator()(S const& s) const noexcept
    {
        std::size_t h1 = std::hash<std::string>{}(s.first_name);
        std::size_t h2 = std::hash<std::string>{}(s.last_name);
        return h1 ^ (h2 << 1); // or use boost::hash_combine
    }
};
int main()
{
    std::string str = "Meet the new boss...";
    std::size_t str_hash = std::hash<std::string>{}(str);
    std::cout << "hash(" << std::quoted(str) << ") = " << str_hash << '\n';
    S obj = { "Hubert", "Farnsworth" };
    // using the standalone function object
    std::cout << "hash(" << std::quoted(obj.first_name) << ", "
              << std::quoted(obj.last_name) << ") = "
              << MyHash{}(obj) << " (using MyHash)\n" << std::setw(31) << "or "
              << std::hash<S>{}(obj) << " (using injected std::hash<S> specialization)\n";
    // custom hash makes it possible to use custom types in unordered containers
    // The example will use the injected std::hash<S> specialization above,
    // to use MyHash instead, pass it as a second template argument
    std::unordered_set<S> names = {obj, {"Bender", "Rodriguez"}, {"Turanga", "Leela"} };
    for(auto& s: names)
        std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n';
}

輸出結果：

hash("Meet the new boss...") = 1861821886482076440
hash("Hubert", "Farnsworth") = 17622465712001802105 (using MyHash)
or 17622465712001802105 (using injected std::hash<S> specialization)
"Turanga" "Leela"
"Bender" "Rodriguez"
"Hubert" "Farnsworth"