本篇内容我们就来学习哈希表

        哈希是一个十分重要的概念，在计算机中应用十分广泛，如哈希表、哈希算法、位图等等。本期我们就来学习哈希表的底层并模仿其底层实现

        相关代码已经上传至作者的个人gitee：楼田莉子/CPP代码学习喜欢请点个赞谢谢。

目录

哈希的概念        

直接定址法

哈希冲突

负载因子

哈希函数

        除法散列法/除留余数法(重点)

        乘法散列法（了解）

        全域散列法（了解）

        其他方法（了解）

处理哈希冲突

        开放定址法

        线性探测

        二次探测

        双重散列（了解）

        链地址法

        处理思路

        扩容

        极端场景

开放定址法代码实现

链地址法代码实现

哈希的概念
        

        哈希(hash)⼜称散列，是⼀种组织数据的⽅式。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系，查找时通过这个哈希函数计算出Key存储的位置，进⾏快速查找

直接定址法

        当关键字的范围⽐较集中时，直接定址法就是⾮常简单⾼效的⽅法，⽐如⼀组关键字都在[0,99]之间，那么我们开⼀个100个数的数组，每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟，那么我们开⼀个26个数的数组，每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置

        这个方法我们在计数排序中使用过，在之前的算法课中也使用过

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

class Solution
{
public:
    int firstUniqChar(string s) 
    {
        int count[26]={0};
        //每个字符出现的次数
        for(auto e:s)
        {
            count[e-'a']++;
        }
        for(size_t i=0;i<s.size();++i)
        {
            if(count[s[i]-'a']==1)
            {
                return i;
            }
            
        }
        return -1;
    }
};

        直接定址法只适用于范围集中的数值范围

哈希冲突

        直接定址法的缺点也⾮常明显，当关键字的范围⽐较分散时，就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值，我们要映射到⼀个M个空间的数组中(⼀般情况下M >= N)，那么就要借助哈希函数(hash function)hf，关键字key被放到数组的h(key)位置，这⾥要注意的是h(key)计算出的值必须在[0, M)之间。

        但是问题显而易见，两个不同的key可能会映射到同⼀个位置去，这种问题我们叫做哈希冲突，或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突，但是实际场景中，冲突是不可避免的，所以我们尽可能设计出优秀的哈希函数，减少冲突的次数，同时也要去设计出解决冲突的⽅案。

        我们将关键字映射到数组中位置，⼀般是整数好做映射计算，如果不是整数，我们要想办法转换成整数

负载因子

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

哈希函数

        ⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中，但是实际中却很难做到，但是我们要尽量往这个⽅向去考量设计

        除法散列法/除留余数法(重点)

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

        当使⽤除法散列法时，要尽量避免M为某些值，如2的幂，10的幂等。如果是2^x ，那么key %2^x本质相当于保留key的后X位，那么后x位相同的值，计算出的哈希值都是⼀样的，就冲突了。如：{63 , 31}看起来没有关联的值，如果M是16，也就是 ，那么计算出的哈希值都是15，因为63的⼆进制后8位是 00111111，31的⼆进制后8位是 00011111。如果是 10^x，就更明显了，保留的都是10进值的后x位，如：{112, 12312}，如果M是100，也就是10^2 ，那么计算出的哈希值都是12。

        当使⽤除法散列法时，建议M取不太接近2的整数次幂的⼀个质数(素数)。

        项目实践中实现方法是有很多的。Java的HashMap采⽤除法散列法时就是2的整数次幂做哈希表的⼤⼩M，这样玩的话，就不⽤取模，⽽可以直接位运算，相对⽽⾔位运算⽐模更⾼效⼀些。但是他不是单纯的去取模，⽐如M是2^16次⽅，本质是取后16位，那么⽤key’ =key>>16，然后把key和key' 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围

内，但是尽量让key所有的位都参与计算，这样映射出的哈希值更均匀⼀些即可。所以我们上⾯建

