首页 > 其他分享 >哈希表总结

哈希表总结

时间：2022-12-14 20:34:36浏览次数：33  
标签：总结 primeTable idx int primeIdx 哈希 table

哈希表

理论讲解

元素通过确定的映射关系找到其在表中的存储位置，这个映射关系叫做哈希函数(散列函数)，==这张表就叫做哈希表(散列表)

优势：适用于快速的查找，时间复杂度为O(1)

缺点：占用内存空间比较大，哈希表的空间效率还是不够高。链式哈希表，每个桶上存一个链表，而链表的每一个节点除了数据域外，还有地址域，1个地址要占4字节（8字节），如果数据规模很大的话，那么内存的占用量就会非常大，甚至无法进行完全存储。

无序关联容器unordered_set、unordered_map的底层实现就是哈希表

哈希函数

设计特点：

  • 计算简单（太复杂会降低查询时间）
  • 散列地址分布均匀（减少哈希冲突发生概率）

哈希函数：

  • 除留余数法
  • 数字分析法
  • 平方取中法
  • md5,sha加密hash算法等

哈希冲突(哈希碰撞)

元素通过哈希函数映射到同一个地址，就表示发生了哈希冲突

发生哈希冲突时的解决方法：

  • 线性探测法 （开放定址法）
    • 当前地址发生冲突了，就往后继续找空闲的位置
    • 缺陷：当表中的元素越来越多时，线性探测法为了找到空闲位置需要遍历的长度就会越来越长，性能由O(1)逐渐达到O(n)
  • 二次探测法：是对线性探测法的改进
  • 链地址法

尽可能减少发生哈希冲突的概率：

  • 哈希函数是除留余数法时，将哈希表的长度设为素数，确保计算后的哈希地址能够尽可能离散
  • 哈希表的装载因子 loadfactor
    • 已占用的桶的个数 / 桶的总个数 > loadfactor 时，哈希表就要进行扩容了,扩容时原来哈希表中的元素需要重新进行哈希，代价是比较大的， 时间复杂度达到O(n)

线性探测哈希表实现

分析

  1. 每个位置的状态：

    • 正在使用

    • 从未使用

    • 当前位置的元素被删除

  2. 添加元素

    扩容操作：如果 （已占用的桶的个数 / 桶的总个数 > loadfactor）则需要先进行扩容！！

    通过哈希函数计算数据存放的位置（哈希地址）

    • 如果该地址是空闲的，直接存储元素，完成

    • 如果该位置被占用(发生冲突了)，那么采用线程探测法继续往后找空闲的位置来存放元素

  3. 查询操作

    通过哈希函数计算数据存放的位置，从该位置取值（需要判断该位置的状态是否为正在使用中）

    • 如果取出的值 == 要查询的元素值，查询成功

    • 如果取出的值 != 要查询的元素值（之前往这个位置放元素时，发生了哈希冲突），继续往后遍历查找该元素

  4. 删除操作

    过哈希函数计算数据存放的位置，从该位置取值，判断状态是否为正在使用中

    • 如果取出的值 == 要删除的值，直接修改当前位置的状态即可（置为已删除状态）

    • 如果取出的值 != 要删除的值，继续往后遍历查找该元素，如果遇到某个位置为从未使用的状态，那么就说明哈希表中没有该元素

  5. 关于素数表

    我们的哈希函数采用除留余数法，为了让地址更离散，表的长度设置为素数，我们能够通过程序得到固定范围内的所有素数（只能被1和本身整除），但是并不是每次扩容都是紧挨着进行扩容的，因为扩容的开销比较大，所以每次扩容的时候都扩大一点，素数的选择最好比较离散些。

    可以参考该素数表：[3, 7, 23, 47, 97, 251, 443, 911, 1471, 42773]

实现

#include <iostream>
using namespace std;

// 桶状态
enum State
{
	STATE_USEING,
	STATE_UNUSED,//从未被用过
	STATE_DEL,//用过但是已经删除
};

//桶结构
struct Bucket 
{
	Bucket(int key=0, State state = STATE_UNUSED)
		:key_(key)
		,state_(state)
	{}
	int key_;//桶存放的数据
	State state_;//桶的状态信息

};

