首页 > 其他分享 >哈希

哈希

时间:2024-05-08 13:35:54浏览次数:14  
标签:idx int ne long 哈希 表中

哈希

字符串哈希

  • 原理

image-20240501195229463

核心思想:将字符串看成P进制数,P的经验值是131或13331,取这两个值的冲突概率低
小技巧:取模的数用2^64,这样直接用unsigned long long存储,溢出的结果就是取模的结果

typedef unsigned long long ULL;
const int N = 1e5+10, P = 131;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始值
p[0] = 1;
for(int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i - 1];
    p[i] = p[i - 1] * P;
}

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

一般哈希

拉链法

4.jpg

开放寻址法

5.jpg

1.jpg

2.jpg

3.jpg

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;
        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

标签:idx,int,ne,long,哈希,表中
From: https://www.cnblogs.com/hnu-hua/p/18179464

相关文章

  • 哈希基础知识学习-python版
    哈希哈希表根据key直接进行访问的无序数据结构,复杂度为O(1)哈希表的实现---字典初始化d1=dict()查找#使用中括号[]进行查找,括号内为特定的键,键-值dic={"a":1,"d":0,"e":3}print(dic["a"])#输出1print(dic["z"])#报错修改dic["a"]=5print(dic[&quo......
  • 在密码学中,“加盐”(Salting)是指在存储用户密码的哈希值之前,向原始密码添加一个随机生
    在密码学中,“加盐”(Salting)是指在存储用户密码的哈希值之前,向原始密码添加一个随机生成的字符串(称为“盐”Salt)的过程。这个盐值通常是全球唯一的,并且与每个用户账户相关联,存储在数据库中与哈希值一起。加盐的目的主要有两个:抵御彩虹表攻击:彩虹表是一种预先计算好的哈希值对照表......
  • lc1(暴力、哈希)
    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例1:输入:nums=[2,7......
  • 【Redis】Redis的操作命令(二)——Redis 哈希(HASH)
    Redishash是一个string类型的field(字段)和value(值)的映射表,hash特别适合用于存储对象。当设置一个名为demo的哈希对象时:HSETdemoname"redistutorial"description"redisbasiccommandsforcaching"likes20visitors23000 获取哈希对象语句,如下:HGETALLde......
  • 2024-04-23---简单题---有效的字母异位词(哈希表)
    题目:思路:排序:复杂度较高。两个字符串进行排序,然后开始比较两个字符串是否相等哈希表:主要是一个hashmap记录第一个字符串所有字符出现的次数,然后遍历第二个字符串没找到一个就将次数减一。看最后所有的值是否为0.时间复杂度选第二种,简单题罢了。代码:排序classSolution......
  • 异或哈希
    问题:https://codeforces.com/contest/1175/problem/F关键点:随机化+异或1.为何要异或:忽略顺序将1~n随机的一一映射到longlong值域内,形成新的映射数组b。再根据异或的特点,只需要判断:b[1]⊕b[2]⊕…………⊕b[n]==b[a[l]]⊕b[a[l+1]]⊕……⊕b[a[r]]2.为何要随机,因为若不随......
  • 哈希
    哈希入门LeetCode1.两数之和注意添加顺序,先判断再添加...classSolution{publicint[]twoSum(int[]nums,inttarget){//{numsvalue:index}Map<Integer,Integer>map=newHashMap<>();List<Integer>res=newArrayList<>......
  • MD5哈希长度延展攻击
    MD5哈希长度延展攻击原理已知原始消息(m)和其对应的哈希值(h)。选择额外数据(m’)。计算填充,使得填充后的消息长度满足长度模512等于448,并包含新消息的长度信息。构造新消息(m+\text{填充}+m’)。计算新消息的哈希值(h’)。代码importhas......
  • 哈希
    简介哈希是一种能把字符串(实际上数组也行,不过本文都会以字符串为例)映射成一个数的算法,哈希就是把一个字符串转成一个\(K\)进制数,但由于得到的数可能会非常大,所以其中会用到取模,因此哈希也有些玄学(建议CF有赛后hack的比赛不要使用哈希,或提高哈希的安全度)。普通哈希可以将......
  • MD5哈希长度延展攻击(选做)
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......