议M取不太接近2的整数次幂的⼀个质数的理论是⼤多数数据结构书籍中写的理论吗，但是实践中，灵活运⽤，抓住本质，⽽不能死读书。（了解）

        乘法散列法（了解）

        乘法散列法对哈希表⼤⼩M没有要求，他的⼤思路第⼀步：⽤关键字 K 乘上常数 A (0<A<1)，并抽取出 k*A 的⼩数部分。第⼆步：后再⽤M乘以k*A 的⼩数部分，再向下取整。

        对于公式：

        其中floor表⽰对表达式进⾏下取整。A属于（0，1）。其中floor表⽰对表达式进⾏下取整。
        Knuth认为下图所示的数值是比较好的

        乘法散列法对哈希表⼤⼩M是没有要求的，假设M为1024，key为1234，A = 0.6180339887, A*key= 762.6539420558，取⼩数部分为0.6539420558, M×((A×key)%1.0) = 0.6539420558*1024 =669.6366651392，那么h(1234) = 669。

        全域散列法（了解）

        如果用前面的方式构造哈希函数，那么哈希函数的安全性不是很高，很容易被人攻击，因此我们要用新的方式来构造哈希函数

        只要散列函数是公开且确定的，就可以实现此攻击。解决⽅法⾃然是⻅招拆招，给散列函数增加随机性，攻击者就⽆法找出确定可以导致最坏情况的数据。这种⽅法叫做全域散列

        对于公式：

        P需要选⼀个⾜够⼤的质数，a可以随机选[1,P-1]之间的任意整数，b可以随机选[0,P-1]之间的任意整数，这些函数构成了⼀个P*(P-1)组全域散列函数组。

假设P=17，M=6，a = 3， b = 4, 则 

        

        需要注意的是每次初始化哈希表时，随机选取全域散列函数组中的⼀个散列函数使⽤，后续增删查改都固定使⽤这个散列函数，否则每次哈希都是随机选⼀个散列函数，那么插⼊是⼀个散列函数，查找⼜是另⼀个散列函数，就会导致找不到插⼊的key了。

        其他方法（了解）

        上⾯的⼏种⽅法是《算法导论》书籍中讲解的⽅法

        《殷⼈昆 数据结构：⽤⾯向对象⽅法与C++语⾔描述 （第⼆版）》和 《[数据结构(C语⾔版)].严蔚敏_吴伟⺠》等教材型书籍上⾯还给出了平⽅取中法、折叠法、随机数法、数学分析法等，这些⽅法相对更适⽤于⼀些局限的特定场景，有兴趣可以去看看这些书籍。

处理哈希冲突

        开放定址法

        在开放定址法中所有的元素都放到哈希表⾥，当⼀个关键字key⽤哈希函数计算出的位置冲突了，则按照某种规则找到⼀个没有存储数据的位置进⾏存储，开放定址法中负载因⼦⼀定是⼩于的。

        线性探测

        从发⽣冲突的位置开始，依次线性向后探测，直到寻找到下⼀个没有存储数据的位置为⽌，如果⾛到哈希表尾，则回绕到哈希表头的位置。

        对于哈希函数：

        

        hash0位置冲突了，则线性探测公式为：

        因为负载因⼦⼩于1，则最多探测M-1次，⼀定能找到⼀个存储key的位置。

        线性探测的⽐较简单且容易实现，线性探测的问题假设，hash0位置连续冲突，hash0，hash1，hash2位置已经存储数据了，后续映射到hash0，hash1，hash2，hash3的值都会争夺hash3位置，这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。

        下⾯演⽰ {19,30,5,36,13,20,21,12} 等这⼀组值映射到M=11的表中。

        二次探测

        从发⽣冲突的位置开始，依次左右按⼆次⽅跳跃式探测，直到寻找到下⼀个没有存储数据的位置⽌，如果往右⾛到哈希表尾，则回绕到哈希表头的位置；如果往左⾛到哈希表头，则回绕到哈希表尾的位置；

        对于哈希函数：

        hash0位置冲突了，则⼆次探测公式为：

        在二次探测中当哈希函数为：

        当hashi<0时，需要hashi += M
        下⾯演⽰ {19,30,52,63,11,22} 等这⼀组值映射到M=11的表中。

        双重散列（了解）

        第⼀个哈希函数计算出的值发⽣冲突，使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值，不断往后探测，直到寻找到下⼀个没有存储数据的位置为⽌。

        对于哈希函数：

        hash0位置冲突了，则双重探测公式为：

        要求 <M且 和M互为质数，有两种简单的取值⽅法：

        1、当M为2整数幂时，

        2、当M为质数时，

        保证与M互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群。若最大公因数，那么所能寻址的位置的个数为 ，使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说，若初始探查位置为1，偏移量为3，整个散列表⼤⼩为12，那么所能寻址的位置为{1, 4, 7, 10}，寻址个数为12/gcd(12,3)=4

        下⾯演⽰ {19,30,52,74} 等这⼀组值映射到M=11的表中，设 h2(key) = key%10 + 1

        链地址法

        处理思路

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

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

        扩容

        开放定址法负载因⼦必须⼩于1，链地址法的负载因⼦就没有限制了，可以⼤于1。负载因⼦越⼤，哈希冲突的概率越⾼，空间利⽤率越⾼；负载因⼦越⼩，哈希冲突的概率越低，空间利⽤率越低；stl中unordered_xxx的最⼤负载因⼦基本控制在1，⼤于1就扩容，我们下⾯实现也使⽤这个⽅式。

        极端场景

        如果极端场景下，某个桶特别⻓怎么办？我们可以考虑使⽤全域散列法，这样就不容易被针对了。

        但是假设不是被针对了，⽤了全域散列法，但是偶然情况下，某个桶很⻓，查找效率很低怎么办？这⾥在Java8的HashMap中当桶的⻓度超过⼀定阀值(8)时就把链表转换成红⿊树。

        ⼀般情况下，不断扩容，单个桶很⻓的场景还是⽐较少的。

