boost::hash 基本使用（tcy）

1.1.用途：
    此散列函数旨在用于基于 STL 的容器中，不适合作为通用散列函数
    支持C++的基本类型，STL无序容器,相同的参数应产生相同结果; 注1,2

1.2.使用注意事项：
    哈希函数实现通常调用boost::hash,boost::hash_range
    或没有命名空间限定boost::hash_combine（以便通过 ADL 找到自定义类型重载）
    通常不应由用户直接调用hash_value

    相同的参数应产生相同的结果

1.2.函数：
    void hash_combine(size_t &, T const&);组合多个值产生hash-顺序有关  注3
    std::size_t hash_range(It, It);        计算迭代器范围哈希-顺序有关  注4
    void hash_range(std::size_t&, It, It);

    std::size_t hash_value(T);基本类型 注1,2
    std::size_t hash_value(T* const&);
    std::size_t hash_value(T (&val)[unsigned N]);
    std::size_t hash_value(const T (&val)[N]);
  
1.3.使用方法：
1）系统支持的类型直接使用-创建实例并将其作为函数调用
    boost::hash string_hash;
    std::size_t h = string_hash("Hash me");
    
2）自定义类型
    类内重载比较运算符，重载friend hash_value(命名空间同类)

注意：
    不同于C++的std::hash;
    相同类型元素不同hash值不同；
    不同类型的数据的hash值可能相等；

注1：基本类型包括 
    bool, char, signed char, unsigned char, wchar_t, char16_t, char32_t, 
    short, unsigned short, int, unsigned int, long, unsigned long
    long long, unsigned long long,float, double, long double,
    
注2：STL无序容器,标准容器
    std:basic_string(string,wstring,u16string,u32string,type_index),T*
    std::array,std::pair,vector,list,deque,set,multiset,map,multimap
    std::complex,tuple
    
注3：boost::hash_combine
用途：重复调用以从多个变量增量创建哈希值
注意：使用调用顺序时很重要；计算数据哈希值，数据顺序在比较中并不重要，
    必须确保数据始终以相同顺序提供
    std::size_t seed = 0;
    hash_combine(seed, 1);hash_combine(seed, 2);不同于：
    boost::hash_combine(seed, 2);boost::hash_combine(seed, 1);
    
注4：boost::hash_range
用途：计算迭代器范围的哈希；对元素顺序敏感，不适合无序容器使用
原理：
    size_t seed = 0;
    for(; first != last; ++first){hash_combine(seed, *first);}//两参数
    for(; first != last; ++first){hash_combine(seed, *first);}//三参数
实例：
    std::vector some_strings;
    std::size_t hash = boost::hash_range(some_strings.begin(), some_strings.end());

注5：
在编写模板类时，您可能不想包含主哈希标头，因为它是一个非常昂贵的包含，
会带来许多其他标头，因此可包含
forward 声明的标头boost::hash，boost::hash_range和boost::hash_combine. 
在实例化boost::hash.当使用使用boost::hash它的容器时，应该为您执行此操作，
因此您的类型将与 boost 哈希容器一起正常工作。

#include 

template 
class my_pair{
    A value1;
    B value2;
public:
    my_pair(A const& v1, B const& v2): value1(v1), value2(v2){}
    bool operator==(my_pair const& b) const{return value1 == b.value1 &&value2 == b.value2;}

    friend std::size_t hash_value(my_pair const& p){
        std::size_t seed = 0;
        boost::hash_combine(seed, p.value1);
        boost::hash_combine(seed, p.value2);

        return seed;
    }
};

注6：可移植性
    boost::hash尽可能支持可移植，一些较旧编译器不支持参数相关查找（ADL） - 用于定制的机制
    hash_value在这些编译器上，需要在命名空间中声明自定义重载boost

    在严格符合标准的编译器上，在实例化boost时不会找到命名空间中定义的重载boost::hash，
    因此对于这些编译器，重载只能在与类相同的命名空间中声明。

2.实例：
实例1：通用使用
#include 

实例2：通用使用-生成的向量包含容器元素哈希值的函数
template 
std::vector get_hashes(Container const& x){
    std::vector hashes;
    std::transform(x.begin(), x.end(), std::back_inserter(hashes),
        boost::hash());

    return hashes;
}

实例3：自定义类型
    boost::hash通过调用hash_value来实现。未指定命名空间，以便它可通过参数查找相关重载
    因此如hash_value在与自定义类型相同的命名空间中有一自由函数，它将被调用
    
