【C++进阶】哈希表（哈希函数、哈希冲突、开散列、闭散列）

分类:热门推荐日期:2024-04-17浏览:1评论:0

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

          主厨：邪王真眼

主厨的主页：Chef‘s blog  

所属专栏：c++大冒险

 

 总有光环在陨落，总有新星在闪烁

引言：

             我们之前学习了红黑树及其应用，它增删查改的时间复杂度仅仅只有log N，然而，今天我们会学习的哈希直接把增删查改的时间复杂度降低到了O（1）！心动了对吧？那就快来学习吧。

一、哈希概念

       顺序结构以及平衡树中，元素关键码（Key）与其存储位置之间 没有对应的关系 ，因此在查找一个元素时， 必须要经过关键码的多次比较。 顺序查找时间复杂度为O(N)，平衡树中为O(log N)。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

        构造一种存储结构，通 过某种函数使元素的存储位置与它的关键码能够建立一一映射的关系 ，那么在查找时通过该函数可以很快找到该元素。该方式即为 哈希(散列)方法， 构造出来的结构称 为 哈希表（Hash Table ），或称散列表。 例如：        对于数据集合{1，7，6，4，5，9}； 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

二、 哈希函数

哈希方法中使用的转换函数称为哈希(散列)函数

哈希函数设计原则：
  1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
  2. 哈希函数计算出来的地址能均匀分布在整个空间中
  3. 哈希函数应该比较简单

常见哈希函数

2.1 直接定址法--(常用)

Hash（Key）= A*Key + B
  1. 优点：简单、均匀
  2. 缺点：需要事先知道关键字的分布情况
  3. 使用场景：适合查找比较小且连续的情况