开放定址法代码实现

#pragma once
#include<vector>
#include<utility>
#include<string>
using namespace std;
namespace HashTable1
{
	//哈希表两大要求：支持相等、能够取模
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _status = EMPTY;
	};
	//enum Status
	//{
	//	EXIST,
	//	EMPTY,
	//	DELETE
	//};
	//template<class K, class V>
	//struct HashData
	//{
	//	std::pair<K, V>
	//	Status status=EMPTY;
	//};
	//将key转为整型
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};
	//string单独实现
	template<>
	struct HashFunc<string>
	{
		// BKDR
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash += ch;
				hash *= 131;
			}

			return hash;
		}
	};
	//模板特化
	//避免字符串哈希冲突
	template<>
	struct HashFunc<string>
	{
		// BKDR
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash += ch;
				hash *= 131;
			}

			return hash;
		}
	};
	struct StringHashFunc
	{
		// BKDR
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash += ch;
				hash *= 131;
			}

			return hash;
		}
	};

	template<class K, class V, class Hash = HashFunc<K>>
	//template<class K, class V，class Hash= HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
			:table(11), size(0)
		{
		}
		//来源STL源码：https://github.com/microsoft/STL/blob/master/stl/inc/hash_table.h
		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;
		}
		bool Insert(const pair<K, V>& kv)
		{
			//去冗余
			if (Find(kv.first) != nullptr)
			{
				return false;
			}
			//负载因子》=0.7时，扩容
			if ((double)size >= table.size() * 0.7)
			{
				//旧思路
				//std::vector<HashData<K, V>> newtable(table.size() * 2);
				////遍历旧值将其映射到新表中
				//for (auto& data : table)
				//{
				//	if (data._status == EXIST)
				//	{
				//		newtable.push_back(data);
				//	}
				//}
				//table.swap(newtable);
				//新思路
				HashTable<K, V, Hash> newHT;
				newHT.table.resize(table.size() * 2);
				for (auto& data : table)
				{
					if (data._status == EXIST)
					{
						newHT.Insert(data._kv);
					}
				}
				table.swap(newHT.table);
			}
			Hash hs;
			size_t hash0 = hs(kv.first) % table.size();
			size_t i = 1;
			size_t hashi = hash0;
			//进行线性探测
			//先比较状态再比较key
			while (table[hashi]._status == EXIST)
			{
				hashi = (hash0 + i) % table.size();
				++i;
			}
			table[hashi]._kv = kv;
			table[hashi]._status = EXIST;
			++size;
			return true;
		}
		HashData<K, V>* Find(const K& key)
		{
			Hash hs;
			size_t hash0 = hs(key) % table.size();
			size_t i = 1;
			size_t hashi = hash0;
			//进行线性探测
			while (table[hashi]._status != EMPTY)
			{
				//返回地址
				if (table[hashi]._status == EXIST && table[hashi]._kv.first == key)
				{
					return &table[hashi];
				}
				hashi = (hash0 + i) % table.size();
				++i;
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			auto* It = Find(key);
			if (It != nullptr)
			{
				It->_status = DELETE;
				--size;
				return true;
			}
			else
			{
				return false;
			}

		}

		void Print()
		{
			cout << "Hash Table Content:" << endl;
			for (size_t i = 0; i < table.size(); ++i)
			{
				if (table[i]._status == EXIST)
				{
					cout << "Index " << i << ": Key=" << table[i]._kv.first
						<< ", Value=" << table[i]._kv.second << endl;
				}
				else if (table[i]._status == DELETE)
				{
					cout << "Index " << i << ": <DELETED>" << endl;
				}
				else
				{
					cout << "Index " << i << ": <EMPTY>" << endl;
				}
			}
			cout << "Size: " << size << ", Capacity: " << table.size() << endl;
		}
	private:
		vector<HashData<K, V>> table;
		size_t size = 0;//有效数据个数
	};

}

