【C++】哈希表的实现（开放定址法）

1.3 负载因子

        设哈希表中已经映射存储了N个值，哈希表的⼤⼩为M，那么 负载因子=  ，负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等，他的英⽂为load factor。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低。

1.4 将关键字转为整数

1.5 哈希函数

除法散列法/除留余数法

• 除法散列法也叫做除留余数法，顾名思义，假设哈希表的⼤⼩为M，那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		 1572869, 3145739, 6291469, 12582917, 25165843,
		 50331653, 100663319, 201326611, 402653189, 805306457,
		 1610612741, 3221225473, 4294967291
		
	};
 const unsigned long* first = __stl_prime_list;
 const unsigned long* last = __stl_prime_list + __stl_num_primes;
 const unsigned long* pos = lower_bound(first, last, n);
 return pos == last ? *(last - 1) : *pos;
}

然后我们用这个表，扩容的地方修改一下。

//newtables._tables.resize(_tables.size() * 2);//2倍扩

//找一个最接近当前空间大小的素数为扩容大小
newtables._tables.resize(__stl_next_prime(_tables.size()));

template<class K, class V>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0)) //先给一个最接近0的素数开空间
		,_n(0)
	{}

	inline unsigned long __stl_next_prime(unsigned long n) //给的一个素数表
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			 1572869, 3145739, 6291469, 12582917, 25165843,
			 50331653, 100663319, 201326611, 402653189, 805306457,
			 1610612741, 3221225473, 4294967291
			
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	HashData<K, V>* Find(const K& key)
	{
		size_t hash0 = key % _tables.size();
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state != EMPTY) //存在或删除状态都要找
		{
			//要判断状态为存在且相等，才是找到了
			//只判断相等的话，删除后还是会被找到
			if (_tables[hashi]._state == EXIST
				&& _tables[hashi]._kv.first == key)//找到了
			{
				return &_tables[hashi];//返回他的地址
			}
			//没找到就线性探测
			hashi = (hash0 + i) % _tables.size();
			++i;
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_state = DELETE;
			return true;
		}
		else
			return false;
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
			return false;
		//扩容
		if (_n * 10 / _tables.size() >= 7)//当负载因子>=0.7时
		{
			HashTable<K, V> newtables;

			//newtables._tables.resize(_tables.size() * 2);//2倍扩

			//找一个最接近当前空间大小的素数为扩容大小
			newtables._tables.resize(__stl_next_prime(_tables.size()));

			for (auto& data : _tables)//遍历旧表
			{
				if (data._state == EXIST)//旧表有数据的
				{
					newtables.Insert(data._kv);//在新表直接调用Insert插入
				}
			}
			_tables.swap(newtables._tables);//新表和旧表交换
			//_tables = newtables._tables;//赋值的写法可行，但效率低
		}

		size_t hash0 = kv.first % _tables.size(); //下标映射
		size_t hashi = hash0;
		size_t i = 1;
		while (_tables[hashi]._state == EXIST) //位置被霸占了
		{
			hashi = (hash0 + i) % _tables.size();//往后找空位（线性探测）
			++i;
		}
		_tables[hashi]._kv = kv;//插入数据
		_tables[hashi]._state = EXIST;//改状态
		++_n;
		return true;
	}

private:
	vector<HashData<K, V>> _tables;
	int _n; //表中存储数据个数
};

key不能取模问题

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函数⽀持把key转换成⼀个可以取模的整形。

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

//模板参数多加一个仿函数
template<class K, class V, class Hash = HashFunc<K>> //HashFunc当缺省
class HashTable
{
    //...
}

bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
		return false;
	//扩容
	if (_n * 10 / _tables.size() >= 7)//当负载因子>=0.7时
	{
		HashTable<K, V, Hash> newtables; //注意这里也要改成3个模板参数
        //...
	}

	Hash hash;
	size_t hash0 = hash(kv.first) % _tables.size(); //下标映射,用仿函数
    //...
}

HashData<K, V>* Find(const K& key)
{
	Hash hash;
	size_t hash0 = hash(key) % _tables.size(); //用仿函数
    //...
}

上面写的是一个默认的仿函数，这个仿函数还是不能将string转为整形，我们要自己为string专门写一个仿函数。

//test.cpp
struct stringHashFunc
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
            hash *= 131;
		}
		return hash;
	}
};

字符串转为整形我们可以 把全部字符ASCII码值乘以一个131（其他值也可以，但是想知道为什么是乘131，去搜BKDR哈希），然后加起来。如果不乘一个数的话，有的字符串不同，但ASCII码值相加是一样的，更容易发生冲突。

//test.cpp
struct stringHashFunc
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
            hash *= 131;
		}
		return hash;
	}
};

int main()
{
	const char* arr[] = { "hello", "left", "sort", "passage" };
	HashTable<string, string, stringHashFunc> s; //传三个参数
	for (auto& e : arr)
	{
		s.Insert({ e, e });
	}
	return 0;
}

第三个参数不传，就用缺省值，就是之前实现的那个HashFunc，传了就是相应的仿函数。

而且写了这个仿函数，传负数也可以了。

int main()
{
	int arr[] = { -19,30,-5,36,13,-20,21,-12,-15 };
	HashTable<int, int> ht; //不传第三个参数
	for (auto e : arr)
	{
		ht.Insert({ e, e });
	}
	return 0;
}

此时用的仿函数就是前面的HashFunc，把负数强转为size_t类型。

对string的仿函数特殊处理

由于我们经常用string类型做key，要额外多传一个仿函数比较麻烦，这里可以对string的仿函数进行一个特化，写法如下。

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string> //特化
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
            hash *= 131;
		}
		return hash;
	}
};

特化的知识在【C++】模板（进阶）2.2 类模板的特化 中有详细讲解。