【C++篇】哈希表

目录

一，哈希概念

1.1，直接定址法

1.2，哈希冲突 

1.3，负载因子

二，哈希函数

2.1，除法散列法 /除留余数法

2.2，乘法散列法

2.3，全域散列法

三，处理哈希冲突

3.1，开放定址法

线性探测

二次探测

双重探测

3.2，开放定址法代码实现

哈希表扩容问题 

key不能取模的问题 

 完整代码实现

3.3，链地址法

哈希表扩容问题 

链地址法代码实现

小结：

一，哈希概念

哈希（hash)又称散列，是一种组织数据的方式。从译名看，有散乱排列的意思。本质就是通过哈希函数把关键字key和存储位置建立一个映射关系，查找时通过这个哈希函数计算出key存储的位置，实现快速查找。

说白了，hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于hash函数建立的一种查找表。

1.1，直接定址法

当关键字的范围比较集中时，直接定址法就是非常简单高效的方法。比如一组关键字的值在[0,99]之间，那么我们开一个100大小的数组，每个关键字的值直接就是存储位置的下标。再比如一组数据a~z的字符，我们可以开一个大小为26的数组，每个关键字的acsll值减去 a的ascll值，就是对应的存储位置下标。也就是说直接定址法是用关键字计算出一个绝对位置或相对位置。

本题链接：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution {

public:

    int firstUniqChar(string s) {

        int hash[26]={0};

        //统计次数

        for(auto& ch:s)

        {

            hash[ch-'a']++;

        }

        for(int i=0;i<s.size();i++)

        {

            if(hash[s[i]-'a']==1)

            return i;

        }

        return -1;

    }

};

1.2，哈希冲突 

不同的key值产生相同的地址，即H（key1)=H（key2)。这种问题叫做哈希冲突或哈希碰撞。

1.3，负载因子

假设哈希表已经存储N个值，哈希表的大小为M，那么负载因子=N/M。负载因子越大，代表哈希冲突的概率越高，空间利用率越高；负载因子越小，代表哈希冲突的概率越低，空间利用率越低。

二，哈希函数

两个不同的key值可能 会映射到同一个位置，这个问题叫做哈希冲突。理想情况是找一个哈希函数避免冲突，但是实际场景中，冲突不可避免，所以我们尽可能设计出好的哈希函数，来减少哈希冲突。

哈希函数的设计可能有很多讲究，比如要考虑均匀性、确定性、高效性等等。不同的应用场景可能需要不同的哈希函数。比如，非加密的哈希函数可能更注重速度，而加密的哈希函数则需要更高的安全性，防止被逆向或者找到碰撞。

2.1，除法散列法 /除留余数法

• 除法散列法也叫除留余数法，假设哈希表的大小为M，那么通过key除以M的余数作为映射的下标。也就是哈希函数为H(key)=key%M。
• 当使用 除法散列法时，应避免M的大小为某些值，比如2的幂，10的幂等。如果是2的x次方，那么key%2^x相当于保留key的二进制前x位。那么前x位二进制相同的key值，计算出的哈希值都是一样的，就会加剧哈希冲突。原因：key%2^x，相当于key&(2^x-1)，其中 2^x-1的二进制表示中前x均为1，其余为均为0，所以最后按位与的结果取决于key的前x位。【见下图】

• 当使用除法散列 法时，建议M取不太接近2的整数次幂的一个质数（素数）

2.2，乘法散列法

• 乘法散列法对哈希表的大小M没有要求，它的大思路第一步：用关键字key乘上A(0<A<1)，并抽取出key*A的小数部分。第二步：再用M乘以key*A的小数部分，再向下取整。
• H(key)=floor(M*((A*key)%1.0))，其中floor表示对表达式进行向下取整。0<A<1，这里最重要的时A的值该如何设定。Knuth认为设为黄金分割点比较好

2.3，全域散列法

• 如果存在一个对手，他针对我们的哈希函数，特意构造出一个发生严重冲突的数据集。比如，让所有关键字落入同一个位置，这种情况是可以存在的。只要哈希函数公开且时确定的，就可以实现次攻击。解决此方法就是给哈希函数增加随机性，攻击者就无法找出确定的导致冲突 加剧的数据。这种方法叫做全域散列。
• H[a][b](key)=((a*key+b)%P)%M。P选择一个足够大的质数，a可以任意选[1,P-1]之间的一个整数，b可以选[0,P-1]之间的任意整数，这些函数就构成了一个P*(P-1)组全域散列函数组。假设P=17，M=6，a=3，b=4，则H[3][4]（8）=((3*8+4)&17)%6=5。
• 需要注意的是，每次初始化哈希表时，随机选取全域散列函数组中的一个散列（哈希）函数使用，后序增删查改都固定使用这个散列函数。否则每次哈希都是随机选一个散列函数，那么插入是一个散列函数，查找又是另一个散列函数，就会导致查找不到插入的key值。

