精华内容
下载资源
问答
  • 这是数据结构课程作业,用二次探测再散列法解决冲突建立哈希表并查找 从键盘读入 待查找 的权重数值,以除留余数法为哈希函数,二次探测再散列法解决冲突建立哈希表,基于哈希算法从数组中查找相应的记录,计算相应...
  • 二次探测

    万次阅读 多人点赞 2020-05-04 16:02:36
    设哈希表长为11,哈希函数为Hash (key)=...二次探测法:采用开放定址法处理冲突中的二次探测再散列(也即是题目中的二元探测法),则哈希函数变为Hash(key) = (Hash(key) + d) % 11,其中d = 1^2, -1^2, 2^2, -2^2...

    设哈希表长为11,哈希函数为Hash (key)=key%11。存在关键码{43,7,29,22,16,92,44,8,19},采用二次探测法处理冲突,建立的hash表为( )
    二次探测法:采用开放定址法处理冲突中的二次探测再散列(也即是题目中的二元探测法),则哈希函数变为Hash(key) = (Hash(key) + d) % 11,其中d = 1^2, -1^2, 2^2, -2^2, 3^2,……,则开始计算。

    对于43,代入公式为Hash(43) = 43 % 11 = 10, 则地址为10;

    对于7,代入公式为Hash(7) = 7 % 11 = 7,则地址为7;

    对于29,代入公式为Hash(29) = 29 % 11 = 7, 与7冲突,则采用二次探测进行消除冲突, 继续(7 + 1) % 11 = 8,没有冲突,则地址为8;

    对于22,代入公式Hash(22) = 22 % 11 = 0, 则地址为0;

    对于16,代入公式Hash(16) = 16 % 11 = 5, 则地址为5;

    对于92,代入公式Hash(92) = 92 % 11 = 4,则地址为4;

    对于44,代入公式Hash(44) = 44 % 11 = 0, 与22的地址冲突,则继续(0 + 1) % 11 = 1,没有冲突,则地址为1;

    对于8, 代入公式Hash(8) = 8 % 11 = 8, 与29有冲突,则继续(8 + 1) % 11 = 9, 没有冲突,则地址为9;

    对于19,代入公式Hash(19) = 19 % 11 = 8. 与 29有冲突,则继续(8 + 1) * 11 = 9, 与8有冲突,继续(8 - 1) % 11 = 7, 与7有冲突,则继续(8 + 4) % 11 = 1, 与44有冲突,则继续(8 - 4) % 11 = 4, 与92有冲突,则继续(8 + 9) % 11 = 6, 没有冲突,则地址为6.

    所以最后得到的Hash表为下图所示:
    在这里插入图片描述

    展开全文
  • 二次探测法就是解决这个问题的,二次探测法的解决冲突的方案是 f i ( k e y ) = ( f i − 1 ( k e y ) + d i )   m o d   m ( d i = 1 2 , − 1 2 , 2 2 , − 2 2 . . q 2 , − q 2 , q ≤ m / 2 ) f_i(key)=(f_...

    关键字集合{12,67,56,16,25,37,22,29,15,47,48,34}。

    开放定址法

    开放定址法公式 f i ( k e y ) = ( f i − 1 ( k e y ) + d i )   m o d   m   ( d i = 1 , 2 , 3 ) f_i(key)=(f_{i-1}(key)+d_i)\space mod\space m\space (d_i=1,2,3) fi(key)=(fi1(key)+di) mod m (di=1,2,3)

    在这个例子中,我们取 d i = 1 , m = 12 d_i=1,m=12 di=1,m=12所以我们遇到冲突的解决方案是
    f i ( k e y ) = ( f i − 1 ( k e y ) + 1 )   m o d   12 f_i(key)=(f_{i-1}(key)+1)\space mod\space 12 fi(key)=(fi1(key)+1) mod 12

    散列函数f(key)=key mod 12。

    计算前5个数

    keymf(key)
    12120
    67127
    56128
    16124
    25121

    前5个都是没有冲突的,直接存入,如下表。

    下标01234567891011
    关键字1225166756

    key=37时,f(37)=37 mod 12 =1,与25冲突,这时候应用上面的公式
    f(37)=(f(37) +1)+mod 12=2;
    此时2是空闲的,所以把37存入2中。

    下标01234567891011
    关键字122537166756

    接下来的22,29,15,47都是没有冲突的,直接存入

    下标01234567891011
    关键字1225371516296756 2247

    接下来是48
    f(48)=48 mod 12=0;冲突
    f(48)=(0+1) mod 12=1;冲突

    f(48)=(5+1) mod 12=6;没有冲突,填入。

    下标01234567891011
    关键字1225371516294867562247

    接下来是34
    f(34)=34 mod 12=10;冲突

    最后的34经过11次冲突之后填入下标为9的空格中

    下标01234567891011
    关键字122537151629486756342247

    普通开放定址发代码:

    #include <iostream>
    #include <cstdlib>
    #define HASHSIZE 12/*散列表的大小*/
    #define NULLKEY -1/*空白标志*/
    
    using namespace std;
    typedef struct
    {
    	int *elem;
    	int count;
    }HashTable;
    
    int m = 12; 
    
    bool InitHashTable(HashTable *H)/*初始化*/
    {
    	H->elem = (int*)malloc(HASHSIZE * sizeof(int));
    	for (int i = 0; i < HASHSIZE; i++) H->elem[i] = NULLKEY;
    	return true;
    }
    
    int Hash(int key)/*哈希函数f(key)=key mod m,这里mod取12*/
    {
    	return key % m;
    }
    
    void InsertHash(HashTable *H, int key)/*开放定址法*/
    {
    	int addr = Hash(key);/*计算哈希值*/
    	while (H->elem[addr] != NULLKEY) addr = (addr + 1) % m;/*如果该地址已被占用,则地址加一继续寻找*/
    	H->elem[addr] = key;/*找到空闲地址,插入*/
    }
    
    bool SearchHash(HashTable *H, int key, int &addr)/*查找*/
    {
    	addr = Hash(key);
    	while (H->elem[addr] != key)
    	{
    		addr = (addr + 1) % m;
    		if (H->elem[addr] == NULLKEY || addr == Hash(key)) return false;/*如果查找到空闲地址或者又回到了原地,则说明该表中没有该关键字*/
    	}
    	return true;
    }
    
    int main()
    {
    	HashTable *test=new HashTable;
    	InitHashTable(test);
    
    	int a[12] = {12,67,56,16,25,37,22,29,15,47,48,34};/*要插入的key*/
    	for (int i = 0; i < 12;i++) InsertHash(test,a[i]);
    
    	int addr;
    	SearchHash(test,48, addr);/*查找48所在的地址*/
    	cout <<"48的地址是:" <<addr<<endl;
    
    	cout << "散列表:" << endl;
    	for (int i = 0; i < HASHSIZE; i++) cout << test->elem[i]<<" ";/*查找哈希数组中各个元素*/
    
    	system("pause");
    }
    

    让我们来看下程序输出的结果

    在这里插入图片描述
    和理论计算的一样。


    二次探测法

    在上面的例子中,我们发现48和34要经过很多次冲突才能找到合适的位置,特别是最后一个34,最后的一个空位就在第一次哈希值前面,但是由于我们解决冲突的方案是
    f i ( k e y ) = ( f i − 1 ( k e y ) + 1 )   m o d   12 f_i(key)=(f_{i-1}(key)+1)\space mod\space 12 fi(key)=(fi1(key)+1) mod 12
    使得我们只能向后寻找空闲的位置,而不能向前,那我们能不能改进一下呢?

    二次探测法就是解决这个问题的,二次探测法的解决冲突的方案是
    f i ( k e y ) = ( f i − 1 ( k e y ) + d i )   m o d   m ( d i = 1 2 , − 1 2 , 2 2 , − 2 2 . . q 2 , − q 2 , q ≤ m / 2 ) f_i(key)=(f_{i-1}(key)+d_i)\space mod\space m(d_i=1^2,-1^2,2^2,-2^2..q^2,-q^2,q\leq m/2) fi(key)=(fi1(key)+di) mod m(di=12,12,22,22..q2,q2,qm/2)
    也就是我们遇到冲突时,先往右探测1个单位,如果不行,就往左探测一个单位,如果还不行,就往右探测 2 2 2^2 22个单位,如果还不行,就往左探测 2 2 2^2 22个单位…

    二次探测法代码:

    #include <iostream>
    #include <cstdlib>
    #include <math.h>
    #define HASHSIZE 12/*散列表的大小*/
    #define NULLKEY -1/*空白标志*/
    
    using namespace std;
    typedef struct
    {
    	int *elem;
    	int count;
    }HashTable;
    
    int m = 12; 
    
    bool InitHashTable(HashTable *H)/*初始化*/
    {
    	H->elem = (int*)malloc(HASHSIZE * sizeof(int));
    	for (int i = 0; i < HASHSIZE; i++) H->elem[i] = NULLKEY;
    	return true;
    }
    
    int Hash(int key)/*哈希函数f(key)=key mod m,这里mod取12*/
    {
    	return key % m;
    }
    
    void InsertHash(HashTable *H, int key)/*开放定址法*/
    {
    	int count = 0;/*记录冲突次数,以便调整左右探测方向,冲突次数为偶数时向右探测,为奇数时向左探测*/
    	int addr = Hash(key);/*计算哈希值*/
    	int temp = addr;
    	while (H->elem[temp] != NULLKEY)
    	{
    		if(count%2==0)
    		    temp = (addr + (int)pow((1 + count / 2),2)) % m;/*向右探测*/
    		else
    			temp = (addr - (int)pow((1 + count / 2), 2)) % m;/*向左探测*/
    		count++;
    	}
    	H->elem[temp] = key;/*找到空闲地址,插入*/
    }
    
    bool SearchHash(HashTable *H, int key, int &addr)/*查找*/
    {
    	int count = 0;
    	addr = Hash(key);
    	int temp = addr;
    	while (H->elem[temp] != key)
    	{
    		if (count % 2 == 0)
    			temp = (addr + (int)pow((1 + count / 2), 2)) % m;/*如果该地址已被占用,则地址加一继续寻找*/
    		else
    			temp = (addr - (int)pow((1 + count / 2), 2)) % m;
    		if (H->elem[temp] == NULLKEY || temp == Hash(key)) return false;/*如果查找到空闲地址或者又回到了原地,则说明该表中没有该关键字*/
    		count++;
    	}
    	addr = temp;
    	return true;
    }
    
    int main()
    {
    	HashTable *test=new HashTable;
    	InitHashTable(test);
    
    	int a[12] = {12,67,56,16,25,37,22,29,15,47,48,34};/*要插入的key*/
    	for (int i = 0; i < 12;i++) InsertHash(test,a[i]);
    
    	int addr;
    	SearchHash(test,48, addr);/*查找48所在的地址*/
    	cout <<"48的地址是:" <<addr<<endl;
    
    	cout << "散列表:" << endl;
    	for (int i = 0; i < HASHSIZE; i++) cout << test->elem[i]<<" ";/*查找哈希数组中各个元素*/
    
    	system("pause");
    }
    

    在这里插入图片描述
    二次探测法构造的散列表和开放定址法有些不一样,至于二次探测法的散列表结果为什么是这样,可以参考上面开放地址法的过程,这里不再详细写二次探测法散列表的构造过程。

    下面是两个散列表的对比

    方法下标01234567891011
    开放定址法关键字122537151629486756342247
    二次探测法关键字122537151629346756482247

    参考书籍:《大话数据结构》

    展开全文
  • 构造哈希表以及二次探测

    千次阅读 2018-09-16 19:53:39
    构造哈希表(散列表)以及二次探测法 今天做笔试题时,遇到一道构造哈希表的题,hash函数是 k%11 ,然后一个数组记不清了,然后就是问二次探测法进行,问下面那个是正确,懵逼啊,没做过,不知道,乱选直接下...

    今天做笔试题时,遇到一道构造哈希表的题,hash函数是 k%11 ,然后一个数组记不清了,然后就是问二次探测法进行,问下面那个是正确,懵逼啊,没做过,不知道,乱选直接下一题,于是有这个博客,赶紧学习一波。

    网上查询了一下。


    构造哈希表的几种方法

    常用方法是直接定址法除留余数法

    • 直接定址法(取关键字的某个线性函数为哈希地址)

    类似于这样的式子

    f(key) = a × key + b

    • 除留余数法(取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址)

    对于散列表长为m的散列函数公式为:

    f( key ) = key mod p ( p ≤ m )

    mod是取模(求余数)的意思。事实上,这方法不仅可以对关键字直接取模,也可在折叠、平方取中后再取模。

    • 平方取中法

    • 折叠法

    • 随机数法

    • 数学分析法


    哈希冲突(碰撞)以及处理

    哈希冲突:既然有哈希函数Hash(key),在有限的空间里,肯定会产生相同的的值(哈希地址),我们称这种情况为哈希冲突(碰撞)。任意的散列函数都不能避免产生冲突。

    1. 开发定址法

    所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入。

    • 线性探测法

    fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)

    用开放定址法解决冲突的做法是:当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。

    ep:我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。 我们用散列函数f(key) = key mod 12。

    当计算前S个数{12,67,56,16,25}时,都是没有冲突的散列地址,直接存入:

    这里写图片描述

    计算key = 37时,发现f(37) = 1,此时就与25所在的位置冲突。

    于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入为2的下标位置。

    这里写图片描述

    接下来22,29,15,47都没有冲突,正常的存入:

    这里写图片描述

    到了 key=48,我们计算得到f(48) = 0,与12所在的0位置冲突了,不要紧,我们f(48) = (f(48)+1) mod 12 = 1,此时又与25所在的位置冲突。于是f(48) = (f(48)+2) mod 12=2,还是冲突……一直到 f(48) = (f(48)+6) mod 12 = 6时,存入该位置:

    这里写图片描述

    我们把这种解决冲突的开放定址法称为线性探测法。

    • 二次探测法

    考虑深一步,如果发生这样的情况,当最后一个key=34,f(key)=10,与22所在的位置冲突,可是22后面没有空位置了,反而它的前面有一个空位置,尽管可以 不断地求余数后得到结果,但效率很差。

    因此我们可以改进di = 12, -12, 22, -22,……, q2, -q2 (q <= m/2),这样就等于是可以双向寻找到可能的空位置。

    对于34来说,我 们取di即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在 某一块区域。我们称这种方法为二次探测法。

    f(key) = (f(key)+di) MOD m (di = 1^2, -1^2, 2^2, -2^2,……, q^2, -q^2, q <= m/2)

    注:1^2 表示是 1的平方。

    2. 链地址法

    前面我们谈到了散列冲突处理的开放定址法,它的思路就是一旦发生了冲突,就去寻找下一个空的散列地址。那么,有冲突就非要换地方呢,我们直接就在原地处理行不行呢?

    答案是可以的,就是链地址法,就好比Java里的HashMap的数据结构一样。

    这里写图片描述

    关于HashMap源码分析 ——> https://blog.csdn.net/Stu_zkl/article/details/82714325
    好了,就写到这了。

    展开全文
  • 二次探测法建立hash表

    千次阅读 2019-09-14 16:07:43
    存在关键码{43,7,29,22,16,92,44,8,19},采用二次探测法处理冲突,建立hash表。 由于哈希表长为11,则序号为0~10. Hash(43)=43%11=10, 43地址为10 Hash(7)=7%11=7, 7地址为7 Hash(29)=29%11=8, 29地址为8 ...

    假设哈希表长度为n,哈希函数为Hash(key)=key%n, key为关键码。
    当Hash(key)相等时,则使用Hash(key) = (Hash(key) + d) % n,d为:1^2、-(1 ^2)、2 ^2、-(2 ^2)、3 ^2、-(3 ^2)…
    例子:
    设哈希表长为11,哈希函数为Hash (key)=key%11。存在关键码{43,7,29,22,16,92,44,8,19},采用二次探测法处理冲突,建立hash表。
    由于哈希表长为11,则序号为0~10.
    Hash(43)=43%11=10, 43地址为10
    Hash(7)=7%11=7, 7地址为7
    Hash(29)=29%11=8,29地址为8
    Hash(22)=22%11=0,22地址为0
    Hash(16)=16%11=5,16地址为5
    Hash(92)=92%11=4,92地址为4
    Hash(44)=44%11=0,由于地址0已存在22,所以Hash(44)=(0+1 ^2)%11=1,44地址为1
    Hash(8)=8%11=8,由于地址8已存在29,所以Hash(8)=(8+1 ^2)%11=9,8地址为9
    Hash(19)=19%11=8,由于地址8已存在29,所以Hash(19)=(8+1 ^2)%11=9,由于地址9已存在8,所以Hash(19)=(8-1 ^2)%11=7,由于地址7已存在7,所以Hash(19)=(8+2 ^2)%11=1,由于地址1已存在44,所以Hash(19)=(8-2 ^2)%11=4,由于地址4存在92,所以Hash(19)=(8+3 ^2)%11=6,19地址为6
    在这里插入图片描述

    展开全文
  • 输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。 输入 测试次数t 每组测试数据格式如下: 哈希表长m、关键字个数n n个关键字 查找次数k k个待查关键字 输出 对每组测试...
  • 哈希表线性探测&二次探测

    千次阅读 2017-06-09 11:00:36
    // 二次探测处理函数 size_t HashFunc2(size_t hashAddr, size_t i) { if(hashAddr >= _table.size()) hashAddr = 0; return hashAddr+2*i+1; } void Swap(HashTable,V>& ht) { _table.swap(ht._...
  • 2.di=1^2, -1^2, 2^2,-2^2, 3^2, …, ±(k)^2,(k)称二次探测再散列; 3.di=伪随机数序列,称伪随机探测再散列。 再散列法:Hi=RHi(key), i=1,2,…,k. RHi均是不同的散列函数,即在同义词产生地址冲突时计算另...
  • 二次探测发解决闭散列表中的冲突问题,可供参考
  • 哈希表——线性探测、二次探测

    千次阅读 2018-04-03 11:24:27
    理想的搜索方法是可以不经过任何比较,一直接从表中得到要搜索的元素。如果构造一种存储结构,使元素的存储位置与它的关键码之间建立一个确定的对应函数关系Hash(),那么每个元素关键码与结构中的一个唯一的存储.....
  • 假设数组hashTable的长度是mSize,用平方探测法插入数字num,每次的位置pos = (num + i * i) % mSize,i的范围是[0, mSize)。 bool flag = false; //未插入 for(int i = 0; i < mSize; i++){ int pos = (num + i...
  • 数据库系统的设计,里面hash表使用二次探测再散列,不是会返回错误的结果么?那它们是怎么实现的?
  • DS哈希查找—二次探测再散列

    万次阅读 多人点赞 2018-12-04 17:23:03
    输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。 输入 测试次数t 每组测试数据格式如下: 哈希表长m、关键字个数n n个关键字 查找次数k k个待查关键字 输出 对...
  • 构造哈希表之二次探测

    万次阅读 多人点赞 2016-06-08 01:19:00
    while (_states[index] == EXITS)//二次探测 { if (_tables[index]._key == key) { return false; } index = index + 2 * i - 1; index %= _capacity; ++i; } _tables[index]._key = ...
  • //二次探测法 index = (index + iCount*iCount) % Hash->capacity; iCount++; } Hash->arr[index].key = key; Hash->arr[index].state = EXISTED; return 1; } //扩容操作 //如果负载因子超标,则...
  • HashTable的简单介绍HashTable是根据关键字直接访问在内存存储的数据结构。 HashTable叫哈希表或者散列表。 它通过一个关键值的函数将所需的数据...给定一字符串“abckhdgubhkacdggk”找出第一只出现一的字符。
  • //偶数冲突向后查找 NewPos = CurrentPos - ( CrashNum / 2 ) * ( CrashNum / 2 ) ; while ( NewPos < 0 ) //等于也不行 { NewPos = NewPos + h - > TableSize...
  • 线性和二次探测-源码

    2021-02-13 08:30:41
    线性和二次探测
  • 线性探测再散列 例如 哈希函数为: H(key) = key %13,key 为关键字,采用开放地址法中的线性探测再散列解决冲突,依次输入 11 个关键字,16,74,60,43,54,90,46,31,29,88,77,构造哈希表    如...
  • cpp代码-二次探测再散列哈希表
  • 哈希表-开放地址法(二次探测以及在哈希法)
  • 前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列 (二)、二次探测再散列 为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,492
精华内容 32,596
关键字:

二次探测