精华内容
下载资源
问答
  • 哈希

    2019-10-01 10:07:13
    实现:构造哈希,处理哈希冲突。...虽然链地址法并不要求哈希桶长度必须为质数,但SGI STL仍然以质数来设计哈希桶长度,并且将28个质数(逐渐呈现大约两倍的关系)计算好,以备随时访问,同时提供一个函数,用来...

    实现:构造哈希,处理哈希冲突。

    构造哈希:取地址法、余数法、平方取中;(除以槽的数量取余数)

    处理冲突:链地址法、再哈希、建立一个公共的溢出区、开放定址法

    STL使用链地址法,用一个链表保持相同散列值的元素。

    虽然链地址法并不要求哈希桶长度必须为质数,但SGI STL仍然以质数来设计哈希桶长度,并且将28个质数(逐渐呈现大约两倍的关系)计算好,以备随时访问,同时提供一个函数,用来查询在这28个质数之中,“最接近某数并大于某数”的质数。

    如何rehash?

    C++的hash表中有一个负载因子loadFactor,当loadFactor<=1时,hash表查找的期望复杂度为O(1). 因此,每次往hash表中添加元素时,我们必须保证是在loadFactor <1的情况下,才能够添加。

    因此,当Hash表中loadFactor==1时,Hash就需要进行rehash。rehash过程中,会模仿C++的vector扩容方式,Hash表中每次发现loadFactor ==1时,就开辟一个原来桶数组的两倍空间,称为新桶数组,然后把原来的桶数组中元素全部重新哈希到新的桶数组中。

    哈希表的桶个数为什么是质数,合数有何不妥?

    哈希表的桶个数使用质数,可以最大程度减少冲突概率,使哈希后的数据分布的更加均匀。

    如果使用合数,可能会造成很多数据分布会集中在某些点上,从而影响哈希表效率。

     

    转载于:https://www.cnblogs.com/pacino12134/p/11253033.html

    展开全文
  • 哈希 哈希

    2021-03-12 18:42:56
    哈希哈希化:通常我们会将大数字转化为数组范围内下表的过程,我们就称之为哈希哈希函数:单词转化为大的数子,大数组再转为哈希化的代码放到一个函数...2.开放地址发:*线性探测 *二次探测 *在哈希 线性:插入.
    哈希表
    哈希化:通常我们会将大数字转化为数组范围内下表的过程,我们就称之为哈希话
    哈希函数:单词转化为大的数子,大数组再转为哈希化的代码放到一个函数中
    哈希表:最终将数据插入到这个数组中,对整个结构的封装就称之为哈希表
    解决冲突(重复)的方法
    1.连地址法:每个数组单元中存储的不是单个数据,而是一个数组或者链表,一旦发现重复就将元素插入到首端或者末端。使用链表数组?插入到首端尾端?因为产生冲突的可能性比较小,并且更具业务需求决定
    2.开放地址发:*线性探测 *二次探测 *在哈希
            线性:插入:当发现下标index=2已经有元素,也就是产生冲突时,让下表index++,直到找到位置是空是将其插入。查询:首先找到下表index=2,如果此时二的位置的数结果与查询结果相同则返回,否则下表index++,直到找见查询的值。如果不存在呢?如果查找有空白就结束,返回false。
    缺点:会产生聚集问题
    二次探测:二次探测优化探测步长,线性探测的步长为1,二次探测步长为inde+1,1,4,9方,idnex+2的方,。。。。
    缺点:依次累加步长相同,就是步长不一的一种聚集,也会影响效率
    在哈希:需要一个关键字,把关键字用另外一个哈希函数再做一次在哈希,这种使用在哈希的结果作为步长,对于指定关键字,步长在调整中不变,不过不同的关键字使用不同的步长,
    第二次哈希特点:与第一个哈希的函数要不同,并且输出结果不可以为0
    stepSize=contant-(key%constant)

     

    展开全文
  • 由于散列中存在冲突问题,所以有些关键码的存储地址并不是和散列函数计算的一样,后来提出很多解决方法解决冲突,其中线性探测法就是一种。所谓线性探测法就是当发生冲突时,从冲突位置的下一个位置起,依次寻找空的...

    问题描述】
    由于散列中存在冲突问题,所以有些关键码的存储地址并不是和散列函数计算的一样,后来提出很多解决方法解决冲突,其中线性探测法就是一种。所谓线性探测法就是当发生冲突时,从冲突位置的下一个位置起,依次寻找空的散列地址。这种情况下如果想要查找某个关键字,就要不断探测,最终才可以找到关键码的存储位置,如今需要统计这个过程中的关键码对比次数。
    已知关键码集合(关键码均大于零),散列表表长为maxS,散列函数为H(key)= key %divi,用线性探测法处理冲突。
    【输入形式】第一行两个整数,第一个表示散列表表长maxS,第二个表示除数divi;第二行关键码的个数;第三行关键码集合,数据元素之间用空格隔开;第四行表示要查找的关键码key。
    【输出形式】待查找值的哈希地址。如果待查找值不存在,则输出-1。
    【样例输入】
    11 11
    9
    47 7 29 11 16 92 22 8 3
    3
    【样例输出】6

    分析:
    1 .创建一个哈希数组
    2 .写一个存入哈希的函数 把输入的数据存入哈希数组里
    3 .在哈希数组中查询 输出结果

    实现

    创建存入哈希数组的函数

    void Insert (int maxS,int divi,int k,int ht[])
    {//maxS 数组长度 divi 除数 k 要存入的数 ht[] 哈希数组
        int j;
        j=k%divi;
        if(ht[j]==0)//为 0 说明 没有存放数据
            ht[j]=k;
        else if(ht[j]!=0) //有数据 
        {
            int i=j;
            while(ht[i]!=0)
            {
                i=(i+1)%maxS;//利用线性探测 每次加一 
            }
            ht[i]=k;
        }
    }
    

    查询下标的函数

    int Search (int maxS,int divi,int k,int ht[])
    {//这里的k和上面的k不同 这个 k 为关键码(key 要查询的数)
        int j;
        j=k%divi;
        int i=j;
        int cnt=0;
        while(ht[i]!=0&&cnt<maxS)//防止因查找不到而死循环
        {
            cnt++;//每次循环 计数器加一
            if(ht[i]==k)
                return i;//找到返回下标
            else
            {
                i=(i+1)%maxS;
            }
        }
        return -1;//如果未找到 返回-1
    }
    

    主函数

    int main()
    {
        int maxS,divi,n,k;
        cin>>maxS>>divi;
        cin>>n;
        int ht[maxS]={0};
        int a[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        cin>>k;
        for(int k=0;k<n;k++)
        {
            Insert(maxS,divi,a[k],ht);//将输入的数据存入哈希数组当中
        }
        cout<<Search(maxS,divi,k,ht)<<endl;
    
    }
    

    在下是一名小白 如果有不恰当的地方 欢迎指正

    展开全文
  • 地址处理哈希冲突的哈希

    千次阅读 2007-11-06 13:54:00
    哈希表作为一种快速查询的数据结构,在数据查找等方面具有广泛的应用:本文就是其一种实现方式,表结构比一般的哈希表的键值结构多了一个count计数,这个值是我论文使用的,所以不介绍了,我还没有毕业呢^_^!...

    哈希表作为一种快速查询的数据结构,在数据查找等方面具有广泛的应用:

    本文就是其一种实现方式,表结构比一般的哈希表的键值结构多了一个count计数,这个值是我论文使用的,所以不介绍了,我还没有毕业呢^_^!

    其实,我的整个实验还有别的代码,这里就不贴完整了,下面的代码也是有删减的,也未提高哈希表删除操作

    首先是:哈希表节点的对象类

    展开全文
  • 哈希

    千次阅读 2019-11-06 09:33:27
    初入数据结构的哈希表(Hash Table) 这次我们来总结一下关于...关键字、值、哈希函数、哈希地址、哈希表之间的关系? 什么是哈希冲突 常见的哈希函数构造方法 怎么样才是好的哈希函数? 常见构建哈希函数的六个方法...
  • 哈希表的构建与查询

    千次阅读 2014-12-22 17:29:41
    设要存放的数据元素有n个,存放数据元素的数组个数为m,哈希函数的设计目标,就是要使通过哈希函数得到的n个数据元素的哈希地址 。  1 除留余数法  除留余数法是用数据元素的关键字K除以哈希表长度m所得的余数...
  • 哈希为什么查询速度 快

    千次阅读 2018-07-17 13:44:25
    哈希算法存取之所以快,是因为其 直接通过关键字key得到要存取的记录内存存储位置 试想这样的场景,你很想学太极拳,听说学校有个叫张三丰的人打得特别好,于是你到学校学生处找人,学生处的工作人员可能会拿出学生...
  • 哈希查找-图书馆查询

    2018-10-16 18:30:47
    下面用哈希查找来解决一个实际问题:图书馆查询问题。 图书馆里面有若干本书(至少3000本,至多30000本),为帮助用户快速查找每本书所在的书架位置,请设计一个模拟 系统实现基于图书编号的快速查询方法。 输入:...
  • 本题要求你模拟hash的保留余数法:取关键字被某个不大于哈希表表长m的数key除后所得余数为哈希地址。即 H(key) = key MOD m。 现在有两种操作:  1. 往hash表插入一个值为x正整数。   2.查询hash表的...
  • 数据结构 人名查询哈希表设计

    千次阅读 多人点赞 2020-01-08 15:56:57
    哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。 测试数据 取读者周围较熟悉的30个人名。 选作内容 (1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数...
  • 针对某个集体(比如你所在的班级)中的同学联系电话设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 【基本要求】 (1) 假定每个记录有下列数据项:电话号码、用户名、地址。 (2) 一是从数据...
  • 一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 ...
  • 哈希查找--链地址

    2020-12-26 13:41:45
    哈希查找–链地址法 题目描述 给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和表头插入 如果首次查找失败,就把数据插入到相应的位置中 实现哈希查找功能 输入 第一行输入n...
  • 哈希索引

    千次阅读 2019-05-22 17:09:45
    哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码...
  • 哈希函数

    2021-05-12 19:29:39
    地址法:为每个哈希值维护一个链表,并将具有相同哈希值的元素都放入这一链表当中。 如下图 开放地址法:当发现哈希值 hh 处产生冲突时,根据某种策略,从 hh 出发找到下一个不冲突的位置。例如,一种最简单的...
  • 哈希查找

    2019-06-03 14:38:46
    提起哈希,Java中的Hashtable类,它是由 key/value 的键值对组成的集合,它就是应用了哈希技术。 那什么是哈希查找呢?在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技术是在记录的存储位置和记录的 key...
  • 哈希值与哈希

    2020-06-21 21:44:02
    哈希值:是一个十进制的整数,由系统随机给出(就是对象的地址值,是一个逻辑地址,是模拟出来得的地址,不是数据实际存储的物理地址) 在Object类中有一个方法,可以获取对象的哈希值 int hashCode() 返回该对象...
  • 并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为哈希表,这一映像过程称为哈希造表或者散列,所得的存储位置称哈希地址或散列地址。2、 hash冲突对应不同的关键字可能获得相同的hash地址,即 ...
  • 哈希函数和哈希

    2021-01-16 11:00:42
    哈希函数和哈希表? 哈希函数和哈希表是非常重要的内容,在面试的时候...桶后跟的是红黑树(查询快)。 哈希表开头就是哈希域,这个一般是经过我们压缩了的哈希域,但是可以保证离散性。 Hash函数不是用来排序的,hashm
  • 在链地址法的描述中,哈希表的结构更加复杂一点,但是查询和存储的性能都有进一步提升,尤其是面对超大量的数据时,将哈希表的每一个位置设计成链表,无疑加快了查询速度,而且理解上也更加容易。 在开放地址法中,...
  • A : DS哈希查找–链地址法 Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 13 Solved: 9 Description 给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和表头插入 如果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 77,091
精华内容 30,836
关键字:

哈希地址查询