总结：实践中，哈希表一般是选择除法散列法作为哈希函数。当然哈希表无论选择什么哈希函数，都无法避免哈希冲突，那么插入数据时，如何解决哈希冲突呢？主要有两种方法，开放定址法和链地址法。

三，处理哈希冲突

3.1，开放定址法

开放定址法中，所有元素都放到哈希表里。当一个关键字key用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置存储。这里的规则有三种：线性探测，二次探测，双重探测。

线性探测

• 从发生冲突的位置开始，依次向后进行 线性探测，直到寻找到一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头 的位置。
• H(key)=key%M=hash0，其中hash0代表映射的位置，如果该位置没有数据，则将key填入 。如果hash0位置已经存在数据，也就是hash0位置冲突了，则线性探测公式为：Hc(key)=(hash0+i)%M=hashi，i=0,1,2,3...,M-1。其中hashi就是经过线性探测找到没有存储数据的位置，再将key填入。

下面演示{19,30,5,36,13,20,21,12} 等映射到M=11的表中.

• 线性探测问题，假设hash0位置连续冲突，hash0,hash1,hash2已经存储数据了，后序映射到hash0，hash1，hash2的值都会 争夺hash3位置，这种现象叫做群集/堆积。下面的二次探测可以解决这个问题。

二次探测

• 从发生冲突的位置，依次左右按二次方跳跃式探测，直到寻找到下一个没有存储数据的位置为止。如果 往右走到哈希表尾，则回绕到哈希表头的位置；如果往左走到哈希表头，则会绕道哈希表尾的位置。
• H(key)=key%M=hash0，hash0位置冲突了，则二次探测公式为，Hc(key)=(hash0+/-i*i)%M，i=1,2,3..,M/=hashi.
• 二次探测结果hashi可能为负数，当hashi<0时，hashi+=M。

下面演示{19,30,52,63,11,22}映射到M=11的表中

双重探测

• 第⼀个哈希函数计算出的值发生冲突，使用第二个哈希函数计算出⼀个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止。
• H(key)=key%M=hash0，hash0位置冲突了，则双重探测公式为：Hc(key)=(hash0+i*H2(key))%M=hashi，i=1,2,3,...,M

3.2，开放定址法代码实现

开放定址法在时间中不如下面的连地址法，所以我们选择简单的线性探测实现即可。

结构：

//当前位置的状态
//存在  空  已删除
enum State
{
	EXIT,
	EMPTY,
	DELETE
};

template <class k,class v>
struct HashData
{
	pair<k, v> _kv;
	State _state = EMPTY;
};

template <class k,class v>
class HashTable
{
private:
	vector<Hashdata<k, v>> _tables; //哈希表
	size_t n = 0;                   //表中存储数据的个数
};

要注意的是这⾥需要给每个存储值的位置加⼀个状态标识，否则删除⼀些值以后，会影响后⾯冲突的值的查找。如下图，我们删除30，会导致查找20失败，当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE}，删除30就可以不用删除值，而是把状态改为DELETE，那么查找20时遇到EMPTY才停，就可以找到20。

哈希表扩容问题 

这里我们哈希表负载因子控制在0.7，当负载因子到0.7以后我们就需要扩容了，我们如果还是按照2倍扩 容，但是同时我们要保持哈希表大小是一个质数，第一个是质数，2倍后就不是质数了。所以我们可以按照sgi版本的哈希表使用的方法。，给了⼀个近似2倍的质数表，每次去质数表获取扩容后的大小。

inline unsigned long __stl_next_prime(unsigned long n)
{
    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;
}

在需要扩容时，调用__stl_next_prime(n），在__stl_prime_list数组中查找第一个大于等于n的数组并返回。

key不能取模的问题 

当key是string/Date等类型时，key不能取模，那么我们需要给HashTable增加⼀个仿函数，这个仿函 数⽀持把key转换成⼀个可以取模的整形，如果key可以转换为整形并且不容易冲突，那么这个仿函数就用默认参数即可，如果这个Key不能转换为整形我们就需要自己实现⼀个仿函数传给这个参数，实 现这个仿函数的要求就是尽量key的每个值都参与到计算中，让不同的key转换出的整形值不同。string做哈希表的key值很常见，我们可以考虑把string特化一下。

template <class k>
class HashFunc
{
    size_t operator()(const k& key)
    {
        return (size_t)key;
    }
};
//特化
template<>
struct HashFunc<string>
{
    // 字符串转换成整形，可以把字符ascii码相加即可
    // 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
    // 这⾥我们使⽤BKDR哈希的思路，用上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131等效果会比较好
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (auto ch : s)
        {
            hash += ch;
            hash *= 131;
        }
        return hash;
    }
};
 

 完整代码实现

//当前位置的状态
//存在  空  已删除
enum State
{
	EXIT,
	EMPTY,
	DELETE
};

