STL源码分析hash_function

简介

hash_function主要是用来计算hash_code，然后把求出的hash_code取余后放入对应的位置。对于普通的int、char、string都有相应的求hash_code的方法，这篇文章针对一个自己定义的类设计了hash_function，用到了一些小技巧。

hash_function源代码

下面是自己定义的类和对于相等符号的函数重载代码，类中主要有三个成员有两种类型，我们需要根据三个成员计算出它们的hash_code。

class Customer
{
public:
	string fname;
	string lname;
	int no;
public:
	Customer(string f, string l, int _no) : fname(f), lname(l), no(_no) {}
};

bool operator==(const Customer &lhs, const Customer &rhs)
{
	return (lhs.fname == rhs.fname && lhs.lname == rhs.lname && lhs.no == rhs.no);
}
bool operator!=(const Customer &lhs, const Customer &rhs)
{
	return lhs == rhs;
}

hash_function是利用类来实现的，

class CustomerHash
{
public:
	size_t operator()(const Customer &c) const
	{
		return hash_val(c.fname, c.lname, c.no);
	}
};

难点主要在于hash_val的设计，需要用到函数模板的重载，

template <class T>
inline void hash_combine(size_t &seed, const T &val)
{
	seed ^= hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// hash_val 版本1
template <typename T>
inline void hash_val(size_t &seed, const T &val)
{
	hash_combine(seed, val);
}
// hash_val 版本2
template <typename T, typename... Types>
inline void hash_val(size_t &seed, const T &val, const Types... args)
{
	hash_combine(seed, val);
	hash_val(seed, args...); // 出现递归调用
}
// hash_val 版本3
template <typename... Types>
inline size_t hash_val(const Types &... args)
{
	size_t seed = 0;
	hash_val(seed, args...); // 此时会调用版本2
	return seed;
}

另外一种方法是设计一种偏特化版本的hash_function对于自己设计的类。下面是简单的示例：

namespace std
{
    template<>
    struct hash<MyString>
    {
        size_t operator()(const MyString &s) const
        {
            return hash<string>()(string(s.get())) // 利用hash<string>
        }
    }
}

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。