// 定义哈希表
class HashTable 
{
public:
	HashTable(int size=primeTable_[0], double loadfactor=0.75) 
		:tableSize_(size)
		,useBucketNum_(0)
		,loadfactor_(loadfactor)
		,primeIdx_(0)
	{
		//我们要保证保证表长是素数(从线性表里取)，所以需要对传入的size进行调整
		int i = 0;
		for (; i < PRIME_SIZE; i++) 
		{
			if (primeTable_[i] >= size) 
			{
				tableSize_ = primeTable_[i];
				primeIdx_ = i;
				break;
			}
		}
		//传入的值过大，可以调整到最后一个素数
		if (i == PRIME_SIZE)
		{
			primeIdx_--;
		}
		pBucket_ = new Bucket[tableSize_];
	}

	~HashTable() 
	{
		delete[]pBucket_;
		pBucket_ = nullptr;
	}
	
	// 增加元素操作
	bool insert(int val) 
	{
		//判断是否是要扩容
		double factor = useBucketNum_ * 1.0 / tableSize_;
		cout << "factor:" << factor << endl;
		if (factor >= loadfactor_) 
		{
			expand();//按照素数表进行扩容
		}

		// 采用除留余数法找到元素在哈希表中对应的位置
		int idx = val % tableSize_;
		int k = idx;
		do 
		{
			if (pBucket_[k].state_ != STATE_USEING) 
			{
				pBucket_[k].state_ = STATE_USEING;
				pBucket_[k].key_ = val;
				useBucketNum_++;
				return true;
			}
			k = (k + 1) % tableSize_;
		} while (k != idx);//k遍历了一边后(实际上由于设置了装载因子并不会出现遍历一边的情况)还无法找到插入位置，则插入失败
		return false;
	}

	// 查询操作
	bool find(int val) 
	{
		int idx = val % tableSize_;
		int k = idx;
		do 
		{
			if (pBucket_[k].state_ == STATE_USEING && pBucket_[k].key_ == val) 
			{
				return true;
			}
			k = (k + 1) % tableSize_;
		} while (pBucket_[k].state_==STATE_UNUSED && k != idx);
		return false;
	}

	// 删除操作
	bool erase(int val) 
	{
		if (useBucketNum_ == 0)
			throw "哈希表为空，没有可删除元素!";
		int idx = val % tableSize_;
		int k = idx;
		do 
		{
			if (pBucket_[k].state_ == STATE_USEING && pBucket_[k].key_ == val) 
			{
				pBucket_[k].state_ = STATE_DEL;
				useBucketNum_--;
			}
			k = (k + 1) % tableSize_;
		} while (pBucket_[k].state_ == STATE_UNUSED && k != idx);
		return true;
	}

private:
	void expand() 
	{
		//按照素数表进行扩容
		if (primeIdx_+1 == PRIME_SIZE)
			throw "the HashTable is too large,expand false!";
		primeIdx_++;
		Bucket* p = new Bucket[primeTable_[primeIdx_]];
		// 遍历原哈希表中的元素，并对它们进行重新哈希
		for (int i = 0; i < tableSize_; i++) 
		{
			if (pBucket_[i].state_ == STATE_USEING) 
			{
				// 用新表长哈希
				int idx = pBucket_[i].key_% primeTable_[primeIdx_];
				int k = idx;
				do 
				{
					if (p[k].state_ != STATE_USEING) 
					{// 不要再useBucketNum_++,因为已用桶的数量没有变
						p[k].state_ = STATE_USEING;// 注意修改状态
						p[k].key_ = pBucket_[i].key_;
						break;
					}
					//线性探测用的也是新表长
					k = (k + 1) % primeTable_[primeIdx_];
				} while (k != idx);

			}
		}
		tableSize_ = primeTable_[primeIdx_];
		delete[]pBucket_;
		pBucket_ = p;

	}
	Bucket* pBucket_;
	int tableSize_;//哈希表长度
	int useBucketNum_;//已用桶的数目
	double loadfactor_;//装载因子，用于扩容
	
	//素数表用于扩容
	//所有哈希表对象都使用同一个素数表
	//c++11中对静态整形常量可以在类内部初始化
	static const int PRIME_SIZE = 10;//素数表大小
	static int primeTable_[PRIME_SIZE];
	int primeIdx_;//素数表索引，不同对象的索引值可能不同

};

int HashTable::primeTable_[PRIME_SIZE] = { 3,7,23,47,97,251,443,911,1471,42773 };

测试代码

