哈希基本理论与BKDRHash

这篇具有很好参考价值的文章主要介绍了哈希基本理论与BKDRHash。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哈希基本理论

描述
对n个元素我们通过一个Hash函数将其映射(映射:和key-value类似)到m个空间中(n<=m)。
每个空间仅存放一个元素
空间位置=Hash(n的关键字)

常见问题
1.hash函数的设计
hash函数的设计决定了整个hash程序,地位类似于状态转移方程于DP中的地位
好的hash要尽量避免冲突(冲突:你算出来的hash(n1)=hash(n2),也就是说有两个不同的元素通过你的函数计算得出同一个位置)

2.冲突如何解决
这个具体问题中都不一样,空说无用,见下文代码示例。

BKDRHash

我买的书上提到了好几种字符串的Hash,其中BKDRHash是首选,这是测评说的不是我说的。
各种Hash的测评数据在这里

Hdu2648
我们以此题为例拆分整个代码来看BKDRHash
首先总代码
我的代码很大~ 你要忍一下

#include <bits/stdc++.h>
using namespace std;
struct node
{
    char name[35];
    int price;
};
vector <node> list1[10005];
unsigned int BKDRHash(char *str)
{
    unsigned int seed=31,key=0;
    while(*str)
    {
        key=key*seed+(*str++);
    }
    return key&0x7fffffff;//不要超过int,好吗
}
int main()
{
    int n,m,key,add,memoryp,ranks,len;
    int p[100005];
    char s[35];
    node temp;
    cin>>n;
    for(int i=0;i<10005;i++)
        list1[i].clear();
    for(int i=0;i<n;i++)
    {
        cin>>temp.name;
        key=BKDRHash(temp.name);
        list1[key].push_back(temp);
    }
    for(cin>>m;m;m--)
    {
        ranks=0;
        len=0;
        for(int i=0;i<n;i++)
        {
            cin>>add>>s;
            key=BKDRHash(s)%10005;
            for(int j=0;j<(int)list1[key].size();j++)
            {
                if(strcmp(list1[key][j].name,s)==0)
                {
                    list1[key][j].price+=add;
                }
                if(strcmp(s,"memory")==0)
                {
                    memoryp=list1[key][j].price;
                }
                else
                {
                    p[len++]=list1[key][j].price;
                }
            }
        }
        for(int i=0;i<len;i++)
        {
            if(p[i]>memoryp)
            {
                ranks++;
            }
        }
        cout<<ranks<<endl;
    }
    return 0;
}

拆分出来看就好多了

基础部分就不一 一细说了
BKDRHash部分

unsigned int BKDRHash(char *str)
{
    unsigned int seed=31,key=0;
    while(*str)
    {
        key=key*seed+(*str++);
    }
    return key&0x7fffffff;//不要超过int,好吗
}

while中是在计算key,或者说在转化出一个key值,最后维护一下边界不要超出int表示最大范围

cin>>temp.name;
key=BKDRHash(temp.name);
list1[key].push_back(temp);
这是在使用没啥好说的

进一步缩小空间

key=BKDRHash(s)%10005;

当然随之而来的就是冲突问题,接下来就是解决冲突,也是Hash中最重要的部分

    for(int j=0;j<(int)list1[key].size();j++)
            {
                if(strcmp(list1[key][j].name,s)==0)
                {
                    list1[key][j].price+=add;
                }
                if(strcmp(s,"memory")==0)
                {
                    memoryp=list1[key][j].price;
                }
                else
                {
                    p[len++]=list1[key][j].price;
                }
            }

当我们输入一个name转化为key值之后我们可以对这个key之下的所有元素进行遍历,遍历到了对应的元素也就是strcmp返回0时,我们自然也就完成了匹配
其实整个冲突处理还要加上前面的一句
list1[key].push_back(temp);

没有这个存储也是无法实现冲突处理的。

我们要找到的不是一个完全完美的hash因为就算是完美的,用的过程中缩小范围之后也会产生冲突。我们需要学习经典的hash,适当设计自己的,重点在如何处理各种冲突上。

总结一下
设计函数返回key
用vector存储key对应的元素