2.2. 除留余数法--(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，
Hash(key) = key% p(p<=p<=m)

  1. 优点：不需要事先知道key的分布情况

  2. 缺点：会产生哈希冲突

  3. 选质数作为除数可以减少哈希冲突，原因：这是因为素数具有较好的分布性质，能够更均匀地将输入数据映射到不同的哈希值上。相比于选择非素数的除数，选择素数可以降低哈希地址集中在某些特定值上的可能性，从而减少冲突的发生。

    以下方法不常用，感兴趣的朋友可以了解一下

2.3. 平方取中法--(了解)

      假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址平方取中法比较适合不知道关键字的分布，而位数又不是很大的情况

2.4. 折叠法--(了解)

        折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

2.5. 随机数法--(了解)

        选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中 random为随机数函数。 通常应用于关键字长度不等时采用此法 注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

三、哈希冲突

哈希冲突是指在哈希表中，不同的键值经过哈希函数计算后得到相同的哈希值，导致它们被映射到同一个槽位或桶中。这种情况下，就会发生冲突。

哈希冲突可能会导致以下问题：

  1. 数据丢失：当两个不同的键值被映射到同一个槽位时，其中一个键值的数据可能会被覆盖。
  2. 查找效率下降：在发生冲突的槽位中，需要通过额外的操作来查找目标键值，这会增加查找的时间复杂度。
  3. 哈希表性能下降：频繁的哈希冲突会导致哈希表的装载因子增加，使得哈希表的性能下降。

四、哈希冲突解决

解决哈希冲突两种常见的方法是： 闭散列和开散列

4.1 闭散列——开放地址法

       当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

4.1.1. 线性探测

      比如中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

 

4.1.2存储数据类型：

enum State
{
	EMPTY,//该位置为空
	EXIST,//该位置已经有元素
	DLETE//该位置元素已被删除
};
templatestruct HashData
{
	State _state = EMPTY;//标记当前位置的状态
	pair < K, V> _kv;
};

注意事项：

        可能有朋友疑问问什么有三个状态，而不是直接存在和不存在两种，这点在后面查找中你就明白了

4.1.3哈希表成员变量

templateclass HashTable
{
protected:
	vector _tables;
	size_t size = 0;//存储数据个数
};

注意事项：

  1. 哈希表底层一般使用数组（vector）
  2. 哈希表的有效数据个数_n与vector的size不同

4.1.4构造函数：

HashTable(size_t size=10)
{
	_tables.resize(size);
}

注意事项：

             不要把缺省值给个0，不然后面还要对0的情况进行讨论，不如直接开10个空间

4.1.5查找：

HashData* Find(const K&key)
{
	size_t hash = key % _tables.size();
	size_t pos = hash;
	size_t i = 1;
	while (_tables[pos]._state != EMPTY)
	{
		if (_tables[pos].state == EXIST && _tables[pos]._kv.first == key)
			return &_tables[pos];
		pos += i;
		if (pos >= _tables.size())
			return nullptr;
	}
	return nullptr;
}

流程：

  1. key取模vector的size（不是capacity！！不然可能越界访问），得到哈希地址hashi
  2. 沿当前位置向后找，直到该位置状态为空或超出数组边界，则返回空指针，表示没有该数据
  3. 如果该位置状态为存在且key相等，则找到了并返回对应数据指针

4.1.6插入 

bool Insert(pair& kv)
{
	
	if (Find(kv.first))
		return false;
	size_t hash = key % _tables.size();
	size_t pos = hash;
	size_t i = 1;
	while (_tables[pos]._state == EXIST)
	{
		pos += i;
		if (pos >= _tables.size())
			return false;
	}
	_tables[pos]._kv = kv;
	_tables[pos]._states = EXIST;
	return true;
	_size++;
}
流程：
  1. 查找当前是否存在该值，如果存在，则不插入（哈希表不存同样的数据）
  2. 通过哈希函数获取待插入元素在哈希表中的位置，得到哈希地址hashi
  3. 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突， 使用线性探测沿当前位置向后找，直到状态为空或删除，才插入

    但是，上述情况是哈希表未满时，如果满了如何扩容？还有，一定要满了才扩容吗？

我们引入负载因子的概念：α = 有效数据个数 / 哈希表长度

            当负载因子越大，哈希冲突的概率就越大，同时发生哈希踩踏的概率也越大，对于开放定址法，应该控制负载因子小于0.7，超过0.7则扩容。

if (_size * 10 / _tables.size() > 7)//扩容
	{
		vector newtables(_tables.size() * 2);
		for (auto hashdata : _tables)
		{
			pairkv = hashdata._kv.first;
			size_t hash = key % _tables.size();
			size_t pos = hash;
			size_t i = 1;
			while (newtables[pos]._state == EXIST)
			{
				pos += i;
			}
			_tables[pos]._kv = kv;
			_tables[pos]._states = EXIST;
		}
		_tables.swap(newtables);
	}

流程：

  1. 判断时左右同乘以10，避免比较浮点数而带来误差
  2. 扩容为原本的2倍（本来应该是接近2倍的素数，这里简单起见没实现）
  3. 将原哈希表中的元素一一映射到新表中
  4. 最后交换旧表和新表（类似于拷贝构造的现代写法）

4.1.7删除 

bool Erase(const K& key)
	{
		HashData* ptr = Find(key);
		if (ptr)
		{
			(*ptr)._state = DELETE;
			--_size;
			return true;
		}
		return false;
	}

注意事项：

  1. 先查找当前是否存在该值，如果存在，则删除
  2. 这里的删除，只用将状态变量改为删除即可，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。因此线性探测采用标记的伪删除法来删除一个元素。
  1. 线性探测优点：实现非常简单，
  2. 线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同 关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降 低。如何缓解呢？

4.1.8. 二次探测

线性探测（一个一个往后找），这种探测方法可能会造成大量的哈希冲突。

那么，有没有什么探测方法能缓解哈希冲突呢？有，那就是二次探测！，因此二次探测为了避免该问题，找下一个空位置的方法为：

while (newtables[pos]._state == EXIST)
{
	pos = hashi + i*i;//二次探测
	++i;
}
插入44使用二次探测解决后的情况为： 研究表明：              当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。 因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷 。

4.2 开散列——链地址法（拉链法）

4.2.1. 开散列概念

       首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表（又称哈希桶）中。 从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

4.2.2节点：

templatestruct HashNode
{
	HashNode _next;
	pair _kv;
	HashNode(pair kv=pair())
		:_next(nullptr)
		,_kv(kv)
	{}
};

4.2.3成员变量：

templateclass HashTable
{
	typedef HashNode Node;
protected:
	vector _tables;
	size_t _size = 0;
};
          这乍一看好像没什么问题，但其实细心地朋友可能在我们写闭散列时就想到了，万一K不能直接取模呢？比如string类，于是乎我们还要加一个函数来支持key取模 
template>class HashTable
{
	typedef HashNode Node;
protected:
	vector _tables;
	size_t _size = 0;
};

4.2.4构造函数

HashTable(size_t size=10)
{
	_tables.resize(size);
}

4.2.5析构函数

~HashTable()
{
	for (auto hash_node : tables)
	{
		while (hash_node)
		{
			Node* new_node = hash_node->_next;
			delete hash_node;
			hash_node = new_node;
		}
	}
}

注意事项：

              每条链表都要手动释放

 4.2.6查找：

Node* Find(const K&key)
{
	size_t hash = Hash(key)%_tables.size();
	Node* cur = _tables[hash];
	while (cur)
	{
		if (cur->_kv.first == key)
			return cur;
		cur = cur->_next;
	}
	return nullptr;
}

细流程：

  1. 先取模计算出哈希地址
  2. 再沿当前单链表向下查找
  3. 进行头插

4.2.7插入

bool Insert(pair& kv)
	{
		if (Find(kv.first))
			return false;
		size_t hash = Hash(key) % _tables.size();
		Node*cur = _tables[hash];
				Node* p(kv);
				p->_next=cur;
				_tables[hash] = p;
				_size++;
				return true;
				
	}

          运用开链法后，虽然没有哈希冲突了，但是链表长度过长也会影响效率。所以，哈希表也需要通过扩容来使链表长度变短，理想的状态是负载因子为1时扩容。

if (_size == _tables.size())
{
	vector new_tables(_size*2);
	for (auto node : _tables)
	{
		while (node)
		{
			Node* next = node->_next;
			size_t hash = Hash(node->_kv.firsh) % new_tables.size();
			node->_next=new_tables[hash];
			new_tables[hash] = node;
			node = next;
		}
	}
	_tables.swap(new_tables);
}

流程：

  1. 二倍扩容（本来应该是接近2倍的素数，这里简单起见没实现）
  2. 遍历旧表，将旧表结点重新映射到新表上
  3. 最后交换旧表和新表

4.2.8 删除

bool Erase(const K& key)
{
	size_t hash = Hash(key) % _tables.size();
	Node* cur = _tables[hash];
	Node* pre = nullptr;
	while (cur)
	{
		if (cur->_kv.first == key)
			break;
		pre = cur;
		cur = cur->_next;
	}
	if (cur == nullptr)
		return false;
	if (pre == nullptr)
		_tables[hash] = cur->_next;
	else
		pre->_next = cur->_next;
	delete cur;
	return true;
}

注意事项：

  1. 要设置前驱指针pre
  2. 根据pre是否为空，分类处理

4.2.9 哈希化

       由于除留余数法涉及到取模运算，而只有整型才能取模。所以针对非整型的数据，需要将其转化为整型，这一过程称为哈希化。

templatestruct HashFunck
{
	size_t operator()(K s)
	{
		return s;
	}
};
template<>struct HashFunck{
	size_t operator()(const string& s)
	{
		size_t number=0;
int multiply=31;
		for (auto ch : s)
			number = number * multiply + ch;//multiply可以取这些值131, 31 131 1313 13131 131313
			return number;
	}
};
 

4.3. 开散列与闭散列比较

       应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

五、哈希表和红黑树的优劣

5.1哈希表优劣

哈希表是一种基于哈希函数的数据结构，它将键映射到存储位置，以实现快速的查找和插入操作。哈希表的优点：

  1. 高效的查找和插入操作：通过哈希函数计算键的存储位置，可以在平均情况下以常数时间复杂度进行查找和插入。
  2. 空间利用率高：哈希表可以根据实际需求动态调整存储空间，避免了不必要的内存浪费。

哈希表的缺点：

  1. 哈希冲突：不同的键可能映射到相同的存储位置，导致冲突。解决冲突的方法包括链地址法和开放地址法，但这些方法可能会增加查找的时间复杂度。
  2. 不支持有序性操作：哈希表中的键是无序的，如果需要按照键的顺序进行操作，就需要额外的处理。

5.2红黑树优劣

红黑树是一种自平衡的二叉搜索树，它具有以下特点：

  1. 平衡性：红黑树通过保持特定的性质，使得树的高度保持在一个较小的范围内，从而保证了查找、插入和删除操作的时间复杂度都是对数级别的。
  2. 有序性：红黑树中的节点按照键的大小有序排列，支持按序遍历和范围查询等操作。

红黑树的优点：

  1. 支持有序性操作：红黑树中的节点按照键的大小有序排列，可以方便地进行按序遍历、范围查询等操作。
  2. 自平衡性：红黑树通过自动调整节点的颜色和旋转操作，保持树的平衡，避免了极端情况下的性能退化。

红黑树的缺点：

  1. 相对于哈希表，红黑树的查找和插入操作的平均时间复杂度较高，尤其是在数据量较大时。
  2. 红黑树需要额外的存储空间来存储节点的颜色信息，相比于哈希表可能会占用更多的内存。

 综上所述，

哈希表适用于需要快速查找和插入操作，并且不要求有序性的场景；而红黑树适用于需要有序性操作，并且对平衡性有要求的场景。具体选择哪种数据结构，需要根据实际需求和场景来进行权衡和选择。

创作不易，点赞关注支持一下吧

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号