STL里面的一个硬编码的Hash函数

程序员文章站 2022-06-20 20:25:42

...

今天看STL hash_map的源码的时候，出于好奇，我看了一个stl里面是用使用什么哈希函数，把key的转换为哈希值的，猜测这里的哈希函数肯定是基于线性同余变种过来的。为什么要对key做变化？这是因为我们使用map的时候，我们会指定某个键值对：key和value。比如{“name”:“jmh”},在c++内部就会先使用一个pair把这种二元关系对存储下来，然后在对key计算哈希值，用hash值来组织起这些实际的pair。

对于一个键值对key和value，可以逻辑上可以理解为stl内部使用一个三元组（hash(key),key,value）来标识这个数据，然后再根据hash(key)把数据组织起来。

STL里面的哈希函数，主要是分两个情况：一个key本身是int，另外一种是key是字符串的情况。
我看了两个版本的stl源码。
一个是SGI STL 版本的，这个是20年前的代码，比较简单：
key为字符串：

inline size_t __stl_hash_string(const char* s)
{
  unsigned long h = 0; 
  for ( ; *s; ++s)
    h = 5*h + *s;
  
  return size_t(h);
}
__STL_TEMPLATE_NULL struct hash<char*>
{
  size_t operator()(const char* s) const { return __stl_hash_string(s); }
};

__STL_TEMPLATE_NULL struct hash<const char*>
{
  size_t operator()(const char* s) const { return __stl_hash_string(s); }
};

key为整数：直接就是恒等映射了，也就是hash(key)=key

__STL_TEMPLATE_NULL struct hash<int> {
  size_t operator()(int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
  size_t operator()(unsigned int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
  size_t operator()(long x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
  size_t operator()(unsigned long x) const { return x; }

另外一个是VS2013里面的实现：
key为字符串：
我们只看32位的实现，这里就使用了很大的起始值和乘积素数。

inline size_t _Hash_seq(const unsigned char *_First, size_t _Count)
	{	// FNV-1a hash function for bytes in [_First, _First+_Count)
 #if defined(_M_X64) || defined(_LP64) || defined(__x86_64) || defined(_WIN64)
	static_assert(sizeof(size_t) == 8, "This code is for 64-bit size_t.");
	const size_t _FNV_offset_basis = 14695981039346656037ULL;
	const size_t _FNV_prime = 1099511628211ULL;

 #else /* defined(_M_X64), etc. */
	static_assert(sizeof(size_t) == 4, "This code is for 32-bit size_t.");
	const size_t _FNV_offset_basis = 2166136261U;
	const size_t _FNV_prime = 16777619U;
 #endif /* defined(_M_X64), etc. */

	size_t _Val = _FNV_offset_basis;
	for (size_t _Next = 0; _Next < _Count; ++_Next)
		{	// fold in another byte
		_Val ^= (size_t)_First[_Next];
		_Val *= _FNV_prime;
		}

 #if defined(_M_X64) || defined(_LP64) || defined(__x86_64) || defined(_WIN64)
	static_assert(sizeof(size_t) == 8, "This code is for 64-bit size_t.");
	_Val ^= _Val >> 32;

 #else /* defined(_M_X64), etc. */
	static_assert(sizeof(size_t) == 4, "This code is for 32-bit size_t.");
 #endif /* defined(_M_X64), etc. */

	return (_Val);
	}

key为整数：

	size_t operator()(const _Kty& _Keyval) const
		{	// hash _Keyval to size_t value by pseudorandomizing transform
		long _Quot = (long)(hash_value(_Keyval) & LONG_MAX);
		ldiv_t _Qrem = _CSTD ldiv(_Quot, 127773);

		_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
		if (_Qrem.rem < 0)
			_Qrem.rem += LONG_MAX;
		return ((size_t)_Qrem.rem);
		}

首先这个函数是把keyval在做一次映射，把它的值转换为新的数字，这么做的好处是使得hash_map的性能不会因为输入数据的随机性的优劣而有较大的的变化，因为不管输入数据key随机与否，这个函数函数都会把哈希值搞的很随机。

这个函数就很有意思了，居然会硬编码 16807和12773,2836，这些数字看起来很奇怪呀？？？这几个数字意味着什么呢？

查了文献才知道，这几个数还大有文章！

这几个数来自基于线性同余的伪随机数发生器，一般来说：
伪随机数发生器的核心步骤就两个：
$1.v_{next}=v_{previous}*a \%\space m$
$2.v_{previous}=v_{next}$
通常m会取成 $2^{31}-1$ 。
而这个不同的 $a$ 的取值就大有讲究了，不同的a 会导致不同的循环周期。这里的循环周期是指，令 $v_{previous}$ 为一个初始值 $x$ 出发，不断的计算 $v_{next}$ ,如此往复，直到 $v_{next}$ 又回到 $x$ 初始值，其中的迭代次数就是循环周期了。显然循环周期越长越好，因为循环周期越长，随机数能取的值就越多，当把这种随机数当做hash值的时候它就越不会发生冲突。

经过上个世纪70年代的研究，人们发现当 $a$ 取 $16807$ 这个素数的时候，不管初始值 $x$ 取啥，它的循环周期特别大就是等于 $2^{31}-1$ 。

// The sequence of values this PRNG should produce includes:
// 
//      Result     Number of results after seed of 1
//
//       16807          1
//   282475249          2
//  1622650073          3
//   984943658          4
//  1144108930          5
//   470211272          6
//   101027544          7
//  1457850878          8
//  1458777923          9
//  2007237709         10
//
//   925166085       9998
//  1484786315       9999
//  1043618065      10000
//  1589873406      10001
//  2010798668      10002
//
//  1227283347    1000000
//  1808217256    2000000
//  1140279430    3000000
//   851767375    4000000
//  1885818104    5000000
//
//   168075678   99000000
//  1209575029  100000000
//   941596188  101000000
//
//  1207672015 2147483643
//  1475608308 2147483644
//  1407677000 2147483645
//           1 2147483646
//       16807 2147483647

至于12773,2836这两个数，存在以下关系：

#define a 16807         /* multiplier */
#define m 2147483647L   /* 2**31 - 1 */
#define q 127773L       /* m div a */
#define r 2836          /* m mod a */

而且有：

def hash1(val):
	return (val * 16801)%constm

def hash2(val):
	q=val//127773
	r=val%127773
	return 16807*r-2836*q

两个函数是等价的！VS2013使用第二种实现，就不用模运行了，只需要除法即可。