int main()
{
	HashTable htable;
	htable.insert(21);
	htable.insert(32);
	htable.insert(14);
	htable.insert(15);

	htable.insert(22);

	cout << htable.find(21) << endl;
	htable.erase(21);
	cout << htable.find(21) << endl;
}

链式哈希表实现

线性探测哈希表的缺陷：

  1. 发生哈希冲突时，采用线性探测法，时间复杂度会逐渐靠近O(n)
  2. 多线程环境中，线性探测所用到的基于数组实现的哈希表，只能给全局的表加互斥锁来保证对哈希表操作的原子性，保证线程安全！

分析

  • 链式哈希表中每个桶都放一个链表，把发生哈希冲突的元素都挂到对应的桶上
  • 哈希函数采用除留余数法，表长为素数
  • 优化策略：
    • 如果每个桶的链表比较长，那么链表搜索花费的时间就会比较长，时间复杂度会趋于O(1) ，这时可以考虑把链表转化成红黑树，红黑树的查找时间复杂度达到O(logn)
    • 在多线程环境下，可以为链式哈希表的每个桶创建自己的分段锁，不同桶中的链表操作是可以并发执行的!

实现

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

class HashTable 
{
public:
	HashTable(int size = primeTable_[0], double loadfactor = 0.75) 
		:useBucketNum_(0)
		,loadfactor_(loadfactor)
		,primeIdx_(0)
	{
		// 需要将哈希表的长度调整到素数长度
		for (; primeIdx_ < PRIME_SIZE; primeIdx_++) 
		{
			if (primeTable_[primeIdx_] >= size) 
			{
				table_.resize(primeTable_[primeIdx_]);
				break;
			}
		}
		if (primeIdx_ == PRIME_SIZE) 
		{
			table_.resize(primeTable_[--primeIdx_]);
		}
	}

	// 不需要再自定义析构函数了，vector成员变量会调用它的析构函数来释放占用的外部内存

	void insert(int val) 
	{
		// 1.插入前先判断需不需要扩容
		// 先查看当前的装载程度
		double factor = (useBucketNum_ * 1.0) / primeTable_[primeIdx_];
		cout << "(当前装载程度)factor:" << factor << endl;
		if (factor >= loadfactor_) 
		{
			expand();
		}
		
		// 利用除留余数法(哈希函数)找到桶索引
		int idx = val % primeTable_[primeIdx_];
		if (table_[idx].empty()) 
		{
			// 仅当桶中的链表容器为空，要插入第一个元素时useBucketNum_++
			useBucketNum_++;
			// 头插法插入第一个元素
			table_[idx].emplace_front(val);
		}
		else 
		{
			// 去重操作-->或者说如果元素已经存在就不再进行插入操作
			// 使用C++算法库提供的泛形函数
			auto it = ::find(table_[idx].begin(), table_[idx].end(), val);
			if (it == table_[idx].end()) // 
			{
				// 要插入的是新元素
				table_[idx].emplace_front(val);
			}
		}
	}

	bool erase(int val) 
	{
		int idx = val % primeTable_[primeIdx_];
		auto it = ::find(table_[idx].begin(), table_[idx].end(), val);
		if (it != table_[idx].end()) 
		{
			table_[idx].erase(it);
			// 删除后需要判断当前桶是否为空，空的话需要useBucketNum_--
			if (table_[idx].empty()) 
			{
				useBucketNum_--;
			}
			return true;
		}
		return false;
	}

	bool find(int val) 
	{
		int idx = val % primeTable_[primeIdx_];
		auto it = ::find(table_[idx].begin(), table_[idx].end(), val);
		if (it != table_[idx].end())
		{	 
			return true;	
		}
		return false;
	}

private:
	void expand() 
	{
		// 先判断是否允许再扩容
		if (primeIdx_ + 1 == PRIME_SIZE)
			throw "the HashTable is too large!";
		
		primeIdx_++;
		// 千万注意，由于扩容后需要重新哈希，所以链表的分布极有可能发生变化,所以要将useBucketNum_=0,重新记录!!!
		useBucketNum_ = 0;
		
		vector<list<int>> oldTable;
		// 发生交换后,table_就是一张空表了
		table_.swap(oldTable);
		table_.resize(primeTable_[primeIdx_]);

		// 把原来表中的每个元素重新哈希到扩容后的表中
		for (auto list : oldTable) 
		{
			for (auto key : list) 
			{
				int idx = key % primeTable_[primeIdx_];
				if (table_[idx].empty()) 
				{
					useBucketNum_++;
				}
				table_[idx].emplace_front(key);
			}
		}


	}