链地址法代码实现

        

#pragma once
#include<vector>
#include<utility>
#include<string>
using namespace std;
namespace HashTable2
{
    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)
        {
        }
    };
    //将key转为整型
    template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };
    //string单独实现
    template<>
    struct HashFunc<string>
    {
        // BKDR
        size_t operator()(const string& str)
        {
            size_t hash = 0;
            for (auto ch : str)
            {
                hash += ch;
                hash *= 131;
            }

            return hash;
        }
    };
    //模板特化
    //避免字符串哈希冲突
    template<>
    struct HashFunc<string>
    {
        // BKDR
        size_t operator()(const string& str)
        {
            size_t hash = 0;
            for (auto ch : str)
            {
                hash += ch;
                hash *= 131;
            }

            return hash;
        }
    };
    struct StringHashFunc
    {
        // BKDR
        size_t operator()(const string& str)
        {
            size_t hash = 0;
            for (auto ch : str)
            {
                hash += ch;
                hash *= 131;
            }

            return hash;
        }
    };
    template<class K, class V,class Hash= HashFunc<K>>
    class HashBucket
    {
        typedef HashNode<K, V> Node;
    public:
        HashBucket() 
            : table(11,nullptr), size(0) 
        {
        }
        ~HashBucket()
        {
            for (int i = 0; i < table.size(); i++)
            {
                Node* cur = table[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                table[i] = nullptr;
            }
        }
        //来源STL源码：https://github.com/microsoft/STL/blob/master/stl/inc/hash_table.h
        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;
        }
        bool Insert(const pair<K, V>& kv)
        {
            size_t hashi = kv.first % table.size();
            Hash  hs;
            //负载因子为1 的时候扩容
            if (size == table.size())
            {
                //旧思路
                //HashBucket<K, V> newHT;
                //newHT.table.resize(table.size() * 2);
                ////将旧表数据映射到新表中
                //for (auto& cur : table)
                //{
                //    while (cur)
                //    {
                //        newHT.Insert(cur->_kv);
                //        cur = cur->_next;
                //    }
                //}
                //table.swap(newHT.table);
                //新思路
                vector<Node*> newTable(table.size() * 2);
                for (size_t i = 0; i < table.size(); i++)
                {
                    Node* cur = table[i];
                    //重新映射挂到新表上
                    while (cur)
                    {
                        Node* next = cur->_next;
                        //映射到新表
                        size_t hashi = cur->_kv.first % newTable.size();
                        cur->_next = newTable[hashi];
                        newTable[hashi] = cur;
                        cur = next;
                    }
                    //释放旧表
                    table[i] = nullptr;

                }
                table.swap(newTable);
            }
            
            Node* newnode = new Node(kv);
            newnode->_next = table[hashi];
            table[hashi] = newnode;
            size++;
            return true;
        }
        Node* Find(const K& key)
        {
            Hash  hs;
            size_t hashi = key % table.size();
            Node* cur = table[hashi];
            while (cur)
            {
                if (cur->_kv.first == key) return cur;
                cur = cur->_next;
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            Hash  hs;
            size_t hashi = key % table.size();
            Node* prev = nullptr;
            Node* cur = table[hashi];
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    if (prev == nullptr)
                    {
                        table[hashi] = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --size;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }
    private:
        vector<Node*> table;
        size_t size;//实际储存数据的个数
    };
}

        

        本期内容到这里就结束了，喜欢请点个赞支持一下作者，谢谢。

        封面图自取：

# c++ # 学习 # 散列表 # 数据结构 # 哈希算法
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

WRB1205S-1WR2 与钡特电源 VB1-12S05S 参数规格解析｜ 1W 宽压输入隔离 DC-DC 工业电源模块性能拆解

avatar 亚马逊云科技技术品牌专区
cover

人工智能如何改变学习方式

avatar 亚马逊云科技技术品牌专区
cover

AI技术正在改变

avatar 亚马逊云科技技术品牌专区