实例3.1：自定义hash函数
#include 
#include 

namespace tcy{
    struct book{int id;std::string author;std::string title;};
    bool operator==(book const& a, book const& b){return a.id == b.id;}
}

//编写函数tcy::hash_value：
namespace tcy{
    std::size_t hash_value(book const& b){boost::hash hasher;return hasher(b.id);}
}

//使用boost::hash：
void test(){
    tcy::book b1(100, "Tom");
    tcy::book b2(101, "Bob");

    boost::hash book_hasher;
    std::size_t b1_hash = book_hasher(b1);

    std::unordered_set > books;
    books.insert(b1);
    books.insert(tcy::book(102, "Jim"));
    books.insert(tcy::book(103, "Aimla"));

    assert(books.find(b1) != books.end());
    assert(books.find(b2) == books.end());
}

实例3.2：自定义hash函数-组合哈希值
点类希望将其用作 unordered_map 的键。需要为此结构自定义散列。
需要组合 x 和 y 的哈希值。boost::hash_combine为此目的提供了该函数

class point{
    int x;
    int y;
public:
    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}

    bool operator==(point const& b) const{ return x == b.x && y == b.y;}

    friend std::size_t hash_value(point const& p){
        std::size_t seed = 0;
        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);

        return seed;
    }
};

int main(){
    boost::hash point_hasher;

    point p1(0, 0);
    point p2(1, 2);
    point p3(4, 1);
    point p4 = p1;

    assert(point_hasher(p1) == point_hasher(p4));

    // 测试可能会失败，如失败那将是一相当糟糕的哈希函数
    assert(point_hasher(p1) != point_hasher(p2));
    assert(point_hasher(p1) != point_hasher(p3));
}

实例4：完整实例头文件

#pragma once

#include 
#include 
#include 
#include 
#include 

//#include 
#include 

namespace bs = boost;
using namespace std::string_literals;

template 
std::vector get_hashes(Container const& x) {
	std::vector hashes;
	std::transform(x.begin(), x.end(), std::back_inserter(hashes),
		boost::hash());

	return hashes;
}

namespace tcy {
	struct Book { int id; std::string author; };
	bool operator==(Book const& a, Book const& b);
	std::size_t hash_value(Book const& b);
}

class Point {
    int x;
    int y;
public:
    Point() : x(0), y(0) {}
    Point(int x, int y) : x(x), y(y) {}

    bool operator==(Point const& b) const { return x == b.x && y == b.y; }
    friend std::size_t hash_value(Point const& p) {
        std::size_t seed = 0;
        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);

        return seed;
    }
};

namespace tc {//推荐用法
	template  class A {
		T x;
	public:
		A(T x) : x(x) {}
		bool operator==(A const& b) { return x == b.x; }            //可定义为成员或普通函数
		//std::size_t hash_value() { return boost::hash()(x); }  //error不能定义为类成员函数
		friend std::size_t hash_value(const A& a) { return boost::hash()(a.x); }
	};
}

namespace tc {//备选用法-编译器若不支持模板friend(不支持 ADL 的编译器)
	// （不能声明为friend hash_value)hash_value需要在boost命名空间中定义
	template  class A1 {
		T x;
	public:
		A1(T x) : x(x) {}
		bool operator==(A1 const& b) { return x == b.x; }//可定义为成员或普通函数
		std::size_t hash() const {return boost::hash()(x); }
	};
}

#ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
namespace boost
#else
namespace tc
{
    template std::size_t hash_value(A1 x){return x.hash();}
}
#endif

void test_boost_hash();


//***********************************************************
// 以上测试boost库hash;以下测试C++ std::hash

struct B{
	int x;
	std::string s;

    B() :s(""), x(0) {}
    B(int x,const std::string& s) :s(s), x(x) {}
    bool operator==(const B& rhs) const { return (x == rhs.x) && (s == rhs.s); }  //必须重载  
};

//将自己的偏特化加入到std中
namespace std{
    template<> struct hash {
        size_t operator()(const B& rhs) const noexcept{
            return (std::hash()(rhs.x)) ^ (std::hash()(rhs.s) << 1);}
    };
}

class B1{
public:
    std::string name;
    std::string age;

    B1(std::string name,std::string age) :name(name),age(age) {}

    bool operator ==(const B1& c) const{
        return (name == c.name && age == c.age);}
};

