Ricky Yel Blog

万能hash_func

 
  • Ricky Yel
  • 2023年 01月03日

对于自定义的结构体，如果需要作为要求元素是可哈希的容器的元素，那么就需要自定义hash函数。STL中这样的容器有：std::unordered_map、std::unordered_set、std::unordered_multimap、std::unordered_multiset。

万能的 hash function

// hash_func.h
//计算种子数值
template<typename T>
inline void hash_combine(size_t& seed, const T& val)
{
	seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

//递归调用出口
template<typename T>
inline void hash_val(size_t& seed, const T& val)
{
	hash_combine(seed, val);
}

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

template<typename... Types>
inline size_t hash_val(const Types&... args)
{
	size_t seed = 0;
	hash_val(seed, args...);
	return seed;
}

用例

需要被hash的对象

#include <string>
struct Custom
{
	std::string str_FirstName;
	std::string str_LastName;
	long l_ID;
};

实现方法1–以仿函数的形式定义哈希函数

struct CustomHash
{
	std::size_t operator()(const Custom& custom) const
	{
		return hash_val(custom.str_FirstName, custom.str_LastName, custom.l_ID);
	}
};

struct CustomEqualTo
{
	bool operator()(const Custom& c1, const Custom& c2) const
	{
		return c1.str_FirstName == c2.str_FirstName &&
			c1.str_LastName == c2.str_LastName &&
			c1.l_ID == c2.l_ID;
	}
};

// 使用方法
int main()
{
	std::unordered_set<Custom, CustomHash, CustomEqualTo> hash_set; // 需要指定 Hash 和 EqualTo

	hash_set.insert(Custom{ "san", "Zhang", 1l });
	hash_set.insert(Custom{ "si", "Li", 2l });
	hash_set.insert(Custom{ "er", "Wang", 3l });
	hash_set.insert(Custom{ "wu", "Zhao", 4l });
	hash_set.insert(Custom{ "liu", "Guan", 5l });
	hash_set.insert(Custom{ "qi", "Wu", 6l });
	hash_set.insert(Custom{ "ba", "Wei", 7l });

	std::cout << "bucket size: " << hash_set.bucket_count() << std::endl;
	for (int i = 0; i < hash_set.bucket_count(); i++)
		std::cout << "bucket #" << i << " has " << hash_set.bucket_size(i) << " items." << std::endl;
  return 0;
}

实现方法2–以struct hash 偏特化的形式实现哈希函数

==必须放在 std 命名空间内==

namespace std 
{
	template<>
	struct hash<Custom>
	{
		std::size_t operator()(const Custom& custom) const
		{
			return hash_val(custom.str_FirstName, custom.str_LastName, custom.l_ID);
		}
	};

	template<>
	struct equal_to<Custom>
	{
		bool operator()(const Custom& c1, const Custom& c2) const
		{
			return c1.str_FirstName == c2.str_FirstName &&
				c1.str_LastName == c2.str_LastName &&
				c1.l_ID == c2.l_ID;
		}
	};
}

// 使用方法
int mian() {
  std::unordered_set<Custom> Custom_set;
  Custom_set.insert(Custom{ "san", "Zhang", 1l });
  ...
  return 0;
}

参考资料

  1. 《C++ STL》 by 侯捷 《40-一个万用的 hash function》
  2. C++ STL源码分析——一个万用的 hash function
搜索