精华内容
下载资源
问答
  • 线性探测-闭散列

    2021-05-27 11:40:31
    线性探测的实现目录:一.线性探测的概念二.线性探测原理三.功能性接口1.构造2.insert3.Capacity4.Swap5.find6.erase 目录: 一.线性探测的概念 我们在这里讲到的线性探测是解决哈希冲突中闭散列的一种方式 闭...

    在这里插入图片描述

    目录:

    一.线性探测的概念

    我们在这里讲到的线性探测是解决哈希冲突中闭散列的一种方式

    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
    ~
    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

    二.线性探测原理

    在这里插入图片描述

    闭散列解决哈希冲突的方法就是将元素后移,存放到为空的位置去.

    三.功能性接口

    1.构造

    enum STATE{		//创建一个枚举
    
    	EXIST,		//存在状态
    	DELETE,		//假删除状态
    	EMPTY		//空状态
    };
    
    template<class K, class V>
    struct HashNode{	//创建哈希结构体保存对应的KV键值对,并且将这个表的初始状态变为空
    
    	pair<K, V> _kv;
    	STATE _state = EMPTY;
    };
    
    //顺序表实现hash
    template<class K, class V>
    class HashTable{		//hash创建
    
    public:
    	typedef HashNode<K, V> Node;		//定义别名
    
    	HashTable(size_t n = 10)		//构造函数构造缺省值为10
    		:_hTable(n)
    		, _size(0)		//存在元素改为0
    	{}
    

    2.insert

    步骤:
    1.计算插入元素的哈希位置
    2.判断对应的位置是否有元素存在
    3.有元素则向后遍历找空存放
    4.无元素则直接存放

    	bool insert(const pair<K, V>& kv){
    
    		//0.判断容量是否够用
    		checkCapacity();	//调用函数
    		//1.计算哈希位置
    		int idx = kv.first%_hTable.size();
    
    		//2.判断key是否存在
    		while (_hTable[idx]._state != EMPTY){
    
    			//如果当前位置数据有效,且key相同
    			if (_hTable[idx]._state == EXIST
    				&&kv.first == _hTable[idx]._kv.first)
    			{
    				return false;
    			}
    			//继续搜索
    			++idx;
    			if (idx == _hTable.size())
    				idx = 0;
    		}
    		//插入
    		_hTable[idx]._kv = kv;
    		_hTable[idx]._state = EXIST;
    		++_size;
    
    		return true;
    	}
    

    3.Capacity

    在这里插入图片描述

    	void checkCapacity(){
    	
    		//负载因子: < 1
    		//存在的元素/容量  0.7
    		if (_hTable.size() == 0 || _size * 10 / _hTable.size() >= 7){//当内部的元素存储超过7成的时候就开辟新的表
    
    			//开新表
    			int newC = _hTable.size() == 0 ? 10 : 2 * _hTable.size();	//创建出对应的二倍的空间
    			HashTable<K, V> newHt(newC);
    
    			for (int i = 0; i < _hTable.size(); ++i){		//在for循环内部
    
    				//插入状态为exist的数据
    				if (_hTable[i]._state == EXIST)	//将内部存在的元素
    				{
    					newHt.insert(_hTable[i]._kv);	//依次在新表里面进行插入
    				}
    			}
    			Swap(newHt);	//交换新表和旧表
    		}
    	}
    

    4.Swap

    	void Swap(HashTable<K, V>& Ht){	//这里的交换就是让新的表指向对应的位置,容量进行交换
    
    		swap(_hTable, Ht._hTable);
    		swap(_size, Ht._size);
    
    	}
    

    5.find

    步骤:
    1.按照查找位置计算所在的位置
    2.如果对应的kv键值对是完全对应的,则直接输出
    3.如果没有找到,则继续向后进行遍历

    	Node* find(const K& key){
    
    		//计算对应的位置
    		int idx = key%_hTable.size();	//先找出所在元素在哈希表中的位置
    		while (_hTable[idx]._state != EMPTY){		//判断对应的位置是否有元素的存在
    
    			if (_hTable[idx]._state == EXIST
    				&& key == _hTable[idx]._kv.first)	//如果元素存在且对应的键值相互对应
    			{
    				return &_hTable[idx];	//则找到,直接输出
    			}
    			++idx;	//没找到则向后遍历
    			if (idx == _hTable.size())	
    			//如果遍历到最后一个位置没有找到,则变为0从第一个重新开始查找
    			{
    				idx = 0;
    			}
    		}
    		return nullptr;	//实在没有找到则直接返回空
    	}
    

    6.erase

    步骤:
    1.找到对应的元素进行删除
    2.注意这里的删除是假删除,元素还存在,只不过将其置为DELETE状态
    3.这里的假删除是为了在插入的时候可以正常的插入.

    	bool erase(const K& key){
    
    		Node* node = find(key);
    		if (node){
    
    			//假删除
    			--_size;
    			node->_state = DELETE;
    			return true;
    		}
    		return false;
    	}
    
    
    private:
    	vector<Node> _hTable;
    	size_t _size;	//有效元素的个数
    };
    

    这就是对于线性探测的实现,主要对于它产生哈希冲突的时候是如何解决的理解.

    展开全文
  • 线性探测哈希 使用哈希表的线性探测实现
  • Go 中的线性探测哈希表 这是用于线性探测哈希表的模板。 因为这是一个探测哈希表,所以只能插入或修改条目(即不能删除)。 并且必须有一个无效的密钥__KEY_NIL用于标记未使用的桶。 优点(相对于 Go 自己的地图类型...
  • c代码实现哈希表线性探测再散列。关键字均为纯数字。查找时为单次查找,未加入循环
  • 线性探测哈希表

    2020-06-22 23:02:07
    5.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并求出等概率查找时查找成功 的 ASL(成功) (1 分),...

    5.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并求出等概率查找时查找成功 的 ASL(成功) (1 分),与查找不成功的 ASL(不成功) (1 分)

    线性探测: H(Key)=Key%11 余数为key所在的位置,如果改位置有值,那么填入下一个位置

    成功的asl:每一个key填入哈希表所需要查询的次数的次数之和的平均

    失败的asl:每一个key与下一个空位的距离之和的平均

    展开全文
  • 内图 使用开放寻址和线性探测的整数 HashMap
  • 线性探测法的查找函数题目答案思路 题目 答案 Position Find( HashTable H, ElementType Key ) { int i,flag=0; i=Hash(Key,H->TableSize); while(H->Cells[i].Info!=Empty&&H->Cells[i]....

    线性探测法的查找函数

    题目

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    答案

    Position Find( HashTable H, ElementType Key )
    {
    	int i,flag=0;
    	i=Hash(Key,H->TableSize);
    	while(H->Cells[i].Info!=Empty&&H->Cells[i].Data!=Key)
    	{
    		if(i==H->TableSize&&flag==0)
    		{
    			i=0;
    			flag=1;
    		}
    		else if(i==H->TableSize) return ERROR;
    		else i++;
    	}
    	return i;
    }
    

    思路

    在通过Hash函数获取Key的第一位置后,在从这个位置遍历Cell数组,如果第一遍没找到,flag变量赋值1,再给它一次机会(因为它有可能是从中间向后遍历,前面的还没遍历),找到了就返回对应的位置,否则返回ERROR

    展开全文
  • JavaScript-DataStructures HashTable 的 JavaScript 实现(线性探测、二次探测、双哈希)
  • 开放寻址——线性探测 分离链接散列算法还有一个亟待解决的缺点:需要指针,由于给新单元分配地址需要时间,这就导致了速度减慢,所以不太好。还有,因为链表是次第关联的结构,实现算法的代码自身的复杂程度和出错...

    开放寻址——线性探测

    https://www.cnblogs.com/hongshijie/p/9419387.html
    分离链接散列算法还有一个亟待解决的缺点:需要指针,由于给新单元分配地址需要时间,这就导致了速度减慢,所以不太好。还有,因为链表是次第关联的结构,实现算法的代码自身的复杂程度和出错概率会大大增加。而只要采用这种策略,就很难保证每组冲突的词条在空间上能够彼此毗邻,因为动态分配的节点在内存里不一定是连续的,这样一来会导致一个致命缺陷:对于稍大规模的词条集合,查找中将做大量的I/O操作,无法利用系统预先缓存,导致效率低下。

    因此或许我们应该放弃这种策略,并反其道而行之,仅仅依靠基本的散列表结构,就地排解冲突反而是更好的选择。也就是采用所谓的开放定址策略,它的特点在于:散列表所占用的空间在物理上始终是地址连续的一块,相应的所有的冲突都在这块连续空间中加以排解。而无需向分离链接那样申请额外的空间。对!所有的散列以及冲突排解都在这样一块封闭的空间内完成。

    在这里插入图片描述

    因此相应地,这种策略也可以称作为闭散列。如果有冲突发生,就要尝试选择另外的单元,直到找到一个可供存放的空单元。具体存放在哪个单元,是有不同优先级的,优先级最高的是他原本归属的那个单元。从这个单元往后,都按照某种优先级规则排成一个序列,而在查找的时候也是按着这个序列行进,每个词条对应的这个序列被称为探测序列or查找链。

    抽象来说,就是我们遇到冲突后,会相继尝试h0(x),h1(x),h2(x)这些单元,其中hi(x)= ( Hash( x ) + F ( I ) ) % TableSize,并且约定F(0)=0,F(x)是解决冲突的方法,就是刚才说的那个“优先级规则”。因为所有的数据都要放在这块空间,所以开放定址所需要的表规模比分离链接要大。通常而言开放定址法的装填因子lambda应该低于0.5。而根据对不同F(x)的选择,学界划分出三种常用的探测序列:线性探测法、平方探测法、双散列

    1.线性探测法

    在线性探测法中,函数F是关于i的线性函数,典型的情形是F(i)=i。这相当于逐个探测每个单元(必要时可以绕回)以查找出一个空单元。下面显示了将{89,18,49,58,69}插入到一个散列表中的情况(竖着看),使用了和之前一样的散列函数hash(x)=x%size,他们有冲突怎么办?用F(i)=i这个方法,每次从i=0开始尝试,那么根据hi(x)= ( Hash( x ) + F ( I ) ) % TableSize就可以计算出各自不相冲突的地址了。完美!(暂时的)

    在这里插入图片描述

    我们脑内单步调试一下:第一个冲突在49产生:(49%10+0)%10=9,被89占了,那接着往后试,i=1,(49%10+1)%10=0,空的,放入这个空闲地址,这个地址是开放的。58依次和18,89,49产生冲突,试选三次后才找到一个空单元。对69的冲突也如此解决,一旦冲突,试探紧邻其后的单元,直至找到空单元or抵达散列表末尾。线性探测序列0->1->2->3在物理上保持连贯性的,具有局部性,这样一来系统的缓存作用将得到充分发挥,而对于大规模的数据集,这样一来更是可以减少I/O的次数。只要表足够大,总能找到一个空闲单元,但是这太费时间了。更糟的是——就算一开始空闲区域多,经过多次排解冲突后,数据所占据的单元也会开始形成一些区块,聚集在一起,被称为一次聚集(primary clustering),但在前面动机篇里说过,散列函数的初衷是避免数据扎堆,所以后面必须改进。

    那么总体看来散列到区块的任何关键字都需要多次试选单元才能解决冲突,然后被放到对应的那个区块里。下面做一个总结

    优点:

    无需附加空间(指针、链表、溢出区)
    探测序列具有局部性,可以利用系统缓存,减少IO
    缺点:

    耗费时间>O(1)
    冲突增多——以往的冲突会导致后续的连环冲突,发生惨烈的车祸
    在这里插入图片描述

    光看这个图可能没什么感觉,举个例子吧,这样感触更深。我们开一个size=7的散列表,也保证了size是素数。把{0,1,2,3,7},就按这个顺序依次插入。前四个数都没问题,依次插入没有冲突。

    在这里插入图片描述

    但是为了插入7,我们先试探0发现非空,往后走,依次试探1,2,3都非空,直到4可以放进去。
    在这里插入图片描述

    在这个散列表的生存期里只有1个发生冲突。看似很棒对吧,再来看另一插入次序:{7,0,1,2,3}。

    在这里插入图片描述

    插入7没问题,但插入0的时候就有冲突了,实际上自此之后每一个数插入都会遇到冲突,前后对比可以看出,第二种插入顺序发生的很多冲突本来是可以避免的。这个时候想必我们改进这种策略的意愿就十分迫切了。
    在这里插入图片描述

    要支持词条的删除则需要格外的小心,现在我们来做一探讨。按照线性探测的规则,先后插入彼此冲突的一组词条都将存放在同一个查找序列中,而更确切的讲:它们应该按照逻辑次序构成整个查找链的一个前缀,其中不得有任何的空桶缝隙。因此词条的删除操作需要做额外的一些处理,如果我们不做一些事先准备,直接将词条删除(就类似对于链表,删除节点的时候不做链条调整,而直接free那个单元,那不直接凉了),就会造成查找链断裂,后续词条丢失——明明存在但访问不到。

    对于这种连续空间的单元删除,一个直观的构想是:将后续词条悉数取出,再重新插入。但这太特么慢了,时间复杂度爆炸。其实对于这个问题有一种典型的处理手法:lazy delete,仅做一个删除标记,比如里面预留一个del变量,设置为TRUE。

    在这里插入图片描述

    那么在日后查找中,遇到他之后就应该越过继续往后查找而不是在此返回。在插入时遇到,就把它视作一个空单元,数据覆盖即可。应该说针对开放定址策略,懒惰删除不仅是“不得已而为之”的方法,甚至可以说是针对这种情况的最优方法。因为毕竟在开放定址策略中,每一个桶单元都同时属于多个查找链

    开放寻址散列的分析
    定理11.6 :
    一个装载因子a=n/m<1的开放寻址散列表,在一次不成功的查找中,期望的探查数之多为1/(1-a).假设散列是均匀的。
    推论11.7
    平均情况,向一个装载因子为a的开放寻址散列表中插入一个元素时,至多需要做1/(1-a)次探查。假设采用的是均匀散列。
    定理11.8
    给定一个装载因子为a<1的开放寻址散列表,一次成功查找中的期望探查数之多为(1/a)ln(1/(1-a)).

    #include "iostream"
    #include "math.h"
    #define Null -1
    #define DELETED -2
    using namespace std;
    
    //散列函数(全域散列在“全域散列解决哈希冲突中已讲”)
    int Hash_div(int val, int m)//除法求余。val值,m为槽的个数(是一个不为2的幂的质数)
    {
    	return val % m;
    }
    
    int Hash_multi(int val, int m)//乘法散列。m一般为2的某次幂
    {
    	double A = (sqrt(5) - 1) / 2;
    	return ((val*A - int(val*A)) * m);
    }
    
    //开放寻址方法:线性探查、二次探查、双重探查
    int Line_Prob(int val, int m, int i) //m为槽的个数(是一个不为2的幂的质数),m越大查找次数就越少
    {
    	return (Hash_div(val, m) + i) % m;
    }
    
    int Twice_Prob(int val, int m,int i)
    {
    	int c1 = 1, c2 = 3;
    	return (Hash_div(val, m) + c1 * i + c2 * i*i) % m; //其中常数c1,c2,m的值的选择是受限制的
    }
    int Double_Probe(int val, int m, int i)
    {
    	return (Hash_div(val, m) + i * (1 + Hash_div(val, m-1))) % m; //其中m为质数,还可以选择m为2的幂,并设置一个总产生奇数的hash_div2
    }
    int hash_insert1(int T[], int m, int k)
    {
    	int i = 0;
    	do
    	{
    		int j = Line_Prob(k, m, i);//这里可以替换成二次,双重探查。插入,查找,删除函数同时被替换
    		if (T[j] == Null || T[j] == DELETED)
    		{
    			T[j] = k;
    			return j;
    		}
    		else i++;
    	} while (i != m);
    	cerr << "hash table overflow" << endl;
    }
    int hash_search(int T[], int m, int k)
    {
    	int i = 0, j = 0;
    	do
    	{
    		j = Line_Prob(k, m, i);//这里可以替换成二次,双重探查。插入,查找,删除函数同时被替换
    		if (T[j] == k)
    		{
    			return j;
    		}
    		else i++;
    	} while (T[j] != Null || i != m);
    	return Null;
    }
    void hash_delete(int T[], int m, int k)
    {
    	int j = hash_search(T, m, k);//首先先找到该关键字k
    	if (j != Null)
    	{
    		T[j] = DELETED;//如果找到了,那么设置其为空。
    		cout << "删除成功!" << endl;
    	}
    	else cout << "待删除的数据不在表中!" << endl;
    }
    void Display(int T[],int m)
    {
    
    	cout << "散列表信息显示:"  ;
    	for (int i = 0; i < m; i++)
    	{
    		cout << T[i] << " ";
    	}
    	cout << endl;
    }
    void main()
    {
    	int a[9] = { 10,22,31,4,15,28,17,88,59 };
    	int T[19] = { 0 };
    	for (int i = 0; i<19; i++)
    	{
    		T[i] = Null;
    	}
    	for (int i = 0; i<9; i++)
    	{
    		hash_insert1(T, 19, a[i]);
    	}
    	Display(T,19);
    	hash_delete(T, 19, 10);
    	Display(T, 19);
    	system("pause");
    }
    
    
    
    
    
    
    
    展开全文
  • 线性探测再散列

    万次阅读 热门讨论 2019-10-07 09:57:11
    处理冲突的方法: 开放寻址法:Hi=(H(key) + di) MOD m, i=1,2,…, k(k),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法: 1.di=1,2,3,…, m-1,称线性探测再散列; 2.di=1^2, -1^2, 2^2,-2^...
  • 先上结论:线性探测再散列就是王道P282(不同版本页码不一致)中的线性探测法。 对于2019年真题中线性探测再散列,严的紫书在P257中明确写到了线性探测再散列的解释。即如下图: 而王道P282中线性探测法如下图:...
  • 哈希表线性探测再散列的方法详解

    万次阅读 多人点赞 2020-03-26 16:01:56
    线性探测再散列的方法详解 例:设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法) 解题步骤...
  • 用于解决冲突的两种算法 线性探测再散列 平方探测再散列(二次探测再散列)参考这个blog,写的很好。 http://blog.csdn.net/qq_27093465/article/details/52348366
  • 散列 在c中使用数组进行散列(线性探测
  • 哈希表(线性存储)+ 线性探测法解决哈希冲突: 将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小...
  • 虽然上文有提到怎么解释的开放地址法处理hash冲突...什么叫线性探测再散列; 什么叫平方探测再散列(二次探测再散列); 老师的ppt吧。 给个原始数据如上图。 下面详细解析。 上面的是线性探测再散列。这个简单。
  • 线性探测法hash

    2016-12-18 19:01:58
    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数
  • 线性探测法的查找函数 (20 分)

    千次阅读 2018-12-07 14:57:18
    6-22 线性探测法的查找函数 (20 分) 试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /*...
  • 从键盘输入各记录,以用户名为关键字建立哈希表, 哈希函数用除留取余数法构造, 采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 并计算查找长度, 哈希表保存到文件中。 测试数据: 取自己...
  • 哈希之线性探测

    2018-12-07 17:25:00
    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数据,每组输入...
  • 散列函数线性探测法处理冲突

    千次阅读 2018-07-07 01:34:39
    散列函数线性探测法处理冲突: #include &amp;amp;lt;iostream&amp;amp;gt; using namespace std; typedef int KeyType; typedef int InfoType; struct done { KeyType key; InfoType otherinfo; }HT[20...
  • 建立hash表 已知有一数据表L(47,2, 23,78,31,18, 42, 7,56, 91,38),用除留余数开放定址法创建一张哈希表,采用线性探测解决冲突。请写出对应的建立哈希表算法
  • 1.//平方探测法没有线性探测法 找的仔细,两者相比:线性探测能找到的,平方探测不一定能找到; 2.//线性探测每次d加1,平方探测是j++ d = j*j ; 仔细一看应该可以看出两者探测精度,明显线性探测的精度更高,比平方...
  • 哈希表线性探测再散列

    千次阅读 2016-10-28 22:19:41
    #include #define HashLength 23 using namespace std; //哈希函数 ...//线性探测再散列 int *HashReLineExplor(int A[], int k,int h[],int m)//关键字数组、关键字个数、哈希表、哈希表长度 { f
  • 已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0..6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为___分析:利用...
  • Hash解决冲突之线性探测

    千次阅读 2016-08-18 20:35:23
    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 输入 连续输入多组数据,每组输入数据第...
  • 链式地址&线性探测的平均查找长度

    千次阅读 多人点赞 2020-08-15 21:59:15
    文章目录1 链式地址法2 线性探测法 1 链式地址法 题目:已知关键字序列为:(75,33,52,41,12,88,66,27),哈希表长为10,哈希函数为:H(k)=kmod7,解决冲突用线性探测再散列法,要求构造哈希表,求出...
  • 问题 A: DS哈希查找—线性探测再散列 时间限制: 1 Sec 内存限制: 128 MB 提交: 454 解决: 303 [提交][状态][讨论版] 题目描述 定义哈希函数为H(key) = key%11,输入表长(大于、等于11)。输入关键字集合,用线性...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,494
精华内容 12,197
关键字:

线性探测