精华内容
下载资源
问答
  • 虽然上文有提到怎么解释的开放地址法处理hash冲突,但是当时只是给了个...什么叫平方探测再散列(二次探测再散列); 老师的ppt吧。 给个原始数据如上图。 下面详细解析。 上面的是线性探测再散列。这个简单。

    虽然上文有提到怎么解释的开放地址法处理hash冲突,但是当时只是给了个简单的图,没有 详细讲解一下,
    我当时有点不明白,回头查查资料,然后亲自动手,整理了一下。
    然后我就三幅图详细讲解一下:
    什么叫线性探测再散列
    什么叫平方探测再散列(二次探测再散列);

    老师的ppt吧。


    给个原始数据如上图。

    下面详细解析。



    上面的是线性探测再散列。这个简单。



    这个就是那个2次平方再散列啦。

    估计讲的很详细啦吧。


    这个只是单纯的看,是不行的,你只是看到,有三个数据在按一定的算法(也就是mod 11 取余)散列到数组上的时候,看到有三个数据产生冲突啦。那么为了让这些数据更好的全部都能落在这个数组上,更好的利用这个数组,不浪费空间,就要去充分利用未分配到数据的数组上的其他位置。那么这就是解决冲突的需求。线性探测法:刚刚开始的时候,数据未冲突的时候,都按照取余的结果挨个按自己的取余结果,可以理解为你上学分班时候,你选座位。当你要去的座位,没人选的时候,你就坐上去,然后这个位置就被选过了,下次如果还有人和你一样,也选了这个座位,那么,他就冲突了。按照线性探测法的做法是:他本来是要坐你的位置的,但是,你已经坐了,那么,他只能以你为基准,查看你的座位的下一个,如果没人就坐下,如果有人,继续找下一个。当他也坐下来之后,后面再来的。发现自己的位置,被这个冲突的哥们占位了,那么,没办法,只能按刚刚那哥们的做法,继续找自己的位置。直到这个班级的所有位置都有人坐,那就OK。对应到这hashmap上就是 把这个数组的所有位置都给占满咯。这个线性探测和平方探测的区别就是在冲突的哥们找自己的位置的差别,一个是挨个查找;一个是高级点,或+n的平方,或-n的平方。都是为了占满教室的位置。


    下面是一个总览的链接:

    java 解决Hash(散列)冲突的四种方法--开放定址法(线性探测,二次探测,伪随机探测)、链地址法、再哈希、建立公共溢出区



    展开全文
  • 浅谈哈希函数与线性探测再散列

    千次阅读 2011-10-21 20:15:07
    一般很多网页的URl地址都是巨长无比的,那么要存储每个网页真的需要为它们分配如此冗长的空间吗,我们相信这些足以让服务器崩溃的愚蠢行为是不会被各大互联网巨头所采用的,所以,他们会选择采用哈希函数的方式来...

            我们知道,一般很多网页的URl地址都是巨长无比的,那么要存储每个网页真的需要为它们分配如此冗长的空间吗,我们相信这些足以让服务器崩溃的愚蠢行为是不会被各大互联网巨头所采用的,所以,他们会选择采用哈希函数的方式来存储这些地址。

            对于一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。

            而哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量,通过一定的函数关系(称为哈希函数),计算出的值,即为该元素的存储地址,表示为:Addr = H(key)。

            哈希函数的好坏在与其对于冲突的处理的好坏。在哈希表中,不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2,但H(K1)=H(K2)。均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。

            要处理这种冲突,我们可以采用如下的方式:

    1.拉链法

      拉出一个动态链表代替静态顺序存储结构,可以避免哈希函数的冲突,不过缺点就是链表的设计过于麻烦,增加了编程复杂度。此法可以完全避免哈希函数的冲突。

    2.多哈希法

       设计二种甚至多种哈希函数,可以避免冲突,但是冲突几率还是有的,函数设计的越好或越多都可以将几率降到最低(除非人品太差,否则几乎不可能冲突)。

    3.开放地址法

      开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
      其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1,称线性探测再散列。
      如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
      称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

    4.建域法

       假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。


    下面我们来看一个简单的哈希函数的例子,本例采用的是P.J.Weinberger的哈希算法:

    // P. J. Weinberger Hash 
    unsigned int PJWHash(char *str)
    {
        unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
        unsigned int ThreeQuarters    = (unsigned int)((BitsInUnignedInt  * 3) / 4);
        unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);
        unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt 
                                                   - OneEighth);
        unsigned int hash    = 0;
        unsigned int test    = 0;
     
        while (*str)
        {
            hash = (hash << OneEighth) + (*str++);
            if ((test = hash & HighBits) != 0)
            {
                hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
            }
        }
     
        return (hash & 0x7FFFFFFF);
    }  

            相信看了上面的程序,许多人都会说,这是什么垃圾算法啊,这个莫名奇妙。的确,在哈希函数中,这是一个效率不太高的算法,对于有效的散列数据的存储不是靠复杂的地址分配就可以完成的,所以,要想真正的完成一个适合于自己的文件存储的哈希函数,绝不能一概而论。

            写到这这篇文章也就差不多了,也许你会说为什么没有提到什么是线性探测再散列,我想说的是,对于那些学了哈希函数却只知道用线性探测再散列这个装B的概念来显示自己高端的人,您还是回家洗洗睡吧。真正高明的哈希函数可不是用线性探测再散列就可以解决的,这种东西最多也只会在各种无趣的等级考试中出现了。

            顺便鄙视下某企鹅今年的校园招聘出了个线性探测再散列的题目。好了,写到这也差不多了,最为一篇浅谈性质的文章,我也不想讲的太多了,所以就这样吧!




    展开全文
  • DS哈希查找—二次探测再散列

    千次阅读 2018-12-08 19:47:36
    DS哈希查找—二次探测再散列 题目描述 定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。 输入 测试次数t 每组测试数据格式如下...

    DS哈希查找—二次探测再散列

    题目描述

    定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。

    输入

    测试次数t

    每组测试数据格式如下:

    哈希表长m、关键字个数n

    n个关键字

    查找次数k

    k个待查关键字

    输出

    对每组测试数据,输出以下信息:

    构造的哈希表信息,数组中没有关键字的位置输出NULL

    对k个待查关键字,分别输出:

    0或1(0—不成功,1—成功)、比较次数、查找成功的位置(从1开始)

    样例输入

    1

    12 10 22 19 21 8 9 30 33

    4 41 13

    4

    22

    15

    30

    41

    样例输出

    22 9 13 NULL 4 41 NULL 30 19 8 21 33

    1 1 1

    0 3

    1 3 8

    1 6 6

    Solution:

    import java.util.*;
    public class Main{
    	public static void main(String args[]){
    		Scanner scanner = new Scanner(System.in);
    		// test times
    		int times = scanner.nextInt();
    		for (int j = 0; j <times ; j++) {
    			int m = scanner.nextInt();// length
    			int n = scanner.nextInt();// num
    			int[] hash = new int[m];
    			for (int i = 0; i <n ; i++) {
    				int key = scanner.nextInt();
    				int h = key%11;
    				// create d
    				int t = 1; // di = 1,2,3,..,m-1
    				while (hash[h]>0){
    					int d;
    					if (t%2==1){ // positive
    						d = ((t+1)/2)*((t+1)/2);
    					}else {
    						d = -(t/2)*(t/2);
    					}
    					h = (key%11+d +m)%m; // Hi = (H(key) + di) MOD m   i=1,2,...,k(k<=m-1)
    					t++;
    				}
    				hash[h] = key;
    			}
    			for (int i = 0; i < m; i++) {
    				if (hash[i] == 0){
    					System.out.print("NULL");
    				}else {
    					System.out.print(hash[i]);
    				}
    				if (i<m-1){
    					System.out.print(" ");
    				}
    			}
    			System.out.println();
    			int k = scanner.nextInt(); // the times of search
    			for (int i = 0; i <k ; i++) {
    				int is_find=0,compare_times=1;
    				int key = scanner.nextInt();
    				int h = key%11;
    				int t = 1;
    				while (hash[h]!=key){
    					int d;
    					if (t%2==1){ // positive
    						d = ((t+1)/2)*((t+1)/2);
    					}else {
    						d = -(t/2)*(t/2);
    					}
    					if (t>=m || hash[h] ==0){
    						is_find =-1;
    						break;
    					}
    					h = (key%11+d +m*t)%m;
    					t++;
    					compare_times++;
    				}
    //				compare_times = (h%11 - key%11 +m)%m + 1;
    				if (is_find==-1){
    					System.out.println(is_find+1+" "+compare_times);
    				}else {
    					System.out.println(is_find+1+" "+compare_times+" "+(h+1));
    				}
    			}
    		}
    
    	}
    }
    

     

    展开全文
  • 问题 B: DS哈希查找—二次探测再散列(关键字互不相同) 时间限制: 1 Sec 内存限制: 128 MB 提交: 123 解决: 57 [提交][状态][讨论版] 题目描述 定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入...

    文章目录


    问题 B: DS哈希查找—二次探测再散列(关键字互不相同)
    时间限制: 1 Sec  内存限制: 128 MB
    提交: 123  解决: 57
    [提交][状态][讨论版]
    题目描述
    定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。
    
    输入
    测试次数t
    每组测试数据格式如下:
    哈希表长m、关键字个数n
    n个关键字(关键字为互不相同的正整数)
    查找次数k
    k个待查关键字
    输出
    对每组测试数据,输出以下信息:
    构造的哈希表信息,数组中没有关键字的位置输出NULL
    对k个待查关键字,分别输出:
    0或1(0—不成功,1—成功)、比较次数、查找成功的位置(从1开始)
    样例输入
    1
    12 10
    22 19 21 8 9 30 33 4 41 13
    4
    22
    15
    30
    41
    样例输出
    22 9 13 NULL 4 41 NULL 30 19 8 21 33
    1 1 1
    0 3
    1 3 8
    1 6 6
    提示
    
    

    直奔代码

    // 问题 B: DS哈希查找—二次探测再散列(关键字互不相同)
    #include<iostream>
    using namespace std;
    
    #define INF -99
    
    
    int main()
    {
        int t;
        cin >> t;
        while( t-- ){
            int m, n;
            cin >> m >> n;
            int * a = new int[m]; 
            for( int i=0; i<m; i++) a[i] = INF;
            
            // 建表
            while( n-- ){
                int num ; 
                cin >> num;
                int di = 1;
                int h = num%11;
                if(a[h]==INF){
                    a[h] = num;
                    continue;
                }
                while( true ){
                    int t1 = (h+di*di)%m;
                    int t2 = (h-di*di)%m;
                    t2 = t2<0 ? (t2+m) : t2;
    
                    /*******
                     * 重点: 这里一定要注意对t2的取值范围进行处理,小于0的时候要进行循环移位
                     * 博主再初学这个的时候,可是被他坑惨了呜呜
                     * 
                     * ******/
    
    
                    if( a[t1] == INF ){
                        a[t1] = num;
                        break;
                    } else if( a[t2] == INF ){
                        a[t2] = num;
                        break;
                    }
                    else{
                         di++;
                    }
                }
            }
            for(int i=0; i<m; i++){
                if(a[i] == INF ) cout<<"NULL"<<" ";
                else cout<<a[i]<<" ";
            }
            cout << endl;
            int k;
            cin >> k;
            while(k--) {
                int f;
                cin >> f;
                int h = f%11;
                int times = 0;
                int flag = 0;              // 没找到为0, 找到为1
                int tf = 0;
                int di = 1;
                 /**************
                  * 查找分三种情况:
                  * 1. 要找的关键字的hash地址为空
                  * 2. 要找的关键字的hash地址不为空且等于关键字
                  * 3. 要找的关键字的hash地址不为空,也不等于关键字,则进行二次探测(平方)
                  * 
                  * #### 注意比较次数自加的位置
                  *     1. 先和自身的hash地址比较,不匹配则+1
                  *     2. 和t1 = (h+di*di)%m; t1的地址比较,不成功则+1
                  *     3. 和t2 = (h-di*di)%m; t2 的地址比较,不成功则+1
                  * **********/
                 times ++;
                 if(a[h]==INF){             // 第一种情况     
                     cout<<0<<" "<<times<<endl;
                 }
                 else{
                     if( a[h]==f ){         // 第二种情况
                         cout<< 1 << " " << times << " " << h+1 <<endl;
                         continue;
                     }
                     while(true){           // 第三种情况
                        int t1 = (h+di*di)%m;
                        int t2 = (h-di*di)%m;
                        t2 = t2<0 ? (t2+m) : t2;
                        times++;
                        if( a[t1]==f ){
                             cout<<1<<" "<<times<<" "<<t1+1<<endl;
                             flag = 1;
                             break;
                         }
                        times++;
                        if( a[t2]==f ){
                             cout<<1<<" "<<times<<" "<<t2+1<<endl;
                             flag = 1;
                             break;
                         }
                        if(a[t1]==INF || a[t2]==INF ){
                            break;
                        }
                         di ++;
                     }
                     if( flag==0 ){
                         cout<<0<<" "<<times<<endl;
                     }
                 }
            }
        }
        return 0;
    }
    
    
    
    展开全文
  • 这是数据结构课程作业,用二次探测再散列法解决冲突建立哈希表并查找 从键盘读入 待查找 的权重数值,以除留余数法为哈希函数二次探测再散列法解决冲突建立哈希表,基于哈希算法从数组中查找相应的记录,计算相应...
  • 输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。 输入 测试次数t 每组测试数据格式如下: 哈希表长m、关键字个数n n个关键字 查找次数k k个待查关键字 输出 对每组测试...
  • DS哈希查找—线性探测再散列

    千次阅读 2018-12-04 17:02:42
    输入表长(大于、等于11),输入关键字集合,用线性探测再散列构建哈希表,并查找给定关键字。 输入  测试次数t 每组测试数据为: 哈希表长m、关键字个数n n个关键字 查找次数k k个待查关键字 输出 对每组...
  • 散列表,也称为哈希表。根据设定的哈希函数H(key)和处理冲突的方法将一组... 处理冲突的方法:1)开放定址法(线性探测再散列二次探测再散列,伪随机探测再散列) 2)哈希法 3)链地址法 4)建立一 公共溢出区
  • 例如 哈希函数为: H(key) = key %13,key 为关键字,采用开放地址法中的线性探测再散列解决冲突,依次输入 11 个关键字,16,74,60,43,54,90,46,31,29,88,77,构造哈希表    如图,例如 16%13=3...
  • 散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和...
  • 线性探测再散列时 以 存储空间的长度来取余 查找时比较次数,如在 {12}中查找12,12跟12也要进行一比较。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0...
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 下面看下2010年...
  • 题目来源:2010-408_计算机学科专业基础综合 ...将关键字序列(7 . 8 . 30 . 11 . 18 . 9 . 14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组 。 散列函数 是: H(key)=(key x3)...
  • 前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列 (二)、二次探测再散列 为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。 ...
  • 前面的文章分析了开地址法的其中一种:线性探测再散列,这篇文章来讲开地址法的第二种:二次探测再散列 (二)、二次探测再散列 为改善“堆积”问题,减少为完成搜索所需的平均探查次数,可使用二次探测法。 ...
  • 设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( ) 【南京理工大学 2001 一、15 (1.5分)】...
  • 假定一个关键字序列为{32,75,63,48,94,25,36,18},哈希地址空间为[0…10],采用哈希函数H(key)=key MOD 11,用二次探测再散列法处理冲突,试给出对应的哈希表(给出求解过程),并计算在等概率情况下查找成功...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,465
精华内容 2,586
关键字:

哈希函数二次探测再散列