哈希表 -- 哈希表的概念, 哈希表的实现 (闭散列, 开散列) 详细解析

作者: 努力学习的少年

个人简介: 双非大二, 一个正在自学 c++ 和 Linux 操作系统, 写博客是总结知识, 方便复习.

目标: 进大厂

如果你觉得文章可以的话, 麻烦你给我点个赞和关注, 感谢你的关注!

种一颗树最好是 10 年前, 其次是现在.

目录

哈希概念

哈希函数

直接定址法

除留余数法

哈希冲突

闭散列 ---------- 开发定址法

闭散列的实现

开散列 -------- 哈希桶

开散列的增容

开散列的实现

哈希概念

用某个函数直接将元素映射到一个顺序结构中, 查找的时候通过映射关系直接找到该值. 这个映射函数叫做哈希函数.

哈希函数

设计哈希函数常用有两种方法: 直接定址法和除留余数法

直接定址法

取关键字的某个线性函数为散列地址: Hash(Key)= A*Key + B

优点: 简单, 均匀

缺点: 需要事先知道关键字的分布情况 使用场景: 适合查找范围集中且已知范围

如下这题就直接使用直接定址法:

该题直接采用直接定址法, 已知该题只包含小写字母, 所以直接创建一个大小为 26 的数组直接映射小写字母即可, 然后遍历字符串, 统计字符串中的小写字母出现的次数, 然后再遍历一遍字符串, 通过字符哈希映射关系, 直接找到第一个只出现一次的字符.

class Solution {
public:
    char firstUniqChar(string s) {
        int arr[26]={0};
        for(auto c:s)// 遍历一遍字符串, 统计 s 中字符的个数
        {
            arr[c-'a']++;
        }
        for(auto c:s)// 再遍历一遍字符串, 找出第一个只出现一次的字符
        {
            if(arr[c-'a']==1)
            return c;
        }
        return ' ';
    }
};

时间复杂度: O(N)

空间复杂度: 因为我们只定义出一个 arr[26] 的数组, 所以空间复杂度为 O(1),

该题是直接将 0~25 映射出 a~z 这 26 个字母, 这种方式叫做直接定址法.

该方式的优点是: 效率高, 通过某个数字直接映射出某个字符.

缺点: 只适用于整数, 字符且范围较小的映射, 浮点数或者范围很广的映射不适用.

除留余数法

假设需要映射一些范围很广的元素, 可以将这个范围很广的数组缩小到一个哈希数组里进行映射, 也就是说映射该数的位置 = 该数 % 哈希表数组的大小, 这就是除留余数法.

例如我们的哈希数组的大小是 10, 所以我们可以将映射的每个元素进行 %10, 那么哈希数组中的范围映射位置是 0~9, 如下, 将下列的数组映射到哈希表中.

哈希冲突

简单来说, 哈希冲突就是不同的值映射到相同的位置

上面的除留余数法就会发生哈希冲突, 例如:

100 和 10 放在大小为 10 的哈希数组中, 那么它们都 %10 之后都是 0, 这就是哈希冲突.

解决哈希冲突常用有两种方法, 闭散列和开散列.

闭散列 ---------- 开发定址法

如果哈希表未满, 然后未被装满, 说明哈希表必然存在空位置, 那么可以把 key 值放在冲突的下一个空位置. 例如:

查找空位置的方式有线性探测和二次探测:

线性探测: 从冲突位置上往后一个一个查找空位置

例如: 上面的 10 映射到哈希表中, 它经过 1,12,3 最终在 4 的位置找到空位置, 往后一个一个查找就是线性探测, 线性探测一旦发生哈希冲突, 所有的冲突连在一起, 容易产生数据 "堆积", 即: 不同关键码占据了可利用的空位置, 使得寻找某关键码的位置需要许多次比较, 导致搜索效率降低., 例如: 当我们要查找 10 这个数据的时候, 我们需要踏过 1,12,3 这三个数据, 查找效率较低.

二次探测: 从冲突位置上往后以 n^2 进行查找空位置. n={1,2,3,4...}

查找值的时候, 也是按二次探测开始查找, 走到空时, 说明查找不到.

如下:

二次探测相对分散一些, 不容易发生踩踏事件.

思考:

哈希什么时候下进行增容? 如何增容?

散列表中载荷因子的定义: a = 哈希表填入的元素个数 / 哈希表的容量

a 越大, 填入表中的元素个数越多, 冲突可能性越大, 查找效率较低, 反之, a 越小, 冲突的可能性越小, 查找效率较高, 为了保证查找效率, 载荷因子到一定的数之后, 哈希表就要增容, 正常情况下, 载荷因子控制在 0~0.8, 超过 0.8, 则查找效率会很低.

闭散列的实现

1. 闭散列需要定义定义一个枚举数组来判断哈希表上位置的状态.

