精华内容
下载资源
问答
  • c代码实现哈希表线性探测再散列。关键字均为纯数字。查找时为单次查找,未加入循环
  • 哈希表线性探测再散列

    千次阅读 2016-10-28 22:19:41
    #include #define HashLength 23 using namespace std; //哈希函数 int HashFuc(int i,int length) ...int *HashReLineExplor(int A[], int k,int h[],int m)//关键字数组、关键字个数、哈希表哈希表长度 { f

    #include<iostream>
    #define HashLength 23
    using namespace std;
    //哈希函数
    int HashFuc(int i,int length)
    {
    	return i%length;
    }
    //线性探测再散列
    int *HashReLineExplor(int A[], int k,int h[],int m)//关键字数组、关键字个数、哈希表、哈希表长度
    {
    	for (int i = 0; i < m; i++)
    		h[i] = NULL;
    	for (int j = 0; j < k; j++)
    	{
    		int loc = HashFuc(A[j], HashLength);
    		while (h[loc])
    		{
    			loc=loc++%m;	//寻找第一个空位置
    		}
    		h[loc] = A[j];
    	}
    	return h;
    }
    
    int main()
    {
    	int Hash[25];//哈希表
    	int Key[20] = { 23, 26, 14, 22, 24, 38, 32, 120, 29, 93, 83, 21, 11, 23, 43, 123, 94, 93, 92, 91 };	//关键字
    	HashReLineExplor(Key, 20, Hash, 25);
    	for (int i = 0; i < 25; i++)
    	{
    		if (Hash[i])
    		{
    			printf("第%2d个元素是:%4d\n", i, Hash[i]);
    		}
    	}
    	return 0;
    }

    数组中元素: 23, 26, 14, 22, 24, 38, 32, 120, 29, 93, 83, 21, 11, 23, 43, 123, 94, 93, 92, 91 

    哈希表中元素:

    第 0个元素是:  23
    第 1个元素是:  24
    第 2个元素是:  93
    第 3个元素是:  26
    第 4个元素是:  23
    第 5个元素是: 120
    第 6个元素是:  29
    第 7个元素是:  94
    第 8个元素是: 123
    第 9个元素是:  32
    第10个元素是:  93
    第11个元素是:  11
    第12个元素是:  92
    第14个元素是:  14
    第15个元素是:  38
    第16个元素是:  83
    第20个元素是:  43
    第21个元素是:  21
    第22个元素是:  22
    第23个元素是:  91
    请按任意键继续. . .


    展开全文
  • 哈希表线性探测&二次探测

    千次阅读 2017-06-09 11:00:36
    在代码中实现了哈希表中任意类型都可以存放,即哈希函数要可扩展以及哈希表动态增容的功能。 贴上代码: #include #include using namespace std; template//特化 class _HashFun { public: size_t operator...

    在代码中实现了哈希表中任意类型都可以存放,即哈希函数要可扩展以及哈希表动态增容的功能。

    贴上代码:

    #include<iostream>
    #include<vector>
    using namespace std;
    
    template<class K>//特化
     class _HashFun
     {
     public:
    	 size_t operator()(K key)
    	 {
    		 return key;
    	 }
     };
    
     template<>
     class _HashFun<string>
     {
     public:
    	 size_t operator()(const char* str)
    	 {
    		 return BKDRHash(str);
    	 }
     private:
    	 static size_t BKDRHash(const char * str)
      {	
    	unsigned int seed = 131; // 31 131 1313 13131 131313	
    	unsigned int hash = 0;
    	while (*str )
    	{
    		hash = hash * seed + (*str++);
    	}
    	return (hash & 0x7FFFFFFF);
      }
     };
    
    enum State //状态标志
    {
    	EXIST,
    	EMPTY,
    	DELETE,
    };
    
    template<class K, class V>
    struct HashElem //哈希元素
    {
    	HashElem()
    		:_s(EMPTY)
    	{}
    	pair<K, V> _kv;
    	State _s;
    };
    
    template<class K, class V, class HashFunc = _HashFun<K>, bool Isline = true>
    class HashTable //哈希表
    {
    public:
    	HashTable(size_t size = 12)
    		:_size(0)
    	{
    		_table.resize(size);
    	}
    
    	bool Insert(const K& key, const V& value)
    	{
    		_CheckTable();
    		//如果表满
    		if(_size == _table.size())
    			return false;
    
            size_t hashAddr = _HashFunc(key);//找哈希地址
    		size_t H0 = hashAddr;
    		size_t i = 1;
     		while(EXIST == _table[hashAddr]._s)//冲突
    		{
    			if(key == _table[hashAddr]._kv.first)//只插入唯一值
    				return false;
    
    			if(Isline)
    			{
    				hashAddr =  HashFunc1(H0);
    			}
    			else
    			{
    				hashAddr =  HashFunc2(H0, i);
    			}
    			i++;
    
    		    //hashAddr++;//线性探测
    			//if(hashAddr == _table.size())//找到最后一个再从头开始
    			//	hashAddr = 0;
    		}
    		//插入
    		_table[hashAddr]._kv.first = key;
    		_table[hashAddr]._kv.second = value;
    		_table[hashAddr]._s = EXIST;
    		_size++;
    		return true;
    
    	}
    	pair<HashElem<K,V>*, bool> Find(const K& key)//查找值为key的元素
    	{
    		size_t hashAddr = _HashFunc(key);
    	    size_t H0 = hashAddr;
    		size_t i = 1;
    		while(EMPTY != _table[hashAddr]._s)
    		{
    			if(_table[hashAddr]._kv.first == key)
    			{
    				if(_table[hashAddr]._s == EXIST)
    					return make_pair(&_table[hashAddr], true);
    				else//DELETE
    					return make_pair((HashElem<K, V>*)NULL, false);//这里需要强转,否则编译器可能将NULL当成0
    			}
    			if(Isline)
    			{
    				hashAddr =  HashFunc1(H0);
    			}
    			else
    			{
    				hashAddr =  HashFunc2(H0, i);
    			}
    			i++;
    			//hashAddr++;//线性探测
    			//if(hashAddr == _table.size())
    			//	hashAddr = 0;
    		}
    		return make_pair((HashElem<K,V>*)NULL,false);
    	}
    
    	bool Remove(const K& key)//删除
    	{
    		pair<HashElem<K, V>*, bool> pos = Find(key);
    		if(pos.second)
    		{
    			pos.first->_s = DELETE;
    			_size--;
    			return true;
    		}
    		return false;
    	}
    
    private:
    	size_t _HashFunc(const K& key)
    	{
    		return HashFunc()(key) % 10/*_table.size()-1*/;
    	}
    
    	// 线性探测处理函数
    	size_t HashFunc1(size_t hashAddr)
    	{
    		hashAddr++;
    		if(hashAddr == _table.size())
    			hashAddr = 0;
    		return hashAddr;
    	}
    
    	// 二次探测处理函数
    	size_t HashFunc2(size_t hashAddr, size_t i)
    	{
    		if(hashAddr >= _table.size())
    			hashAddr = 0;
    		return hashAddr+2*i+1;
    	}
    
    	void Swap(HashTable<K,V>& ht)
    	{
    		_table.swap(ht._table);//两个容器交换不创建临时对象 
    		swap(_size, ht._size);
    	}
    	void _CheckTable()
    	{
    		if(_size*10 / _table.size() >= 7)
    		{
    			size_t newsize = _table.size()*2;//乘2可能会越界
    			//newsize = GetNextPrime(newsize);
    			//交换法 销毁原来的空间
    			HashTable<K, V> ht(newsize);
    			for(int idx = 0;idx <= _table.size();idx++)
    			{
    				if(_table[idx]._s == EXIST)
    					ht.Insert(_table[idx]._kv.first, _table[idx]._kv.second);
    			}
    			Swap(ht);
    		}
    	}
    
    	vector<HashElem<K, V>> _table;
    	size_t _size;//有效元素的个数
    };
    
    void FunTest()
    {
    	int a[] = {11,25,37,14,36,49,57};
    	HashTable<int, int> ht;
    	for(int idx = 0; idx <sizeof(a)/sizeof(a[0]); idx++)
    		ht.Insert(a[idx], idx);
    
    	pair<HashElem<int, int>*, bool> pos = ht.Find(25);
    	if(pos.second)
    	{
    		cout<<pos.first->_kv.first<<endl;
    	}
    	else
    	{
    		cout<<"没有找到该元素"<<endl;
    	}
    
    	ht.Remove(25);
    
    	pair<HashElem<int, int>*, bool> pos1 = ht.Find(25);
    	if(pos1.second)
    	{
    		cout<<pos1.first->_kv.first<<endl;
    	}
    	else
    	{
    		cout<<"没有找到该元素"<<endl;
    	}
    
    }


    展开全文
  • 哈希表线性探测再散列的方法详解

    万次阅读 多人点赞 2020-03-26 16:01:56
    例:设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法) 解题步骤: 1.将 ...

    哈希表线性探测再散列的方法详解
    例:设哈希表长为m=14,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法)

    解题步骤:
    (1)将关键字序列中的每一个数除以散列函数中的11并取余数。
    在这里插入图片描述
    (2)将关键字对照余数,放入哈希表中。
    在这里插入图片描述
    (3)因为在关键字序列中16排在51前,所以我们先处理关键字16的冲突,也就是先解决关键字16到底应该放在哪一个哈希表值的位置。
    (4)关键字16除以11取余数为5,哈希表值为5处已经被关键字5占用,关键字5在关键字序列中排在16的前面,所以,关键字16只能向后移动一位放在哈希表值为6处,但是此时哈希表6的位置处放的是关键字17,我们查看关键字序列可以发现,关键字16在序列中是排在17的前面,所以,可以将16放在哈希表值为6处。此时,17变为冲突的关键字。
    在这里插入图片描述
    (5)此时冲突关键字为17和51,对照关键字序列,关键字51的位置排在关键字17之前,所以我们先处理关键字51的冲突。
    (6)关键字51与关键字7冲突,查看关键字序列,关键字7排在关键字51的前面,所以关键字需向后移动一位,在哈希表值8处存储,查看哈希表,值为8处没有其他关键字占用,将关键字51放入8处。

    在这里插入图片描述
    (7)此时只有关键字17处于冲突状态。哈希表值为7、8、9、10处关键字为7、51、31、21,查看关键字序列发现关键字7、51、31、21均排在17的前面,所以关键字17只能放在此时为空的哈希表值11处。
    在这里插入图片描述

    仅仅只是为了考试,我太难了。。。。°(°¯᷄◠¯᷅°)°。

    展开全文
  • 实验 哈希表线性探测再散列

    千次阅读 2017-06-20 13:49:44
    将上面的数据利用长度为15的哈希表存储,输出存储后的哈希表。哈希函数采用key%13,用线性探测再散列解决冲突,设计并实现查找运算。 代码: #include using namespace std; const int MAXN=15; typedef struct ...

    将上面的数据利用长度为15的哈希表存储,输出存储后的哈希表。哈希函数采用key%13,用线性探测再散列解决冲突,设计并实现查找运算。

    代码:

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN=15;
    typedef struct HashList{
        int elem[MAXN],mod;
        HashList(){
            for(int i=0;i<MAXN;i++) elem[i]=-1;
            mod=13;
        }
    public:
        int Insert(int x){
            int pos=x%mod;
            while(elem[pos]!=-1) pos=(pos+1)%mod;
            elem[pos]=x;
            return pos;
        }
        void show(){
            for(int i=0;i<mod;i++)
                cout<<elem[i]<<' ';
            cout<<endl;
        }
        int Find(int x){
            int pos=x%mod;
            while(elem[pos]!=x) pos=(pos+1)%mod;
            elem[pos]=x;
            return pos;
        }
    }HashList;
    int main()
    {
        srand((unsigned long long)time(0));
        int a[10]={90 ,92 ,41 ,2 ,4 ,29 ,73 ,87 ,11 ,77};
        HashList b;
        for(int i=0;i<10;i++){
            b.Insert(a[i]);
            b.show();
        }
        cout<<a[3]<<' '<<b.Find(a[3])<<endl;
    }


    展开全文
  • //哈希表中每个元素不仅包含关键字,还有其状态信息 typedef struct Element{ Key key; State state; } Element; //哈希表,包括元素类型,有效数据大小,容量和哈希函数 typedef struct HashTable { Element *...
  • 直接看代码: #include <stdio.h> #include <stdlib.h> //宏定义相关常量 #define Max 10 #define Size 10 typedef struct Sqlist{ int *data; int length;...//哈希表 int hash (int key){
  • 2.线性探测开放寻址法  *调用哈希函数处理键得到哈希值,用值除以的长度后取余数,从而确定中的一个位置  *如果该位置非空,则探测下一个位置,到达最后一项时,折回表头。  *如果回到原来哈希位置上时还未...
  • 线性探测哈希 使用哈希表线性探测实现
  • 哈希表-线性探测法理论 线性探测法的理论我们在上一篇博客已经阐述了。 现在我们来看看线性探测法的增删查的代码思想: 哈希表的增加元素: 注意:往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然访问数组...
  • 哈希表-线性探测

    2016-11-28 11:41:27
    哈希表是一种数据结构,它可以提供快速的插入和查找操作。不论哈希表有多少数据,插入和删除(有时包括删除)只需要接近常量的时间,即O(1)的时间级。 哈希表运算非常快,在计算机程序中,如果需要在一秒钟内...
  • 哈希表——线性探测

    2018-10-13 19:04:29
     * 哈希表是根据关键码值来进行访问的数据结构  * 也就是说 他通过关键码值映射到表中的一个位置来访问记录,来加快查找的速度,  * 这个映射叫做散列函数,这个存放记录的数组叫做散列表  * 1、哈希表可以快速...
  • 哈希线性探测

    2018-12-07 17:25:00
    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数据,每组输入...
  • 二、线性探测 简单的来说就是遇到哈西冲突就查找下一个位置,看位置上是否有数据,假如有则继续查找,假如没有则将数据放入到当前位置 局限性:引发洪水式的冲突,冲突越来越多,找的越来越慢(因为找到的是一片冲突...
  • 线性探测哈希表

    2020-06-22 23:02:07
    5.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并求出等概率查找时查找成功 的 ASL(成功) (1 分),...
  • 插入删除接近常量,大o表示法最快的方式哈希表查询也快,但是底层存储结构是数组,一旦创建无法改变大小哈希表无法用来有序遍历冲突的解决方法:开放地址法(线性探测,二次探测,再哈希)和链地址法 //数据项(key...
  • 哈希表线性探测法和链地址法求查找成功与不成功的平均查找
  • 哈希表又称散列表。 哈希表存储的基本思想是:以数据表中的每个记录的关键字 k为自变量,通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个...
  • 搜索结构之哈希表线性探测法)

    万次阅读 2017-06-20 12:01:58
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 哈希表(线性存储)+ 线性探测法解决哈希冲突: 将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小...
  • 哈希表线性探测

    2019-05-10 11:22:33
    //长 #define ERROR - 1 typedef struct key { int key ; } Hashtable ; void chushi ( Hashtable hash [ ] ) { for ( int i = 0 ; i < m ; i ++ ) { hash [ i ] . key = 0 ; } } ...
  • /* / / @哈希表(线性探测法) / */ #include<stdio.h> #include<stdlib.h> #include<windows.h> #define Field -1 #define null -32768 typedef struct hashmap...
  • 根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数据,每组...
  • 哈希表的散列线性探测排序问题 题目:给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79) 哈希函数为:H(key)=key % 13, 哈希表长为m=15,设每个记录的查找概率相等。 请画出按照线性探测再散列处理冲突得到...
  • 从键盘输入各记录,以用户名为关键字建立哈希表, 哈希函数用除留取余数法构造, 采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 并计算查找长度, 哈希表保存到文件中。 测试数据: 取自己...
  • 哈希表-线性探测法/链地址法

    千次阅读 2018-10-27 13:34:48
    分别画出用线性探测法和拉链法解决冲突时构造的哈希表,并求出在等概率情况下,这两种方法的查找成功和查找不成功的平均查找长度。 2.链地址法:用链地址发解决冲突的方法时:把所有关键字为同义词的记录...
  • 哈希表——线性探测、二次探测

    千次阅读 2018-04-03 11:24:27
    搜索的效率取决于搜索过程中比较的次数。理想的搜索方法是可以不经过任何比较,一次直接从中得到要搜索的元素。如果构造一种存储结构,使元素的存储位置与它的关键码之间建立一个确定的对应函数关系Hash(),那么每...
  • 散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置的表。 哈希函数的构造方法:1)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,762
精华内容 4,304
关键字:

哈希表线性探测次数