用vector处理冲突文章来源地址https://www.toymoban.com/news/detail-417353.html

到了这里,关于哈希基本理论与BKDRHash的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录day6|哈希表理论基础、有效的字母异位词、两个数组的交集、快乐数、两数之和

    当需要判断一个元素是否在一个集合中,哈希表的时间复杂度只有O(1)。 哈希表有一个映射的操作,当映射的元素在同一个索引下标的位置,就会引发 哈希碰撞 。 哈希碰撞的两种解决方法:拉链法 线性探测法   同时,哈希表还有常见的三种数据结构:分别是数组、集合s

    2024年02月06日
    浏览(46)
  • 算法训练第5天|哈希表理论基础 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

    哈希表是根据 关键码 的值而直接进行访问的数据结构。 一般哈希表都是用来快速判断一个元素是否出现集合里。 数组、集合set、映射map 力扣链接 题目描述: 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意: 若  s  和  t   中每个字符出现的

    2024年02月19日
    浏览(43)
  • 【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和

    【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和 新的一部分-哈希表,哈希表之前做题相对比较熟练希望能快速复习 Source: 题目 Note:以前刷的时候使用python字典,这次换做C++ 注意数组就是简单的哈希表,但是数组的大小

    2024年02月20日
    浏览(45)
  • 数据结构:定长顺序串(SString)基本操作的算法描述(C语言)

    作者在学习数据结构时,发现鲜有完全按照 C 语言描述的算法操作,这让习惯于写 .c 而不是 .cpp 的初学者很是头疼。本文将基于 C 语言描述算法操作,如有错漏还望大佬们指正。 本文将按照严惠敏所著《数据结构(C语言版)》所做的函数原型声明进行算法描述,由于C语言不支

    2024年02月07日
    浏览(69)
  • ARM架构基本理论(1)

    ARM (Advanced RISC Machine)是一种基于 RISC(Reduced Instruction Set Computing) 架构的计算机处理器架构,由ARM Holdings(ARM公司)开发和授权给其他公司生产和销售。 ARM架构最初是为低功耗、高效能的嵌入式系统设计的,如智能手机、平板电脑、数字电视、路由器、音频设备、控制器

    2024年02月02日
    浏览(38)
  • 数据仓库基本理论Ⅰ

    数据仓库是一个面向主题的,集成性的,非易失性的,时变性的数据集合,用于管理决策。 数据仓库解决的问题: 为业务部门提供准确清晰的报表 为管理人员提供更强的分析能力 为数据挖掘和知识发现奠定基础 面向主题 数据仓库内的数据是 针对特定的业务主题 。数据仓

    2024年02月22日
    浏览(39)
  • 1.数据仓库基本理论

    概念 : 数据仓库是一个用于存储、分析、报告的数据系统 数据仓库的目的是构建面向分析的集成化数据环境,分析结果为企业提供决策 特点 : 数据仓库本身并不“生产”任何数据,其数据来源与不同外部系统 同时数据仓库自身不需要“消费”任何数据,其结果开放给各个

    2024年02月11日
    浏览(33)
  • 解释基本的3D理论

    推荐:使用 NSDT场景编辑器 快速搭建3D应用场景 3D 本质上是关于 3D 空间中形状的表示,并使用坐标系来计算它们的位置。 WebGL 使用右侧坐标系 — 轴指向右侧,轴指向上方,轴指向屏幕外,如上图所示。 x y z 使用顶点构建不同类型的对象。 顶点 是空间中的一个点,在坐标系

    2024年02月10日
    浏览(31)
  • 测试基本理论-看这篇就够了

    软件测试(Software Testing): 在规定的条件下对程序进行操作,以发现程序错误,衡量软件质量,并对其是否能满足设计要求进行评估的过程。 【系统软件】:如操作系统、数据库管理系统,各种驱动软件等; 【应用软件】:如Office、有道翻译、QQ等; 【单机版本】:如Office,

    2024年02月06日
    浏览(48)
  • 网络安全:密码学基本理论.

    密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律,应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码以获取通信情报的,称为破译学,总称密码学. 目录 网络安全:密码学基本理论. 密码学基本概念: 密码安全性分析: 密码体系分析:

    2024年02月16日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包