enum State// 标识哈希表中位置的状态
    {
        EMPTY,// 空
        EXITS,// 存在
        DLETE// 删除
    };

2. 定义一个哈希表存储的数据结构体, 一个是存储的数据, 一个是存储的状态, 状态默认为空.

template<class K,class V>
	class HashData// 哈希位置的数据
	{
	public:
		pair<K, V> _kv;// 哈希表上映射的数据
		State _state = EMPTY;// 位置上的状态
	};

3. 哈希表的定义

namespace sjp
{
	enum State// 标识哈希表中位置的状态
	{
		EMPTY,// 空
		EXITS,// 存在
		DLETE// 删除
	};
	template<class T>
	struct HashFunc// 哈希仿函数, 用来转化为整数, 才能进行除留余数
	{
		size_t operator()(const T& k)
		{
			return k;
		}
	};
	template<>//string 仿函数的模板特化
	struct HashFunc<string>
	{
		// 将字符变成对应的整形值
		//BKDRHAXI 每次加上一个数, 在乘上 131
		// 近似唯一
		size_t  operator()(const string& st)
		{
			size_t ret = 0;
			for (auto e : st)
			{
				ret += e;
				ret *= 131;
			}
			return ret;
		}
	};
	template<class K,class V>
	class HashData// 哈希位置的数据
	{
	public:
		pair<K, V> _kv;// 哈希表上映射的数据
		State _state = EMPTY;// 位置上的状态
	};
	template<class K, class V, class HashFunc= HashFunc<K>>// 仿函数
	class HashTable
	{
	public:
		bool Insert(const pair<K, V>& kv)
		{
			if (find(kv.first) != NULL)// 如果 kv 值在_table, 则插入失败
				return false;
			if (_table.capacity() == 0)
			{
				_table.resize(10);
			}
			else if ((double)_n /(double) _table.size()>=0.7)// 计算负载因子
			{
				// 大于负载因子, 哈希表进行增容
				HashTable<K, V, HashFunc> newHT;// 创建新的哈希表并未原来的两倍
				newHT._table.resize(_table.size() * 2);
				for (auto& e : _table)// 将旧表中数据一个一个的映射到新表中
				{
					if (e._state == EXITS)
					{
						newHT.Insert(e._kv);// 在运行 insert, 相当于复用了 insert
					}
				}
				_table.swap(newHT._table);// 最后将 newHT.table 和本身的 table 交换即可
			}
			// 位置得模上 size()
			HashFunc hf;
			size_t index = hf(kv.first)%_table.size();
			size_t i = 1;
			int start = index;
			// 探测后面的位置 -- 线性探测 or 二次探测
			while (_table[index]._state == EXITS)// 发生冲突, 探测下一个位置
			{
				i += 1;
				index =start+i*1;// 进行二次探测
				index %= _table.size();
			}
			_table[index]._kv = kv;
			_table[index]._state = EXITS;
			++_n;
			return true;
		}
		HashData<K, V>* find(const K& k)// 查找函数
		{
			HashFunc fc;// 仿函数
			if (_table.size()== 0)// 防止除 0
				return nullptr;
			int index = fc(k) % _table.size();
			int i = 1;
			while (_table[index]._state !=EMPTY )// 如果找到的位置不为空, 则继续往下找
			{
				// 找到了需要判断该值是否存在, 有可能被删除掉
				if (_table[index]._state == EXITS&&_table[index]._kv.first == k)
				{
					return &_table[index];
				}
				else
				{
					index += i;
					index %= _table.size();
				}
			}
			return NULL;
		}
		bool erase(const K& k)// 删除数据
		{
			HashData<K, V>* kv = find(k);// 查找 key 值
			if (kv == NULL)// 找不到, 则删除失败
			{
				return false;
			}
			else if (kv != NULL)// 找到了
			{
				kv->_state = DLETE; // 直接将该位置的状态设置为 DLETE, 假删除
				return true;
			}
		}
	private:
		vector<HashData<K,V>> _table;
		size_t _n=0;// 存储有效数据的个数
	};
}

为了让各个类型都能映射到哈希表中, 需要创建一个仿函数的类模板, 该仿函数可以将 char 和 int 等直接转换为整数.

template<class K>
	struct Hash// 将数据转换为整数的仿函数
	{
		size_t operator()(const K& k)
		{
			return k;
		}
	};

为了让 string 类型也能映射到哈希表里面, 所以我们需要将 string 转化为整数, 这样才能 % 某个数找到相应的位置, 所以我们需要对上面的仿函数进行模板的特化,. 如下:

template<>// 模板的特化, 将 string 的转换为整数
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			int ret = 0;
			for (auto c : s)
			{
				ret += c;
			}
			return ret;
		}
	};

当然, 这样将 string 中的字符相加起来后, 不同的 string 会发生冲突, 例如:

"abbc" 和 "acbb" 或者 "abcd" 和 "aadd" 它们的转化成整数是冲突的.

