精华内容
下载资源
问答
  • 哈希桶
    2022-07-07 11:20:19

    哈希概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中元素的比较次数。
    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。、
    向该结构当中:
    插入元素: 根据待插入元素的关键码,用此函数计算出该元素的存储位置,并将元素存放到此位置。
    搜索元素: 对元素的关键码进行同样的计算,把求得的函数值当作元素的存储位置,在结构中按此位置取元素进行比较,若关键码相等,则搜索成功。
    该方式即为哈希(散列)方法, 哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(散列表)。
    在这里插入图片描述
    用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快 问题:按照上述哈希方式,向集合中插入元素44,会出现什么问题?

    哈希冲突

    不同关键字通过相同哈希函数计算出相同的哈希地址,这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。

    哈希函数

    引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:
    1.哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值域必须在0到m-1之间
    2.哈希函数计算出来的地址能均匀分布在整个空间中,哈希函数应该比较简单

    常见哈希函数

    直接定址法
    取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况
    除留余数法
    设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
    平方取中法
    假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况**(了解即可)**
    折叠法
    折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
    折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况。(了解即可)
    随机数法
    选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。(了解即可)
    数字分析法
    设有n个d位数,每一位可能有r种不同的符号,这r中不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,而在某些位上分布不均匀,只有几种符号经常出现。此时,我们可根据哈希表的大小,选择其中各种符号分布均匀的若干位作为哈希地址。(了解即可)
    注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

    哈希冲突解决

    解决哈希冲突两种常见的方法是:闭散列和开散列
    一、线性探测
    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
    插入
    1.通过哈希函数获取待插入元素在哈希表中的位置
    2.如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探
    3.测找到下一个空位置,插入新元素
    在这里插入图片描述
    删除
    采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
    线性探测的优点:实现非常简单。
    线性探测的缺点:一旦发生冲突,所有的冲突连在一起,容易产生数据“堆积”,即不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要多次比较(踩踏效应),导致搜索效率降低。
    二、二次探测
    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为: = ( + )% m,或者: = ( - )% m。其中:i = 1,2,3…, 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。 对于2.1中如果要插入44,产生冲突,使用解决后的情况为:
    在这里插入图片描述
    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。
    因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。

    开散列 —— 链地址法(拉链法、哈希桶)

    开散列,又叫链地址法(拉链法),首先对关键码集合用哈希函数计算哈希地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    在实际中,开散列的哈希桶结构比闭散列更实用,主要原因有两点:
    1.哈希桶的负载因子可以更大,空间利用率高。
    2.哈希桶在极端情况下还有可用的解决方案。

    哈希表的闭散列实现

    在这里我们为了不影响删除导致的后果,我们使用仿删除的方法,标记法定义空来表示删除。
    EMPTY(无数据的空位置)。
    EXIST(已存储数据)。
    DELETE(原本有数据,但现在被删除了)。

    //枚举:标识每个位置的状态
    enum State
    {
    	EMPTY,
    	EXIST,
    	DELETE
    };
    
    

    这里我们先创建节点的结构

    //哈希表每个位置存储的结构
    template<class K, class V>
    struct HashData
    {
    	pair<K, V> _kv;
    	State _state = EMPTY; //状态
    };
    

    为了保证负载因子不会过大,创建哈希表的时候要加入有效数据的个数,来保证接下来分析扩容。

    //哈希表
    template<class K, class V>
    class HashTable
    {
    public:
    	//...
    private:
    	vector<HashData<K, V>> _table; //哈希表
    	size_t _n = 0; //哈希表中的有效元素个数
    };
    
    

    哈希表的插入

    步骤:
    1、查看哈希表中是否存在该键值的键值对,如果有就不插入,因为哈希表不允许数据冗余。
    2、判断是否需要调整哈希表的大小,哈希表大小为0的话设置哈希表初始值。
    3.负载因子大于0.7需要增容,首先创建一个新的哈希表,新哈希表的大小设置为原哈希表的2倍,将原哈希表当中的数据插入到新哈希表,交换这两个哈希表。
    3、将键值对插入哈希表,首先通过哈希函数计算哈希地址,找到一个状态为EMPTY或DELETE的位置,将数据插入该位置,并将该位置的状态设置为EXIST。
    4、哈希表中的有效元素个数加一。

    //插入函数
    bool Insert(const pair<K, V>& kv)
    {
    	//1、查看哈希表中是否存在该键值的键值对
    	HashData<K, V>* ret = Find(kv.first);
    	if (ret)
    	{
    		return false; //插入失败
    	}
    
    	//2、判断是否需要调整哈希表的大小
    	if (_table.size() == 0) 
    	{
    		_table.resize(10); 
    	}
    	else if ((double)_n / (double)_table.size() > 0.7) //负载因子大于0.7需要增容
    	{
    		
    		HashTable<K, V> newHT;
    		newHT._table.resize(2 * _table.size());
    		
    		for (auto& e : _table)
    		{
    			if (e._state == EXIST)
    			{
    				newHT.Insert(e._kv);
    			}
    		}
    		//c、交换这两个哈希表
    		_table.swap(newHT._table);
    	}
    
    	//3、将键值对插入哈希表
    	//通过哈希函数计算哈希地址
    	size_t start = kv.first%_table.size(); 
    	size_t index = start;
    	size_t i = 1;
    	int base = index;
    	//找到一个状态为EMPTY或DELETE的位置
    	while (_table[index]._state == EXIST)
    	{
    		index = start + i; //线性探测
    		//index = start + i*i; //二次探测
    		index %= _table.size(); 
    		i++;
    	}
    	//将数据插入该位置,并将该位置的状态设置为EXIST
    	_table[index]._kv = kv;
    	_table[index]._state = EXIST;
    	
    	//4、哈希表中的有效元素个数加一
    	_n++;
    	return true;
    }
    
    

    哈希表的查找

    步骤:
    1.通过哈希函数计算哈希地址
    2.若该位置的状态为EXIST,并且key值匹配,则查找成功,直到找到空位置还没有找到目标元素,查找失败。

    //查找函数
    HashData<K, V>* Find(const K& key)
    {
    	if (_table.size() == 0) //哈希表大小为0,查找失败
    	{
    		return nullptr;
    	}
    
    	size_t start = key % _table.size(); //通过哈希函数计算哈希地址(除数不能是capacity)
    	size_t index = start;
    	size_t i = 1;
    	//直到找到空位置为止
    	while (_table[index]._state != EMPTY)
    	{
    		//若该位置的状态为EXIST,并且key值匹配,则查找成功
    		if (_table[index]._state == EXIST&&_table[index]._kv.first == key)
    		{
    			return &_table[index];
    		}
    		index = start + i; //线性探测
    		//index = start + i*i; //二次探测
    		index %= _table.size(); //防止下标超出哈希表范围
    		i++;
    	}
    	return nullptr; //直到找到空位置还没有找到目标元素,查找失败
    }
    
    

    注意: 在查找过程中,必须找到位置状态为EXIST,并且key值匹配的元素,才算查找成功。若仅仅是key值匹配,但该位置当前状态为DELETE,则还需继续进行查找,因为该位置的元素已经被删除了。

    哈希表的删除

    步骤:
    1.查看哈希表中是否存在该键值的键值对,若不存在则删除失败。
    2.若存在,则将该键值对所在位置的状态改为DELETE即可。
    3.哈希表中的有效元素个数减一。
    注意: 虽然删除元素时没有将该位置的数据清0,只是将该元素所在状态设为了DELETE,但是并不会造成空间的浪费,因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的,此时插入的数据就会把该数据覆盖。

    //删除函数
    bool Erase(const K& key)
    {
    	//1、查看哈希表中是否存在该键值的键值对
    	HashData<K, V>* ret = Find(key);
    	if (ret)
    	{
    		//2、若存在,则将该键值对所在位置的状态改为DELETE即可
    		ret->_state = DELETE;
    		//3、哈希表中的有效元素个数减一
    		_n--;
    		return true;
    	}
    	return false;
    }
    
    

    哈希桶的实现

    哈希表的结构

    在开散列的哈希表中,哈希表的每个位置存储的实际上是某个单链表的头结点,即每个哈希桶中存储的数据实际上是一个结点类型,该结点类型除了存储所给数据之外,还需要存储一个结点指针用于指向下一个结点。

    //每个哈希桶中存储数据的结构
    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 HashTable
    {
    public:
    	//...
    private:
    	vector<Node*> _table; //哈希表
    	size_t _n = 0; //哈希表中的有效元素个数
    };
    
    

    哈希表的插入

    步骤:
    1.查看哈希表中是否存在该键值的键值对,若已存在则插入失败。
    2.判断是否需要调整哈希表的大小,若哈希表的大小为0,或负载因子过大都需要对哈希表的大小进行调整。
    3.将键值对插入哈希表。
    4.哈希表中的有效元素个数加一。

    //插入函数
    bool Insert(const pair<K, V>& kv)
    {
    	//1、查看哈希表中是否存在该键值的键值对
    	Node* ret = Find(kv.first);
    	if (ret) //哈希表中已经存在该键值的键值对(不允许数据冗余)
    	{
    		return false; //插入失败
    	}
    
    	//2、判断是否需要调整哈希表的大小
    	if (_n == _table.size()) //哈希表的大小为0,或负载因子超过1
    	{
    		//增容
    		//a、创建一个新的哈希表,新哈希表的大小设置为原哈希表的2倍(若哈希表大小为0,则将哈希表的初始大小设置为10)
    		vector<Node*> newtable;
    		size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
    		newtable.resize(newsize);
    
    		//newtable.resize(GetNextPrime(_table.size()));
    		
    		//b、将原哈希表当中的结点插入到新哈希表
    		for (size_t i = 0; i < _table.size(); i++)
    		{
    			if (_table[i]) //桶不为空
    			{
    				Node* cur = _table[i];
    				while (cur) //将该桶的结点取完为止
    				{
    					Node* next = cur->_next; //记录cur的下一个结点
    					size_t index = cur->_kv.first%newtable.size(); //通过哈希函数计算出对应的哈希桶编号index(除数不能是capacity)
    					//将该结点头插到新哈希表中编号为index的哈希桶中
    					cur->_next = newtable[index];
    					newtable[index] = cur;
    
    					cur = next; //取原哈希表中该桶的下一个结点
    				}
    				_table[i] = nullptr; //该桶取完后将该桶置空
    			}
    		}
    		//c、交换这两个哈希表
    		_table.swap(newtable);
    	}
    
    	//3、将键值对插入哈希表
    	size_t index = kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index(除数不能是capacity)
    	Node* newnode = new Node(kv); //根据所给数据创建一个待插入结点
    	//将该结点头插到新哈希表中编号为index的哈希桶中
    	newnode->_next = _table[index];
    	_table[index] = newnode;
    
    	//4、哈希表中的有效元素个数加一
    	_n++;
    	return true;
    }
    
    

    哈希表的查找

    1.先判断哈希表的大小是否为0,若为0则查找失败。
    2.通过哈希函数计算出对应的哈希地址。
    3.通过哈希地址找到对应的哈希桶中的单链表,遍历单链表进行查找即可。

    //查找函数
    HashNode<K, V>* Find(const K& key)
    {
    	if (_table.size() == 0) //哈希表大小为0,查找失败
    	{
    		return nullptr;
    	}
    
    	size_t index = key % _table.size(); //通过哈希函数计算出对应的哈希桶编号index(除数不能是capacity)
    	//遍历编号为index的哈希桶
    	HashNode<K, V>* cur = _table[index];
    	while (cur) //直到将该桶遍历完为止
    	{
    		if (cur->_kv.first == key) //key值匹配,则查找成功
    		{
    			return cur;
    		}
    		cur = cur->_next;
    	}
    	return nullptr; //直到该桶全部遍历完毕还没有找到目标元素,查找失败
    }
    
    

    哈希表的删除

    步骤:
    1.通过哈希函数计算出对应的哈希桶编号。
    2.遍历对应的哈希桶,寻找待删除结点。
    3.若找到了待删除结点,则将该结点从单链表中移除并释放。
    4.删除结点后,将哈希表中的有效元素个数减一。

    //删除函数
    bool Erase(const K& key)
    {
    	//1、通过哈希函数计算出对应的哈希桶编号index(除数不能是capacity)
    	size_t index = key % _table.size();
    	//2、在编号为index的哈希桶中寻找待删除结点
    	Node* prev = nullptr;
    	Node* cur = _table[index];
    	while (cur) //直到将该桶遍历完为止
    	{
    		if (cur->_kv.first == key) //key值匹配,则查找成功
    		{
    			//3、若找到了待删除结点,则删除该结点
    			if (prev == nullptr) //待删除结点是哈希桶中的第一个结点
    			{
    				_table[index] = cur->_next; //将第一个结点从该哈希桶中移除
    			}
    			else //待删除结点不是哈希桶的第一个结点
    			{
    				prev->_next = cur->_next; //将该结点从哈希桶中移除
    			}
    			delete cur; //释放该结点
    			//4、删除结点后,将哈希表中的有效元素个数减一
    			_n--;
    			return true; //删除成功
    		}
    		prev = cur;
    		cur = cur->_next;
    	}
    	return false; //直到该桶全部遍历完毕还没有找到待删除元素,删除失败
    }
    
    
    更多相关内容
  • 哈希和哈希桶

    2021-10-31 23:54:34
    哈希桶也是如此,哈希桶的规则中,当哈希桶中元素的个数与桶的个数相等时,就要考虑扩容,哈希桶的容量改变后,哈希函数计算的地址也改变了,所以要将旧哈希桶中的元素搬移到新的哈希桶中。 有时候会有些更极端的...

    概念

    数据结构中有一类常用于搜索,给定一个元素集合,常见的可用于搜索的算法有
    遍历,遍历是十分粗暴简单的手段,对于元素的集合没有特殊要求,时间复杂度是O(N)。效率通常较低。
    二分查找,二分查找要求元素集合有序,时间复杂度为O(logN),
    二叉搜索树,查找规则简单,但是退化为单支树时间复杂度是O(N),
    AVL树和红黑树,时间复杂度都是O(logN).

    上面的这些常用的方法无一例外都有一个关键步骤就是元素的比较,通过比较待查找元素和集合中的元素,来确定该元素在集合中的位置。真实的效率取决于比较的次数。

    如果有不需要进行元素比较就能查找的方法,就能达到理想的查找。

    哈希就是这样一种数据结构,

    在存储元素时,通过某些方法,将元素与所存储的位置建立一一对应的关系,则在查找时就可以不需要进行数据的比较。这种方法称为哈希散列方法。元素存储的集合称为哈希表或者散列表,建立映射关系的方法称为哈希函数或者散列函数。通过这个函数来计算元素来计算元素在哈希表中的插入位置。

    比如,
    元素集合:1 6 7 5 4 9
    哈希函数:f(x) = x % capacity

    插入元素时,通过哈希函数计算该元素在哈希表中的位置, 1%10 = 1,则1放在1号位置。
    在这里插入图片描述
    查找元素时,通过函数计算该元素在表格中的位置,检测该位置上存储的元素是否是待查找元素。

    哈希冲突

    如果新增一个元素11,通过哈希函数计算,结果应该插入在1的位置,此时该位置已经有元素了,这就是哈希冲突的产生原因,当不同的元素通过相同哈希函数计算出相同的哈希地址,这种问题成为哈希冲突。

    哈希函数的设计

    如果哈希函数的设计不合理,则会产生不同元素的哈希地址集中存在与某一段地址范围中,使得哈希冲突产生的概率非常高。因此哈希函数要求
    1.函数的定义域必须包含所有要存储的关键码,散列表如果有m个地址,其值域必须在[0,m)之间。
    2.哈希函数计算出来的地址要能均匀的分布在哈希表中。
    3.哈希函数应尽量简单

    常用的方法:
    直接定址法,取关键字的某个线性函数作为散列地址, Hash = A*Key+B ,这种函数简单且分布均匀,但是要提前分析关键字的分布情况,适用于元素集合较小且连续的情况。比如查找字符串中只出现一次的字符。就可以采用直接定址法,将字符串中字符的ASCII码值作为数组下标,统计次数。

    除留余数法,设散列表中的地址数为m,在不大于m的数中取一个接近或等于m的的素数p,设计
    Hash = Key % p这样的方法计算哈希地址。是非常常用的一种方法。

    平方取中法,比如关键字为1234,那它的平方就是1522756,取中间3位得到227作为哈希地址,5678的平方Wie23239684,则取中间的3位239或者396作为哈希地址。平方取中法比较适合不知道关键字的分布情况,关键字的位数又不是很大时用。

    折叠法,首先将关键字分割成位数相等的几部分,比如关键字12345678,可以分为123,456,78,最后一个可以位数短一点,将分出来的数相加并根据散列表的容量取靠后的位数作为散列表地址。适合用于关键字位数较多的情况。

    随机数法,取关键字的随机函数值作为哈希地址,Hash = random(Key),适合用于关键字长度不等的情况。

    数学分析法,有n个位数相同的数字,每个位上都有r种不同的符号,出现概率不一定相同,可能在某几位上分布比较平衡,根据散列表的大小,选择符号分布较均匀的几位作为哈希地址,比如手机号码的集合,前三位的分布重复较多都是1几几,不均匀,而后四位分布较均匀。

    哈希函数的设计只能尽量降低产生哈希冲突的概率,不论一个哈希函数设计的多么科学,都无法彻底避免哈希冲突的产生。

    哈希冲突的解决方式

    闭散列

    在这里插入图片描述
    在上面的例子中,如果要继续向哈希表中插入元素54,根据哈希函数算出的地址,应该插入在5的位置,而5的位置上已经有元素了,闭散列的处理方式在5的元素之后开始依次向后查找有没有非空的位置,找到了就将这个元素插入进去,如果找到末尾也没有,则返回表头从表头开始继续找非空的位置。
    闭散列中,哈希表中的每个位置都增加了一个标识用来表示状态
    在这里插入图片描述

    EMPTY,表示该位置为空,EXIST,表示该位置上有有效元素,DELETE表示该位置元素被删除了。在插入时,通过哈希函数计算出地址后,先检测该位置有没有发生哈希冲突,如果没有发生就直接插入并将该位置状态修改为EXIST,删除时,先通过哈希函数计算表中的位置,发现该位置有元素,与待删除元素进行比较,如果是则直接删除,但是该位置的状态不能修改成EMPTY,应改为DELETE,因为如果该位置为空,则表明该元素不存在。
    

    这种依次查找空位的方式称为线性探测,线性探测插入和删除的规则比较简单,但是存在一定缺陷,发生哈希冲突时,容易产生数据的堆积,导致堆积的元素占用大量空余的位置,增加查找时的时间消耗影响效率。

    另一种方式称为二次探测,不再通过挨个去找空位的方式,下一个位置是通过H(i) = (H0 + i²) 或者H(i) = H0 - i²的方式去计算。与线性探测相比,能解决数据堆积的问题,但是线性探测最差情况下,走完一圈哈希表就能找到,而二次探测不能确定。当表中空位置比较少时,可能需要找很多次。

    总的来说,当哈希表中的元素存了非常多的时候,表中的剩余位置越来越少,发生冲突的概率就越来越高,而且会影响探测的效率,哈希是追求高效查找的数据结构,而当哈希表中有效元素很多时,会大大影响效率。解决这个问题就需要哈希表中存储的元素不能太多,达到一定程序就要扩容,所以哈希表一定是不会存满的。具体什么情况下扩容,提到负载因子的概念,负载因子是有效元素/空间总数的值,有研究表明,线性探测负载因子达到70%左右就应该进行扩容,而二次探测负载因子达到50%就应该进行扩容。因此哈希也是一种空间利用率较低的数据结构。

    开散列

    开散列又称链地址法,相比于闭散列在开发中应用更多,开散列实际上是数据与链表的集合,数组中的每个元素都是单链表,链表上挂载发生哈希冲突的元素。
    在这里插入图片描述

    首先通过哈希函数计算出哈希地址,然后,具有相同哈希地址的元素归为一个集合中,称为一个桶,桶中的元素通过单链表组织起来。哈希表中存放链表的头,这种结构称为哈希桶。

    根据哈希桶的规则,插入元素的理想状态,
    在这里插入图片描述
    而实际上,当插入的元素比较特殊时,依然会导致大部分元素集中在一个链表中,导致某些链表特别长,这样一来,在哈希桶中查找元素实际上变成了在链表中查找元素,链表的查询时间复杂度是O(N),因此插入元素也应该避免这种问题的出现。闭散列当中是通过根据负载因子来进行扩容的方式解决问题的。哈希桶也是如此,哈希桶的规则中,当哈希桶中元素的个数与桶的个数相等时,就要考虑扩容,哈希桶的容量改变后,哈希函数计算的地址也改变了,所以要将旧哈希桶中的元素搬移到新的哈希桶中。
    有时候会有些更极端的情况,虽然没达到扩容的条件,但是某些链表中挂载的节点已经非常多了,哈希表的性能因此会下降,此时的处理方法是当链表中的节点达到一定的阈值还没有得到扩容时,将链表转换成红黑树。一般设计是当链表中节点的个数等于8的时候,就将链表转换为红黑树,删除时,当红黑树中的节点个数小于6的时候,再将红黑树转换位链表。

    除留取余法的设计,除留取余法要取一个不大于表的容量但最接近于它的素数,在SGI-STL3.0版本中,hash_map底层给出了一个和除留取余法有关的确定素数的方法。将常用的28个素数枚举出来。
    53ul, 97ul, 193ul, 389ul, 769ul,
    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    1610612741ul, 3221225473ul, 4294967291ul
    泛型设计:理想的哈希表应该能存储任意元素,但是有些元素不能直接取模运算,比如常见的字符串类型。atoi只能将数字类型的字符串转换为字符串格式,因此要借助一些其他的算法来实现取模的运算,有住专门设计的字符串哈希算法等。

    实现一个简单的哈希桶

    #pragma once
    
    #include<iostream>
    #include"Common.h"
    #include<vector>
    
    using namespace std;
    
    template<class T>
    
    struct HashBucketNode {
    	HashBucketNode<T>* next;
    	T data;
    
    	HashBucketNode(const T& x = T())
    		:next(nullptr)
    		,data(x)
    	{}
    };
    
    template<class T>
    
    class T2Intdef {
    public:
    	const T& operator()(const T& data) {
    		return data;
    	}
    };
    
    //一种字符串转整形的算法
    class T2str {
    public:
    	size_t operator()(const string& s){
    		const char* str = s.c_str();
    		unsigned int seed = 131;
    		unsigned int hash = 0;
    		while (*str)
    		{
    			hash = hash * seed + (*str++);
    		}
    		return (hash & 0x7FFFFFFF);
    	}
    };
    
    
    template<class T,class T2Int = T2Intdef<T>>
    
    class HashBucket {
    	typedef HashBucketNode<T> Node;
    public:
    	HashBucket(size_t capacity = 53)
    		:table(Getnextprime(capacity))
    		,size(0)
    	{}
    	
    	~HashBucket() {
    		Destroy();
    	}
    
    	bool Insert(const T& data) {
    		//检测是否需要扩容
    		Checkcapacity();
    		size_t bucketloc = Hashfuc(data);
    		Node* cur = table[bucketloc];
    		while (cur) {
    			if (data == cur->data) {
    				return false;
    			}
    			cur = cur->next;
    		}//有位置可插入,必是cur走到了空的位置
    
    		cur = new Node(data);
    
    		cur->next = table[bucketloc];
    		table[bucketloc] = cur;
    		++size;
    		//就是链表头插法,本来链表的首节点是table[bucketloc]
    		//先把头结点的地址交给cur的next
    		//再设置cur称为新的头结点
    		return true;
    	}
    
    	bool Erase(const T& data) {
    		size_t bucketloc = Hashfuc(data);
    		Node* cur = table[bucketloc];
    		Node* prev = nullptr;
    		while (cur) {
    			if (data == cur->data) {
    				//判断cur是不是头结点
    				if (nullptr == prev) {
    					table[bucketloc] = cur->next;
    				}
    				else {
    					prev->next = cur->next;
    				}
    				delete cur;
    				--size;
    				return true;
    			}
    			else {
    				prev = cur;
    				cur = cur->next;
    			}
    		}
    		return false;
    	}
    
    	Node* Find(const T& data) {
    		size_t bucketloc = Hashfuc(data);
    		Node* cur = table[bucketloc];
    		while (cur) {
    			if (data == cur->data) {
    				return cur;
    			}
    			cur = cur->next;
    		}
    		return nullptr;
    	}
    
    	size_t Size()const {
    		return size;
    	}
    
    	bool Empty() {
    		return 0 == size;
    	}
    
    	void Print() {
    		for (size_t i = 0; i < table.capacity(); i++) {
    			Node* cur = table[i];
    			cout << "table[" << i << "]";
    			while (cur) {
    				cout << cur->data << "--->";
    				cur = cur->next;
    			}
    			cout << "NULL" << endl;
    		}
    		cout << "=========================================";
    	}
    
    	void Swap(HashBucket<T,T2Int>& ht) {
    		table.swap(ht.table);
    		std::swap(size, ht.size);
    	}
    
    private:
    	//哈希函数 除留取余法
    	size_t Hashfuc(const T& data) {
    		T2Int t2int;
    		return t2int(data) % table.capacity();
    	}
    
    	void Destroy() {
    		for (size_t i = 0; i < table.capacity(); i++) {
    			Node* cur = table[i];
    			while (cur) {
    				table[i] = cur->next;
    				delete cur;
    				cur = table[i];
    			}
    		}
    		size = 0;
    	}
    	void Checkcapacity() {
    		//当有效元素个数存满
    		if (size == table.capacity()) {
    			//创建一个新的哈希桶
    			HashBucket<T, T2Int> newh(Getnextprime(table.capacity()));
    			//旧表拆下来
    			for (size_t i = 0; i < table.capacity(); i++) {
    				Node* cur = table[i];
    				while (cur) {
    					table[i] = cur->next;
    					size_t newloc = newh.Hashfuc(cur->data);
    					cur->next = newh.table[newloc];
    					newh.table[newloc] = cur;
    					newh.size++;
    					cur = table[i];
    					//先断开cur
    				}
    			}
    			this->Swap(newh);
    		}
    	}
    private:
    	std::vector<Node*> table;//哈希表
    	size_t size;//有效元素的个数
    };
    
    #pragma once
    
    
    const int PRIMECOUNT = 28;
    const size_t primeList[PRIMECOUNT] =
    {
    	53ul, 97ul, 193ul, 389ul, 769ul,
    	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    	1610612741ul, 3221225473ul, 4294967291ul
    };
    
    size_t Getnextprime(size_t prime) {
    	size_t i = 0;
    	for (; i < PRIMECOUNT; i++) {
    		if (primeList[i] > prime) {
    			return primeList[i];
    		}
    	}
    	return primeList[i];
    }
    

    底层为哈希桶的容器:
    unordered系列容器
    unordered_map
    unordered_set
    unordered_multimap
    unordered_multiset
    这些容器底层都是哈希桶结构,在C++11中提出,使用时包含头文件<unordered_map><unorder_set>,查询效率为O(1),应用于不关心元素序列是否有序,追求查找效率的场景中,内部只有正向迭代器。

    展开全文
  • 避免冲突与解决冲突3.1 避免冲突的方式1——哈希函数的设计3.2 避免冲突的方式2——负载因子的调节3.3 解决冲突的方式1——闭散列3.4 解决冲突的方式2——开散列、哈希桶(重要)4.哈希表查找成功与查找失败的求法4.1 ...

    一、哈希表

    1.哈希表概念

    可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。它存储的空间叫哈希表。增删查改的时间复杂度都是O(1)。

    当向该结构中:

    1、插入元素
    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
    2、搜索元素
    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。

    该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

    例如:数据集合{1,7,6,4,5,9};

    哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

    在这里插入图片描述
    用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快,时间复杂度为O(1) 。 问题:按照上述哈希方式,若下标4中已经有元素,向集合中插入元素44,会出现什么问题?

    2.冲突的概念

    冲突是指:不同的关键字key,通过相同的哈希函数,得到了相同的位置,该种现象称为哈希冲突或哈希碰撞。

    把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

    3.避免冲突与解决冲突

    首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题,冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率。

    避免冲突的方式有两种,一种是设置合理的哈希函数,另一种是负载因子调节。负载因子越大,则冲突率越大。

    在这里插入图片描述

    3.1 避免冲突的方式1——哈希函数的设计

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

    常见哈希函数的设置:

    1. 直接定制法–(常用)
      取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况。
    2. 除留余数法–(常用)
      设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址
    3. 平方取中法–(了解)
      假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况。
    4. 折叠法–(了解)
      折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
      折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况。
    5. 随机数法–(了解)
      选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法。
    6. 数学分析法–(了解)
      设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某
      些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如:
      在这里插入图片描述
      假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是相同的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

    数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。

    注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突。

    3.2 避免冲突的方式2——负载因子的调节

    在这里插入图片描述
    负载因子和冲突率的关系粗略演示:
    在这里插入图片描述
    所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。

    已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。

    总结:负载因子的计算公式:当前存入表中的数据个数/表的大小。因此如果要降低负载因子,只能通过增大表的长度来实现。

    3.3 解决冲突的方式1——闭散列

    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。找到下一个空位置的闭散列的方法有两种:

    1. 线性探测
      比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。

    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

    插入操作:
    1、通过哈希函数获取待插入元素在哈希表中的位置。
    2、如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素。
    在这里插入图片描述
    采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

    缺点:会把冲突的元素都堆积在一起。

    1. 二次探测
      二次探测为了避免线性探测的缺点,它找下一个空位置的方法为:
      在这里插入图片描述
      或者减i的平方。i为冲突的次数,i从1开始。

    例如:
    当哈希表如下图后,要插入44,但4下标中已经有元素了,此时是第一次冲突,因此计算Hi=(4+1)%10=5 。
    在这里插入图片描述
    此时再插入24,但是4下标已经有元素了,是第一次冲突。再向后一个下标找,此时5下标已经有元素了,是第二次冲突。再向后找,6下标没有元素,则Hi=(4+4)%10=8,则24放入8下标中。
    在这里插入图片描述
    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。

    因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。

    3.4 解决冲突的方式2——开散列、哈希桶(重要)

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

    哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了,那如果冲突严重,就意味着小集合的搜索性能其实也时不佳的,这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化,例如:

    1. 每个桶的背后是另一个哈希表
    2. 每个桶的背后是一棵搜索树(红黑树)

    链地址法的图示:当有哈希桶在某个下标下,则哈希表对应下标的值为链表头结点的地址,如果没有则为null。每个结点都由key,value与next组成。
    在这里插入图片描述
    细节操作:
    因为是用哈希桶来解决冲突,因此要创建一个每个下标底下都是结点组成的链表的数组Node[] array;,并且用usedSize来记录数组中结点的个数,目的是求出负载因子。而每个哈希桶都是由结点组成的,因此结点类可以定义到哈希桶类里面。

    put、resize方法:先根据设计的哈希函数求出对应的下标,找到对应下标后去遍历该下标的链表,**如果已经有相同的key值的结点,则更新完key值中的value后退出。**如果没有,则创建一个哈希桶,设置cur结点从头结点开始,用头插法插入新的结点。当然,插入后要计算出负载因子是否超过了0.75,如果超过就扩容。**扩容后数组的长度会变长,因此每个哈希桶根据新的哈希函数的计算结果跟原来的不同,则要重新哈希。(resize方法)**等全部哈希桶重新哈希完之后,新的数组的引用要赋值给旧的数组的引用。

    get方法:首先要根据哈希函数求出对应的下标,再从下标当中去找是否有相同的值的哈希桶,若有,则返回该哈希桶的value值,否则返回-1。

    总体代码:

    public class HashBucket {
    
        static class Node {
            public int key;
            public int val;
            public Node next;
    
            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }
    
        private Node[] array;
        public int usedSize;
    
        public HashBucket() {
            this.array = new Node[10];
            this.usedSize = 0;
        }
    
    
        public void put(int key,int val) {
            //1、确定下标
            int index = key % this.array.length;
            //2、遍历这个下标的链表
            Node cur = array[index];
            while (cur != null) {
                //更新val
                if(cur.key == key) {
                    cur.val = val;
                    return;
                }
                cur = cur.next;
            }
            //3、cur == null   当前数组下标的 链表  没要key
            Node node = new Node(key,val);
            node.next = array[index];
            array[index] = node;
            this.usedSize++;
            //4、判断  当前 有没有超过负载因子
            if(loadFactor() >= 0.75) {
                //扩容
                resize();
            }
        }
    
        public int get(int key) {
            //以什么方式存储的  那就以什么方式取
            int index = key % this.array.length;
            Node cur = array[index];
            while (cur != null) {
                if(cur.key == key) {
                    return cur.val;
                }
                cur = cur.next;
            }
            return -1;//
        }
    
        public double loadFactor() {
            return this.usedSize*1.0 / this.array.length;
        }
    
        public void resize() {
            //自己创建新的2倍数组
            Node[] newArray = new Node[2*this.array.length];
            //遍历原来的哈希桶
            //最外层循环 控制数组下标
            for (int i = 0; i < this.array.length; i++) {
                Node cur = array[i];
                Node curNext = null;
                while (cur != null) {
                    //记录cur.next
                    curNext = cur.next;
                    //在新的数组里面的下标
                    int index = cur.key % newArray.length;
                    //进行头插法
                    cur.next = newArray[index];
                    newArray[index] = cur;
                    cur = curNext;
                }
            }
            this.array = newArray;
        }
    
    
        public static void main(String[] args) {
            HashBucket hashBucket = new HashBucket();
            hashBucket.put(1,1);
            hashBucket.put(4,4);
            hashBucket.put(14,14);
            hashBucket.put(24,24);
            hashBucket.put(34,34);
            hashBucket.put(44,44);
            hashBucket.put(54,54);
            hashBucket.put(64,64);
    
            System.out.println(hashBucket.get(54));
            System.out.println("ffafas");
        }
    }
    

    4.哈希表查找成功与查找失败的求法

    查找成功和查找失败是将数据都填入哈希表后再求的。

    4.1 查找成功的求法

    一个哈希表如下图:
    在这里插入图片描述
    假设现在要查找4,则根据哈希函数Hash(key)=key%array.length,找到了4下标,因为4下标下的数据就是4,则查找一次就成功,1和9数据的查找成功次数求法也是一致。
    假设此时要查找24,则先根据哈希函数求出下标为4,但是4下标的数据是4,而不是24,算查找一次。此时往后移一个单位,发现是44不是我们查找的24,则算查找第二次。此时再往后移一个单位,发现是24,算是查找的次数是第三次。

    因此上图中查找成功的平均查找长度:(1+1+2+3+1)/5=8/5。

    如果找9下标的值查找的不是要查找的数据,则返回到0下标开始找,并且找9下标失败后算查找1次。

    4.2 查找失败的求法

    一个哈希表如下图:
    在这里插入图片描述
    第一次假如找数据1,则根据哈希函数Hash(key)=key%array.length求得下标为1,假设下标1中的数据不是我们找的数据1,算查找失败了一次,则向后移一个单位去找。此时下标2的值为空,则说明查找失败,算查找失败了两次。

    假如此时找数据44,根据哈希函数求得下标为4,但此时下标4下的数据不是44,则没有保证在查找成功的前提下去查找。因此向后移一个单位去找,此时发现下标5的数据是44,则查找失败的次数从此时才开始计算。我们还是要假设当前5下标是查找失败的,算查找失败一次,则再向后移一个单位去找。还是一样,假设下标6的值不是44,查找失败,则向后移一个单位去找。到下标7后,发现该下标的数据为空,则肯定是查找失败,这次也算查找一次,因此查找失败的长度加起来一共有三次。

    注:查找失败的操作是从真正找到要找的值开始向后找下一个空的地方。

    二、用泛型实现开散列与开散列在源码上的底层实现

    1.用泛型实现开散列

    用泛型实现哈希表则它的key和val都是引用类型,不能跟上面的一样直接用大于小于号比较。

    步骤:首先定义一个类Person创建带有一个参数的构造方法。再将HashBuck类变为泛型类,直接再类名后加<K,V>,并且哈希表中每个下标的值都是一个链表,链表由结点组成,因此要设置public Node<K,V>[] array = (Node<K,V>[])new Node[10];

    因为我们的key是引用类型,不能直接用哈希函数去求下标,那么如何将一个引用转化为一个数值去求下标呢?

    此时我们自己实现的类(key)要同时实现equals和hashcode方法,hashcode方法是为了将一个引用类型转换为一个数值从而达到去求它要存储的对应的下标。equals方法是判断两个引用是否是相同的。

    如:
    当之间用== 比较,则比较的是地址,为false。

    class Student {
        public int id;
    
        public Student(int id) {
            this.id = id;
        }
    }
    public class Test {
        public static void main(String[] args) {
            Student student1 = new Student(12);
            Student student2 = new Student(12);
            System.out.println(student1==student2);
        }
    }
    //打印结果:false
    

    但是重写equals方法后,如下例子相当于判断是否是相同的一个人,因为它们的id都相同。

    class Student {
        public int id;
    
        public Student(int id) {
            this.id = id;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return id == student.id;
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(id);
        }
    }
    public class Test {
        public static void main(String[] args) {
            Student student1 = new Student(12);
            Student student2 = new Student(12);
            System.out.println(student1.equals(student2));
        }
    }
    //打印结果:true
    

    面试问题:

    1. hashcode和equals的区别?
      答:如果在HashMap中,hashcode的作用是定位当前key值应该存储的下标位置。equals的作用是在经过hashcode定位某个下标后,遍历链表,比较哪个key是相同的。
    2. 为什么hashcode和equals要同时出现?
      答:在HashMap中,首先要经过hashcode定位存储的下标,但是如果要获取某个key时,要用到equals方法,因此在HashMap中hashcode和equals是配套使用的。因此以后在hashmap中要存放自己自定义的数据类型,一定要在自定义的数据类型的类里面重新hashcode和equals方法。
    3. 当两个数据的equals相同,则hashcode相同吗?那如果两个数据的hashcode相同,equals一定相同吗?如果两个数据的hashcode不同,则equals一定相同吗?
      答:当两个数据的equals相同,hashcode一定相同。如果两个数据的hashcode相同,equals不一定相同。如果两个数据的hashcode不同,则equals一定不相同。

    总体代码:

    class Person {
        public String id;
    
        public Person(String id) {
            this.id = id;
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;
            return Objects.equals(id, person.id);
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(id);
        }
    }
    class HashBuck<K,V> {
        static class Node<K,V> {
            public K key;
            public V val;
            public Node<K,V> next;
    
            public Node(K key, V val) {
                this.key = key;
                this.val = val;
            }
        }
    
        public Node<K,V>[] array = (Node<K,V>[])new Node[10];
        public int usedSize ;
    
        public void put(K key,V val) {
            int hash = key.hashCode();
            int index = hash%array.length;
            Node<K,V> cur = array[index];
            while(cur!=null) {
                if(cur.val.equals(val)) {
                    return;
                }
                cur=cur.next;
            }
            Node<K,V> node = new Node<>(key,val);
            node.next=array[index];
            array[index]=node;
            usedSize++;
            if(loadFactor()>=0.75) {
                resize();
            }
        }
        public void resize() {
            Node<K,V>[] newArray = (Node<K,V>[])new Node[2*array.length];
            for (int i = 0; i < array.length; i++) {
                Node<K,V> cur = array[i];
                while(cur!=null) {
                    int hash = cur.key.hashCode();
                    int index = hash% newArray.length;
                    Node<K,V> curNext = cur.next;
                    cur.next=newArray[index];
                    newArray[index]=cur;
                }
            }
            array=newArray;
        }
    
        public double loadFactor() {
            return usedSize*1.0/array.length;
        }
    
        public V get(K key) {
            int hash = key.hashCode();
            int index = hash%array.length;
            Node<K,V> cur = array[index];
            while(cur!=null) {
                if(cur.key.equals(key)) {
                    return cur.val;
                }
                cur=cur.next;
            }
            return null;
        }
    }
    public class Test {
        public static void main(String[] args) {
            Person person1 = new Person("123");
            Person person2 = new Person("123");
            HashBuck<Person,String> hashBuck = new HashBuck<>();
            hashBuck.put(person1,"zjr");
            System.out.println(hashBuck.get(person2));
        }
    }
    

    2.开散列在源码上的底层实现

    哈希桶的基本原理在3.4小节中已经提到,那么在Java当中它是如何去实现开散列的呢?
    注:Java中HashMap和HashSet的底层都是开散列的处理方式。

    在存放的时候:
    1、找当前位置链表中是否有相同的key。
    2、当数组超过64,并且有一个链表超过8时,链表就变成一棵红黑树来处理,它查找的效率更快。
    3、JDK1.8后,数组中当有元素插入时链表实现的是尾插法。

    点入Java中的HashMap学习它的源码:
    1、
    在这里插入图片描述
    在HashMap类当中定义了一个结点类,并且实现了Map.Entry<K,V>,说明HashMap当中有结点的组成。

    2、默认的初始容量为16。在这里插入图片描述
    3、数组的最大长度为2^30
    在这里插入图片描述
    4、默认的负载因子0.75f
    在这里插入图片描述
    5、变为红黑树的前提是数组的大小超过64
    在这里插入图片描述
    6、HashMap中的数组名为table,初始长度为0。
    在这里插入图片描述
    7、调用无参的构造方法是将负载因子赋值。
    在这里插入图片描述

    2.1 HashMap底层面试题

    要想会面试题,必须把下面的图以及参考部分的源码看懂。

    第一次put:
    在这里插入图片描述
    第二次put:
    在这里插入图片描述
    冲突时如何去调整:
    在这里插入图片描述
    对应第一题:
    在这里插入图片描述

    1、如果new HashMap(19),bucket数组多大? 答:2^5=32 。
    2、HashMap什么时候开辟bucket数组占用内存? 答:第一次put时。
    3、hashmap何时扩容? 答:负载因子为0.75f时。
    4、当两个对象的hashcode相同会发生什么? 答:哈希冲突或碰撞。
    5、如果两个键的hashcode相同,你如何获取值对象? 答:在hashcode的数组位置开始遍历链表。
    6、你了解重新调整HashMap大小存在什么问题吗? 答:重新哈希。

    展开全文
  • 14 哈希表和哈希桶

    千次阅读 2022-01-17 14:05:52
    代码实现五、开散列(哈希桶)5.1. 开散列扩容5.2. 代码实现六、闭散列和开散列的比较 一、哈希表 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把...


    一、哈希表

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,通过这种方式,可以不经过任何比较,一次直接从表中得到要搜索的元素,即查找的时间复杂度为 O(1)。
    这个映射函数叫做哈希(散列)函数,存放记录的数组叫做哈希(散列)表。

    最典型的例子是计数排序,将要排序的数组每个元素和新开辟的数组的下标进行映射。

    向哈希表中插入和搜索元素的过程如下:
    先用哈希函数将被要插入或查找的键值转化为数组的一个索引。

    • 插入元素: 根据索引位置,将元素存放到此位置。
    • 搜索元素: 根据索引,找到存储在该索引位置的元素。

    在理想情况下,不同的键都能转化为不同的索引值。当然,这只是理想情况,所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。这就是哈希冲突的问题。

    二、哈希函数

    2.1. 直接定址法(常用)

    取关键字的某个线性函数作为散列地址:hash(key)=A*key + B
    优点:简单、均匀
    缺点:实现需要知道关键字的分布情况,并且只适合查找比较小,且连续分布的情况
    适用场景:查找字符串中,第一次出现的单词:构建一个数组 hash[ch-‘a’] 即为对应的地址
    不适用场景:给一批数据, 1 5 8 100000 像这数据跨度大,数据元素不连续,很容易造成空间浪费

    2.2. 除留余数法(常用)

    设散列表中允许的地址数为m,通常是取一个不大于m,但是最接近或者等于m的质数num,作为除数,按照哈希函数进行计算hash(key)= key%num, 将关键码转换成哈希地址
    优点:使用场景广泛,不受限制。
    缺点:存在哈希冲突,需要解决哈希冲突,哈希冲突越多,效率下降越厉害。

    2.3. 几种不常用的方法

    1. 平方取中法

    hash(key)=key*key 然后取函数返回值的中间的几位,作为哈希地址
    比如 25^2 = 625 取中间的一位 2 作为哈希地址

    比较适合不知道关键字的分布,而位数又不是很大的情况

    1. 折叠法

    将关键字从左到右分割成位数相等的几部分(最后一部分可以短些),然后将这几部分叠加求和,并且按照散列表长度,取最后几位作为散列地址

    适用于不知道关键字分布,关键字位数比较多的情况

    1. 随机数法

    选取一个随机函数,取关键字的随机函数值,作为它的哈希地址,hash(key) = random(key),random为随机函数

    通常用于关键字长度不等的情况

    1. 数学分析法

    通过实现分析关键字,来获取哈希地址

    比如用每个人的手机号码充当关键字,如果采用前三位作为哈希地址,那么冲突的概率是非常大的。如果采用的是中间3位那么冲突的概率要小很多

    常用于处理关键字位数比较大的情况,且事前知道关键字的分布和关键字的若干位的分布情况


    三、哈希冲突

    不同关键字通过相同哈希函数计算出相同的哈希映射地址,这种现象称为哈希冲突或哈希碰撞。
    在这里插入图片描述

    解决哈希冲突通常有两种方法:闭散列(开放地址发)和开散列(链地址法)。


    四、闭散列

    闭散列也叫做开放地址法,当发生哈希冲突的时候,如果哈希表未被填满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置的"下一个"空位置中去,寻找下一个空位置的方法有线性探测法和二次探测法

    4.1. 线性探测

    从发生冲突的位置开始,依次向后探测,直到寻找到下一个位置为止

    优点:实现非常简单
    缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据"堆积",即不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要进行多次比较,导致搜索效率降低。
    在这里插入图片描述

    4.2. 负载因子

    随着哈希表中数据的增多,产生哈希冲突的可能性也随着增加。
    我们将数据插入到有限的空间,那么空间中的元素越多,插入元素时产生冲突的概率也就越大,冲突多次后插入哈希表的元素,在查找时的效率必然也会降低。介于此,哈希表当中引入了负载因子(载荷因子):

    散列表的载荷因子定义为 α = 填入表中的元素 / 散列表的长度

    α是散列表装满程度的标志因子,α越大表明装入表中的元素越多,产生冲突的可能性也就越大,反之填入表中的元素越少,冲突可能性越低,空间利用率也就越低

    闭散列:一般将载荷因子控制在 0.7-0.8以下,超过0.8查表时候的缓存不中率会按照指数曲线上升(哈希可能性冲突越大),因此一般hash库中,都将α设置在0.8以下。 闭散列,千万不能为满,否则在插入的时候会陷入死循环

    开散列/哈希桶:一般将载荷因子控制在1。超过1,那么链表就挂得越长,效率也就越低

    4.3. 二次探测

    线性探测的缺陷是产生哈希冲突,容易导致冲突的数据堆积在一起,这是因为线性探测是逐个的找下一个空位置.
    二次探测为了缓解这种问题(不是解决),对下一个空位置的查找进行了改进(跳跃式查找):
    POS = (H+i2)%m
    其中:i=1、2、3…
    H是发生哈希冲突的位置
    m是哈希表的大小
    在这里插入图片描述

    4.4. 插入和删除操作

    插入操作比较简单:通过哈希函数插入元素在哈希表中的位置,如果发生了哈希冲突,则使用线性探测或二次探测寻找下一个空位置插入元素。
    但是删除操作比较麻烦,采用闭散列处理哈希冲突时,不能随便删除哈希表中已有的元素,如果直接删除元素,会影响其他元素的搜索(比如原来下标为40的元素因为前面删除了一个元素下标变成了39)。
    因此线性探测采用标记的伪删除法来删除下一个元素。

    4.5. 扩容操作

    为了减少冲突,哈希表的大小最好是素数。为了能够获取每次增容后的大小,将需要用到的素数序列提前用一个数组存储起来,当我们需要增容时就从该数组当中进行获取。

    4.6. 代码实现

    namespace CloseHash//闭散列
    {
    	enum State
    	{
    		EMPTY,
    		EXIT,
    		DELETE
    	};
    	template<class K,class V>
    	struct  HashData
    	{
    		pair<K, V> _kv;
    		State _state=EMPTY;//节点的状态默认为空
    	};
    	template<class K>
    	struct  Hash
    	{
    		size_t operator()(const K& key)
    		{
    			return key;
    		}
    	};
    	template<>
    	struct  Hash<string>
    	{
    		size_t operator()(const string& s)
    		{
    			size_t value = 0;
    			for (auto ch : s)
    			{
    				value += ch;
    				value *= 131;
    			}
    			return value;
    		}
    	};
    	template<class K, class V,class HashFunc=Hash<K>>
    	struct  HashTable
    	{
    	public:
    		size_t GetNextPrime(size_t prime)
    		{
    			static const int PRIMECOUNT = 28;//给成静态,不用重复生成
    			static const size_t primeList[PRIMECOUNT] =
    			{
    				53ul, 97ul, 193ul, 389ul, 769ul,
    				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    				1610612741ul, 3221225473ul, 429496729ul
    			};
    
    			size_t i = 0;
    			for (; i < PRIMECOUNT; ++i) {
    				if (primeList[i] > prime)
    					return primeList[i];
    			}
    
    			return primeList[i];
    		}
    		bool Insert(const pair<K, V>& kv)
    		{
    			HashData<K, V>* ret = Find(kv.first);
    			if (ret) //哈希表中已经存在该键值的键值对(不允许数据冗余)
    			{
    				return false; //插入失败
    			}
    
    			//进行扩容检测
    			if (_n == 0 || (_n / _table.size() * 10 > 7))//当前个数为0或者载荷因子超过了,则进行扩容
    			{
    				//size_t newsize = _size == 0 ? 10 : 2 * _tables.size();//初始化给10,后续扩容两倍
    
    				//选取素数
    				size_t newsize = GetNextPrime(_table.size());
    
    				//扩容之后,需要重新计算元素的位置
    
    				HashTable<K, V, HashFunc> newHT;
    				newHT._table.resize(newsize);
    
    				for (auto& e : _table)
    				{
    					if (e._state == EXIT)
    						newHT.Insert(e._kv);
    				}
    				_table.swap(newHT._table);//进行交换
    			}
    	
    			HashFunc hf;
    			size_t start= hf(kv.first) % _table.size();
    			size_t index = start;
    			//探测后面的位置,线性探测或二次探测
    			size_t i = 1;
    			while (_table[index]._state == EXIT)
    			{
    				index =start+i;
    				index %= _table.size();
    				++i;
    			}
    			_table[index]._kv = kv;
    			_table[index]._state = EXIT;
    			++_n;
    			return true;
    		}
    		HashData<K,V>* Find(const K& key)
    		{
    			if (_table.size() == 0) return nullptr;
    
    			HashFunc hf;
    			size_t start = hf(key) % _table.size();
    			size_t index = start;
    			size_t i = 1;
    			while (_table[index]._state != EMPTY)
    			{
    				if (_table[index]._state== EXIT
    					&&_table[index]._kv.first == key)
    				{
    					return &_table[index];
    				}
    				index = start + i;
    				index %= _table.size();
    				++i;
    			}
    			return nullptr;
    		}
    
    		bool Erase(const K& key)
    		{
    			HashData<K, V>* ret = Find(key);
    			if (ret == nullptr)
    			{
    				return false;
    			}
    			else
    			{
    				ret->_state = DELETE;
    				return true;
    			}
    		}
    
    	private:
    		vector<HashData<K,V>> _table;
    		size_t _n = 0;
    	};
    }
    

    五、开散列(哈希桶)

    开散列又名哈希桶/开链法,首先对关键码集合采用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表串联起来,各个链表的头节点存储在哈希表中
    在这里插入图片描述

    5.1. 开散列扩容

    与闭散列不同,开散列需要负载因子达到1的时候才进行扩容。
    因为在理想的情况下每个桶下面只有一个节点。哈希桶的载荷因子控制在1,当大于1的时候就进行扩容,这样平均下来,每个桶下面只有一个节点;

    与闭散列进行比较: 看起来哈希桶之中存储节点的指针开销比较大,其实不然。闭散列的负载因子需要保证小于0.7,来确保有足够的空间降低哈希冲突的概率,而表项的空间消耗远远高于指针所占的空间效率,因此哈希桶更能节省空间。

    5.2. 代码实现

    namespace OpenHash//开散列
    {
    	template<class K,class V>
    	struct HashNode
    	{
    		HashNode<K, V>*_next;
    		pair<K, V>_kv;
    		HashNode(const pair<K, V>& kv)
    			:_next(nullptr)
    			,_kv(kv)
    		{} 
    	};
    	template<class K>
    	struct  Hash
    	{
    		size_t operator()(const K& key)
    		{
    			return key;
    		}
    	};
    	template<>
    	struct  Hash<string>
    	{
    		size_t operator()(const string& s)
    		{
    			size_t value = 0;
    			for (auto ch : s)
    			{
    				value += ch;
    				value *= 131;
    			}
    			return value;
    		}
    	};
    	template<class K, class V, class HashFunc = Hash<K>>
    	struct HashTable
    	{
    	public:
    		typedef HashNode<K, V> Node;
    		Node* Find(const K& key)
    		{
    			HashFunc hf;
    			if (_table.size() == 0) return nullptr;
    			size_t index = hf(key) % _table.size();
    			Node* cur = _table[index];
    			//在桶中进行查找
    			while (cur)
    			{
    				if (cur->_kv.first == key)
    				{
    					return cur;
    				}
    				else
    				{
    					cur = cur->_next;
    				}
    			}
    			return nullptr;
    		}
    
    		bool Insert(const pair<K, V>& kv)
    		{
    			HashFunc hf;
    			if (Find(kv.first)) return false;//列表里已经存在kv
    
    			//负载因子到1时进行增容
    			if (_n == _table.size())
    			{
    				vector<Node*>newtable;
    				size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
    				newtable.resize(newSize);
    
    				//遍历旧表中的节点,重新计算映射位置,挂到新表中
    				for (size_t i = 0; i < _table.size(); ++i)
    				{
    					if (_table[i])
    					{
    						Node* cur = _table[i];
    						while (cur)
    						{
    							//记录原来cur后面的节点
    							Node* next = cur->_next;
    							size_t index = hf(cur->_kv.first) % newtable.size();
    							//头插
    							cur->_next = _table[index];
    							_table[index] = cur;
    							cur = next;
    						}
    						_table[i] = nullptr;
    					}
    				}
    				_table.swap(newtable);
    			}
    			size_t index = hf(kv.first) % _table.size();
    			Node* newnode = new Node(kv);
    			newnode->_next = _table[index];
    			_table[index] = newnode;
    			++_n;
    		}
    		bool Erase(const K& key)
    		{
    			HashFunc hf;
    			size_t index = hf(key) % _table.size();
    			Node* prev = nullptr;
    			Node* cur = _table[index];
    			//在桶中找到对应的节点进行删除
    			while (cur)
    			{
    				if (cur->_kv.first == key)
    				{
    					//头结点的情况
    					if (_table[index] == cur)
    					{
    						_table[index] = cur->_next;
    					}
    					else
    					{
    						prev->_next = cur->_next;
    					}
    					--_n;
    					delete cur;
    					return true;
    				}
    				prev = cur;
    				cur = cur->_next;
    			}
    			//要删的节点不存在
    			return false;
    		}
    	private:
    		vector<Node*> _table;
    		size_t _n=0;//有效数据的个数
    	};
    }
    

    六、闭散列和开散列的比较

    1. 开散列处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
    2. 由于开散列中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
    3. 闭散列为减少冲突,要求负载因子α较小,故当结点规模较大时会浪费很多空间。而开散列中可取α≥1,且结点较大时,开散列中增加的指针域可忽略不计,因此节省空间;
    4. 在用开散列构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对闭散列构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。实际删除操作待表格重新整理时在进行,这种方法也被称为惰性删除。

    资料参考:
    哈希表、哈希桶的实现
    哈希表底层探索
    数据结构之(一)Hash(散列)
    哈希之开散列,闭散列

    展开全文
  • 哈希表、哈希桶(C++实现)

    千次阅读 多人点赞 2022-01-23 19:41:13
    哈希表、哈希桶哈希概念哈希函数哈希冲突解决哈希冲突闭散列线性探测闭散列的实现哈希表的结构哈希表的插入哈希表的查找哈希表的删除开散列哈希概念 哈希概念 在顺序结构和平衡树中,元素关键码与其存储位置之间没有...
  • 哈希表、哈希桶的实现

    千次阅读 多人点赞 2022-01-09 10:50:23
    文章目录哈希概念哈希冲突哈希函数哈希冲突解决闭散列开散列 哈希概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。搜索的效率取决于搜索...
  • 文章目录哈希哈希(散列)函数 哈希 哈希(散列)是一种数据结构,通过散列算法将元素值转换为散列值进行存储。使得元素存储的位置与元素本身建立起了映射关系,如果要查、改数据,就可以直接到对应的位置去,使得...
  • 哈希表+哈希桶简介及实现

    千次阅读 多人点赞 2020-08-01 22:44:47
    一文看懂哈希表,理解哈希桶
  • 开散列法对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个,各个中的元素通过一个单链表链接起来,各链表的头结点组成 一个向量,因此,向量的元素个数与可能的...
  • 我们可以先实现一个比较简单的哈希表,使用java中解决哈希冲突的方法,即哈希桶(开散列)方式实现,其中注意: 可以使用内部类方式定义节点 负载因子默认为0.75 因为我们使用的是哈希桶方式解决哈希冲突,所以在...
  • 哈希桶

    2020-05-15 23:31:14
    什么是哈希桶
  • 哈希桶的实现

    万次阅读 2017-06-20 12:32:29
    【开散列法】 开散列法又叫链地址法(开链法)。 开散列方法首先对关键码集合用某一个...称同一子集合中的关键码互为同义词,每一个子集合称为 一个。通常各个中的表项通过一个单链表链接起来,亦称为同义词子表。
  • 哈希(二)哈希桶

    千次阅读 2018-05-15 19:10:35
    哈希(二)哈希桶 概念 哈希桶又被称作开链法,开散列法。相比于闭散列法哈希桶更为灵活直观,存数据时不会浪费空间,开散列法存数据时由于避免哈希冲突,总会有百分之三十的空间浪费,当存储空间很大时将会...
  • 哈希表以及哈希冲突的解决 1.哈希表 1.1概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应关系,因此在查找一个元素的时候,必须要经过关键码的多次比较,这样查找的效率就比较低下,搜索的效率取决...
  • 哈希结构 哈希概念 常见的K-V结构,实现了元素关键码与元素值的映射关系,但没有实现元素关键值与元素存储位置的映射关系,在遍历过程中,一般的顺序表或搜索二叉树要进行关键值的多次比较,其中顺序表的时间...
  • 开散列法又叫链地址法(开链法)/哈希桶/拉链法,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储...
  • 目录概念哈希函数哈希冲突哈希冲突的解决闭散列概念哈希表闭散列的实现(采用线性探测)哈希表整体框架插入元素查找元素删除元素开散列概念哈希表开散列实现(哈希桶)整体框架插入元素查找元素删除元素字符串哈希...
  • //一个数组里存放一个(三个元素和指向下一个地址的) } HashTable1[i].link = NULL; } } int InsertHashTable(ElemType x) { int i; int index = Hash(x); for (i = 0; i ; i++) { if (HashTable1...
  • 数据结构之哈希表(包含哈希桶

    千次阅读 2018-05-15 08:20:20
    哈希表详解机器代码的实现。
  • 哈希表、哈希桶、解决哈希冲突(开散列、闭散列)。
  • 哈希表: 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放...
  • 文章目录Redis 学习笔记-哈希桶和底层数据结构1.Redis 基本数据类型2.Redis 底层数据结构类型3.Redis 基本数据类型和底层数据结构关系示意图4.key 是如何查找到哈希桶4.1 哈希表(HashTable)原理图4.2 哈希桶和数据...
  • 参考回答: hash表的实现主要包括构造哈希和处理哈希冲突两个方面: (1) 对于构造哈希来说,主要包括直接地址法、平方取中法、除留余数法...虽然链地址法并不要求哈希桶长度必须为质数, 但SGI STL仍然以质数来...
  • 哈希表与哈希冲突(手动实现哈希桶

    多人点赞 热门讨论 2022-07-11 18:19:09
    一直在说哈希,你还记得哈希冲突吗? 尝试过自己手动实现哈希桶来解决哈希冲突吗?挑战一下,你会发现源码也没那么难,嘻嘻
  • 目录unordered系列关联式容器unordered_map的文档介绍unordered_map的接口说明 unordered系列关联式容器 在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 ,即最差情况下需要比较红黑...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • ** 因为本人之前一直写的是电子笔记,对自己学会的东西作一个总结,所以基本都是文字,本来想全发成博客的形式,发现全发成博客比较花费时间,而且一直发博客...哈希就是为了摆脱,查找的瓶颈,想了一个让查找平均的...
  • 哈希表和哈希桶

    千次阅读 2018-05-24 22:31:55
    哈希表简介:  哈希表是通过关键值来访问的数据结构,也就是说他通过把关键值映射到表中的一个位置来访问记录,以加快 查找速度,这个映射关系就是哈希函数,存放数据的列表叫做散列表。         首先给...
  • 哈希桶的应用

    2022-04-04 21:36:29
    哈希桶的一个应用

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,862
精华内容 19,544
关键字:

哈希桶

友情链接: data.zip