	vector<list<int>> table_;	// 哈希表
	int useBucketNum_;			// 已用桶的数目
	double loadfactor_;			// 装载因子

	static const int PRIME_SIZE = 10;
	static int primeTable_[PRIME_SIZE];
	int primeIdx_;
};

int HashTable::primeTable_[PRIME_SIZE] = { 3,7,23,47,97,251,443,911,1471,42773 };

测试代码

int main() 
{
	HashTable htable;
	htable.insert(21);
	htable.insert(32);
	htable.insert(14);
	htable.insert(15);

	htable.insert(22);
	htable.insert(23);

	cout << htable.find(21) << endl;
	htable.erase(21);
	cout << htable.find(21) << endl;
	return 0;
}

关于代码中的table_.swap()操作，这个操作的效率会不会比较低？

  • 实际上，这里两个容器只是把成员变量做了一个交换，也就是底层指针的指向做了交换，并没有涉及内存的构造，拷贝，所以效率是很高的

  • **注意： **

    • 如果两个容器使用的空间配置器allocator是一样的，即拥有相同的内存管理方式，那么可以使用swap操作，成员变量直接交换，效率高！
    • 如果两个容器使用的空间配置器allocator是不一样的，即拥有不同的内存管理方式，那么就需要采用效率低的整个数据的交换

总结

标签：总结,primeTable,idx,int,primeIdx,哈希,table
From： https://www.cnblogs.com/ChenFei-Blogs/p/16983429.html

相关文章

  • 算子研发总结
     1统计DDR读写性能Taskddr读写工具，->DDR-gsram->代码memcp_->reportDMAcycle/DMAreadbyte/fps/totaltime ->REPORTaipucycle=DMA+SPU......
  • 12.14学习总结
    缓存更新策略缓存更新是redis为了节约内存而设计出来的一个东西，主要是因为内存数据宝贵，当我们向redis插入太多数据，此时就可能会导致缓存中的数据过多，所以redis会对部分数......
  • 基本排序算法总结（转）
    基本排序算法总结原文：https://blog.csdn.net/qq_21187515/article/details/127212565一直想总结一下最常用的排序算法，自己写一下代码并运行一下记忆更深刻1、插入排序......
  • 12月14日内容总结——
    一、模板层之标签分支结构if{%if条件1(可以自己写也可以用传递过来的数据)%}<p>今天又是周三了</p>{%elif条件2(可以自己写也可以用传递过来的数据)%}......
  • javaweb之文件上传总结
    一。文件上传：是指允许客户将本地文件，上传到服务器端 常见的应用：上传照片、上传新闻图片、上传附件 文件上传编程基本步骤： 1、在用户页面中添加上传输入项（客户端页......
  • IPv6改造为什么这么难？IPv6改造方案难点总结-中科三方
      据统计，截至2019年6月，我国IPv6活跃用户数仅为1.3亿，而到2020年底，这个数字需超过5亿。目前网上最早关于IPv4地址枯竭的新闻可追溯到2004年，来源京华时报。     ......
  • 个人学期期末总结和对王建民老师的评价
    JavaWeb学习期末总结：这个学期是来到学校本部的第一个学期，也是专业分流后来到软件工程专业继续学习的第一个学期。这是一个全新的学期，什么都是新的，我满怀期待，满怀热情地加入......
  • 现代软件工程个人总结
    软件工程课程总结这个学期主要学习的内容是Android、Python爬虫、Python flask框架，完成了一个简单的家庭记账本app，完成了一个简单的体温登记app，完成结对作业（中国疫情数......
  • MySQL 面试题总结
    MySQL的面试知识点总结Q1：MySQL的逻辑架构了解吗？第一层是服务器层，主要提供连接处理、授权认证、安全等功能。第二层实现了MySQL核心服务功能，包括查询解析、分析、优......
  • 画流程图总结
    画流程图是程序员必备的专业技能，下面是我总结的平时画流程图的一些心得体会，有不足和不标准不妥的地方请指正！首先先认识流程图有哪些常用的框框：注意：1标准的开始必须用：而不是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99