class B1hash{
public:
    std::size_t operator()(const B1& c) const{
        return hash_val(c.name,c.age);}

    template 
    size_t hash_val(const Types&... args)const{
        size_t seed = 0;
        hash_value(seed, args...);
        return seed;
    }

    template 
    void hash_value(size_t& seed,const T& firstArg,const Types&... args) const{
        hash_combine(seed, firstArg);
        hash_value(seed, args...);
    }

    template 
    void hash_value(size_t& seed,const T& val) const{
        hash_combine(seed, val);
    }

    template
    void hash_combine(size_t& seed,const T& val) const{
        seed ^= std::hash()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
};


struct Point_ { 
    double x=0, y=0; 
    Point_() = default;
    Point_(double x, double y) :x(x),y(y) {}
};

struct Point_Cmp {
    bool operator()(const Point_& lhs, const Point_& rhs) const {
        return lhs.x < rhs.x; // NB. intentionally ignores y
    }
};

template
class T_hash {
public:
    size_t operator()(const Point_& s) const {
        size_t h1 = std::hash()(s.x);
        size_t h2 = std::hash()(s.y);
        return h1 ^ (h2 << 1);
    }
};

class t_hash {
public:
    size_t operator()(const Point_& s) const {
        size_t h1 = std::hash()(s.x);
        size_t h2 = std::hash()(s.y);
        return h1 ^ (h2 << 1);
    }
};

void test_cpuls_hash();

#include "boost_hash.h"
#include 
#include 

#include 
#include 
#include 
#include 


bool tcy::operator==(tcy::Book const& a, tcy::Book const& b) { return a.id == b.id; }
std::size_t tcy::hash_value(tcy::Book const& b) { boost::hash hasher; return hasher(b.id); }

void _test_int_boost_hash() {
	int x = 1; 
	assert(bs::hash()(x) == 1);
	assert(bs::hash()(x) == 1);
	assert(bs::hash()(x) == 1);
	assert(bs::hash()(x) == 1);
	assert(bs::hash()(x) == 1);
	assert(bs::hash()(x) == 1);

	int& rx = x; const int& crx = x;
	assert(bs::hash()(rx) == 1);
	assert(bs::hash()(crx) == 1);

	int* px = &x;
	auto h1 = bs::hash()(px);
	const int* cpx = &x; 
	auto h2 = bs::hash()(cpx);
	int* const pcx = &x; 
	auto h3 = bs::hash()(pcx);
	assert(h1 == h2 && h2 == h3);//h1每次运行的值都不同

	assert(bs::hash()(1) != bs::hash()(1));
}

void _test_str_boost_hash() {
	auto h = bs::hash()('a');
	assert(h == bs::hash()('a'));
	assert(h != bs::hash()("a"s));

	h = bs::hash()("Tom");
	assert(h != bs::hash()("Tom"s));
}

size_t hash_vec(const std::vector& vec) {return bs::hash>()(vec); }
size_t hash_vec(const std::vector& vec) { return bs::hash>()(vec); }
size_t hash_vec_range(const std::vector& vec) { return boost::hash_range(vec.begin(), vec.end()); }
size_t hash_vec_range(const std::vector& vec) { return boost::hash_range(vec.begin(), vec.end()); }

void _test_vector_boost_hash() {
	std::size_t h{}, h1{}, h2{};

	int x = 0;
	std::vector vec;
	std::vector dvec;

	assert(bs::hash()(x) == 0);
	assert(hash_vec(vec) == 0);
	assert(hash_vec(dvec) == 0);
	assert(hash_vec_range(vec) == 0);

	vec = { 2 };
	assert(bs::hash()(2) == 2);
	assert(hash_vec(vec) == 10832819064819134812);
	assert(hash_vec_range(vec) == 10832819064819134812);

	dvec = { 2 };
	assert(hash_vec(dvec) == 551290964831955812);
	assert(hash_vec_range(dvec) == 551290964831955812);

	vec = { 1,2,3 };
	assert(hash_vec(vec) == hash_vec_range(vec));
}

void _test_set_boost_hash() {
	std::size_t h{};
	std::set set;
	h = boost::hash_range(set.begin(), set.end());
	assert(h == 0);
	
	set={ 1, 2, 3, 4, 5 };
	h = boost::hash_range(set.begin(), set.end());
	assert(h == 10158794003290771518);
}


//使用boost::hash：
void test_book_boost_hash() {
	tcy::Book b1{ 100, "Tom"s };
	tcy::Book b2{ 101, "Bob"s };

	boost::hash book_hasher;
	std::size_t b1_hash = book_hasher(b1);

	std::unordered_set > books;
	books.insert(b1);
	books.insert(tcy::Book{ 102, "Jim" });
	books.insert(tcy::Book{ 103, "Aimla" });

	assert(books.find(b1) != books.end());
	assert(books.find(b2) == books.end());
}


void test_point_boost_hash() {
	boost::hash point_hasher;

	Point p1(0, 0);
	Point p2(1, 2);
	Point p3(4, 1);
	Point p4 = p1;

	assert(point_hasher(p1) == point_hasher(p4));

	// 测试可能会失败，如失败那将是一相当糟糕的哈希函数
	assert(point_hasher(p1) != point_hasher(p2));
	assert(point_hasher(p1) != point_hasher(p3));
}

void test_hash_combine() {
	//使用boost::hash_combine调用顺序时很重要
	std::size_t seed = 0;
	boost::hash_combine(seed, 1);
	boost::hash_combine(seed, 2);

	//产生不同的种子：
	std::size_t seed2 = 0;
	boost::hash_combine(seed2, 2);
	boost::hash_combine(seed2, 1);
	assert(seed != seed2);
}

void test_hash_range() {//计算迭代器范围的哈希
	std::vector vecstr;
	std::size_t hash = boost::hash_range(vecstr.begin(), vecstr.end());
	assert(hash == 0);

	vecstr = {"Tom", "Bob"};
	hash = boost::hash_range(vecstr.begin(), vecstr.end());
	std::cout << "vector hash=" << hash << std::endl;//1859127738627118395
}


void test_custom_type_boost_hash() {
	tc::A x1(1), x2(2), x3(1);
	boost::hash > hasher;

	assert(hasher(x1) == hasher(x1));
	assert(hasher(x1) != hasher(x2));
	assert(hasher(x1) == hasher(x3));

	tc::A1 y1(1), y2(2), y3(1);
	boost::hash > hasher1;

	assert(hasher1(y1) == hasher1(y1));
	assert(hasher1(y1) != hasher1(y2));
	assert(hasher1(y1) == hasher1(y3));
}

void test_boost_hash() {
	_test_int_boost_hash();
	_test_str_boost_hash();
	_test_vector_boost_hash();
	_test_set_boost_hash();

	test_book_boost_hash();//使用boost::hash
	test_point_boost_hash();
	test_hash_combine();
	test_hash_range();
	test_custom_type_boost_hash();
}


void _test_cpuls_int_hash() {
	int x = 1; 
	int* px = &x; const int* cpx = &x;

	//去除限定符的int,long,size_t值(恒定)都相同
	assert(bs::hash()(x) == 1);
	assert(std::hash()(x) == 12478008331234465636);

	//去除限定符的*int,*long,*size_t值（每次运行都不同）都相同
	assert(bs::hash()(px) == bs::hash()(cpx));
}

void _test_cpuls_vector_hash() {
	auto h = std::hash()("Tom"s);

	std::vectorvec;
	h = std::hash>()(vec);
}

void test_cpuls_Point_hash() {
	using std::cout;
	using std::endl;
    Point_ p1, p2;
    std::hash hp;
	assert(hp(&p1)!=hp(&p2));//指针类型每次运行值不同
   
	assert(T_hash()(p1) == 17962616281243732559);
	assert(T_hash()(p2) == 17962616281243732559);
	assert(t_hash()(p1) == 17962616281243732559);
	assert(t_hash()(p2) == 17962616281243732559);

    std::any a1 = 1,a2 = 1;
    std::hash hash_any;
	assert(hash_any(&a1)!= hash_any(&a2));
}

void _test_cpuls_B_hash(){
	B b,b1(1011,"Tom"s), b2(1012, "Bob"s) ;
	assert(std::hash()(b) == 15762686341408249279);
	
	std::unordered_map map;
	//std::unordered_map map;//参数3可写可不写
	map.insert({ b,10 });
	map.insert({ b1,20 });
	map.insert({ b2,30 });
}

void _test_cpuls_B1_hash(){
	std::unordered_multiset set;
}

void test_cpuls_hash() {
	_test_cpuls_int_hash();
	_test_cpuls_B_hash();
	_test_cpuls_B1_hash();
	test_cpuls_Point_hash();
}

boost::hash 基本使用（tcy）

C/C++/C#相关栏目本月热门文章