所以可以相加每个字符后 * 131, 这样使我们 string 转化成整数的冲突概率变得极低.

template<>// 模板的特化, 将 string 的转换为整数
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			int ret = 0;
			for (auto c : s)
			{
				ret += c;
				ret *= 131;
			}
			return ret;
		}
	};

然后将仿函数传入到模板列表中, 这样我们哈希表默认可以会对 string,char 等进行整形转化

template<class K, class V,class Hash=Hash<K>>

如果有其它类型需要转化成仿函数, 我们也可以自定义一个仿函数将它传进我们类模板中.

开散列 -------- 哈希桶

概念:

开散列概念开散列法又叫链地址法 (开链法), 首先对关键码集合用散列函数计算散列地址, 具有相同地址的关键码归于同一子集合, 每一个子集合称为一个桶, 各个桶中的元素通过一个单链表链接起来, 各链表的头结点存储在哈希表中.

如下: 将下面的数组

我们将映射相同位置的值用一个单链表连接起来, 各链表的头节点存储在哈希表中, 将每条链表称为一个桶. 其中链表的插入删除是进行头插, 因为头插的效率是 O(1).

开散列的增容

桶的个数是一定的, 随着数据的不断的插入, 冲突的概率越来越高, 每个桶的元素不断增加, 那么映射效率越低, 当每个桶的元素是只有一个元素时, 映射效率时最高的, 当元素个数等于桶的个数时, 可以给哈希表继续增容.

开散列的实现

template<class K, class V,class Hash=Hash<K>>
	class HashTable
	{
		typedef HashData<K, V> node;
	public:
		bool insert(const pair<K, V>& kv)// 插入
		{
			if (find(kv.first) != nullptr)// 哈希表中的 k 值不允许重复
				return false;
			if (_table.capacity() == 0)// 如果容量为 0, 则哈希表初始化 10 个空间
			{
				_table.resize(10,0);
			}
			else if (_n / _table.size()>= 1)// 哈希表中的元素大于
			{
				HashTable<K,V> newtable;// 创建一个新的哈希表
				newtable._table.resize(_table.size() * 2);//newtable 的大小为_table 的两倍
				for (auto& c : _table)// 将_table 中的元素映射到 newtable 中
				{
					node* cur = c;//c 是每个链表的头节点
					while (cur)
					{
						newtable.insert(cur->_kv);
						cur=cur->_next;
					}
				}
				_table.swap(newtable._table);// 交换两个表格, 完成增容
			}
			node* newnode = new node(kv);// 创建新的节点
			Hash hs;
			int index = hs(kv.first) % _table.size();// 找到映射的位置
			node* cur = _table[index];// 新的节点进行头插
			newnode->_next = cur;
			_table[index] = newnode;
			_n++;// 有效数据加 1
			return true;
		}
		node* find(const K& k)// 查找
		{
			if (_table.size() == 0)// 如果哈希表的空间为 0, 则直接返回
				return nullptr;
			Hash hs;
			int index = hs(k) % _table.size();// 找到该值在哈希表对应的映射位置
			// 在该位置上的链表进行查找
			node* cur = _table[index];
			while (cur)
			{
				if (cur->_kv.first == k)// 找到了
					return cur;
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;// 找不到
		}
		bool erase(const K& k)// 删除
		{
			if (_table.size() == 0)
				return false;
			Hash hs;
			int index = hs(k) % _table.size();// 找到该值在哈希表对应的映射位置
			node* pre = nullptr;//cur 前面的一个节点
			node* cur = _table[index];
			while (cur)
			{
				if (cur->_kv.first == k)// 找到了
				{
					if (pre == nullptr)// 头节点删除
					{
						_table[index] = cur->_next;
					}
					else// 中间节点删除
					{
						pre->_next = cur->_next;
					}
					delete cur;
					cur = nullptr;
					_n--;
					return true;
				}
				else
				{
					pre = cur;
					cur = cur->_next;
				}
			}
			return false;// 找不到, 删除失败
		}
	private:
		vector<node*> _table;// 哈希表
		size_t _n;// 计算哈希表中有多少个有效元素
	};
}

思考: 在极端情况下, 如果所有的数都映射在一个桶, 且没有到达有效数据个数小于哈希表的大小, 此时的查找的效率是 O(N), 请问有什么解决方法可以提高查找效率.

由于哈希表中的有效元素未达到哈希表的容量, 所以就没办法增容, 为了防止链表的太长, 我们可以将限制链表的长度, 如果链表大于该长度, 我们把该链表转化为红黑树, 例如我们可以 设置链表的最大长度为 8, 如果大于该长度, 在将该链表转换为红黑树.

若文章出现错误, 随时欢迎你帮我指正, 若文章对你有所帮助, 麻烦你给我点个关注!!!

来源: https://blog.csdn.net/sjp11/article/details/122477041