template <class k,class v>
struct HashData
{
	pair<k, v> _kv;
	State _state = EMPTY;
};

template <class k>
class HashFunc
{
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};
//特化
template<>
struct HashFunc<string>
{
	// 字符串转换成整形，可以把字符ascii码相加即可
	// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
	// 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数，这个质数⼀般去31, 131等效果会比较好
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};

template<class k, class v, class Hash = HashFunc<k>>
class HashTable
{
public:
	HashTable()
		:_tables(__stl_next_prime(0))
		, _n(0)
	{}
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		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;
	}


	bool insert(const pair<k, v>& kv)
	{
		Hash hash;
		//负载因子>=0.7  扩容
		if (_n * 10 / _tables.size() >= 7)
		{
			//创建一个新表
			HashTable<k, v, Hash> newht;
			//扩容
			newht._tables.resize(__stl_next_prime(_tables.size() + 1));
			//旧表数据映射到新表
			for (auto& data : _tables)
			{
				if (data._state == EXIST)
					newht.insert(data._kv);
			}
			//_tables=newht._tables;
			_tables.swap(newht._tables);
		}

		size_t hash0 = hash(kv.first) % _tables.size();
		size_t hashi = hash0;
		int i = 1;
		while (_tables[hashi]._state == EXIST)
		{
			//线性探测
			hashi = (hash0 + i) % _tables.size();//防止越界
			i++;
		}

		_tables[hashi]._kv = kv;
		_tables[hashi]._state = EXIST;
		_n++;

		return true;
	}

	HashData<k, v>* find(const k& key)
	{
		Hash hash;
		size_t hash0 = hash(key) % _tables.size();
		size_t hashi = hash0;
		int i = 1;
		while (_tables[hashi]._state != EMPTY)
		{
			if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
			{
				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;
		}
	}
private:
	vector<HashData<k, v>> _tables;
	size_t _n;
};

3.3，链地址法

开放定址法中所有的元素都放到哈希表里，链地址法中所有的数据不再直接存储在哈希表中。哈希表 中存储一个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下面，链地址法也叫做拉链法或者哈希桶。

下面演示{19,30,5,36,13,20,21,12,24,96} 等这一组值映射到M=11的表中

哈希表扩容问题 

开放定址法负载因子必须小于1，链地址法的负载因子就没有限制了，可以大于1。负载因子越大，哈 希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越低，空间利用率越低；STL中的unordered_map和unordered_set最大复杂因子进本控制在1，大于1就开始扩容。

链地址法代码实现

//链地址法
//哈希桶
template<class k, class v>
struct HashNode
{
	pair<k, v> _kv;
	HashNode<k, v>* _next;
	HashNode(const pair<k, v>& kv)
		:_kv(kv)
		, _next(nullptr)
	{}
};
template<class  k, class v>
class Hash_bucket
{
public:
	typedef HashNode<k, v> Node;
	Hash_bucket()
		:_tables(__stl_next_prime(0))
		, _n(0)
	{}
	~Hash_bucket()
	{
		for (int i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;

				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		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;
	}
    
	bool insert(const pair<k, v>& kv)
	{
		//防止键值冗余
		if (find(kv.first))
			return false;

		//负载因子>=1时，扩容
		if (_n / _tables.size() >= 1)
		{
			//创建新表
			vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
			for (int i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
                //直接将旧表中的节点插入到新表中 所映射的位置
				while (cur)
				{
					Node* next = cur->_next;
					//直接插入到新表
					size_t hashi = cur->_kv.first % newtables.size();
					cur->_next = newtables[hashi];
					newtables[hashi] = cur;

					cur = next;
				}
			}
			_tables.swap(newtables);
		}

		size_t hashi = kv.first % _tables.size();
		Node* newnode = new Node(kv);
		//头插到新表
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		++_n;

		return true;
	}
	Node* find(const k& key)
	{
		size_t hashi = key % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
				return cur;
			cur = cur->_next;
		}
		return nullptr;
	}
	bool erase(const k& key)
	{
		size_t hashi = key % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				--_n;

				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}

		return false;
	}

private:
	vector<Node*> _tables;
	size_t _n;
};

小结：

哈希表这种数据结构，是利用哈希函数来快速定位数据的位置，然后存储到数组中的相应位置。

这样在查找的时候，时间复杂度可以接近O(1)，非常高效。不过如果多个键被哈希到同一个位置，就会发生冲突，这时候需要解决冲突的方法，比如链地址法或者开放寻址法。

那哈希表的实现原理大概是怎样的呢？当插入一个键值对时，首先用哈希函数计算键的哈希值，然后根据哈希值找到对应的数组下标，如果该位置已经有元素了，就用链表或者其他方式处理冲突，然后存储进去。查找的时候同样计算哈希值，找到位置后，如果该位置有多个元素，需要遍历链表进行查找。好的哈希函数应该尽量均匀分布，减少冲突，这样哈希表的效率才会高。