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

    2020-11-03 01:04:21
    我们可以用这个式子造出哈希函数来 磁力链接,每一位数值范围是0-f 且总共有16位,这就是所谓哈希码, 这就是哈希函数的返回值。 能表示的数值范围是: 哈希函数的性质: 哈希函数的输入域可以是非常大的范围,...

    有一对 哈希元 a,b
    我们可以用下面式子造出哈希函数来
    在这里插入图片描述
    磁力链接总共有16位,每一位数值范围是0-f,这就是所谓哈希码,
    即哈希函数的返回值。

    百度百科:哈希码具体是什么?
    答:hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值

    能表示的数值范围是????????:每位都是 2的16次方 ,共有16位,所以16个2的16次方。
    在这里插入图片描述
    哈希函数的性质:
    哈希函数的输入域可以是非常大的范围,比如,任意一个字符串,但是输出域是固定的范围(一定位数的bit),假设为S(虽然S可能会很大,但是和输入域没法比),并具有如下性质:

    1. 典型的哈希函数都有无限的输入值域
    2. 当给哈希函数传入相同的输入值时,返回值一样。
    3. 当给哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,这时当然的,因为输出域统一是S,所以会有不同的输入值对应在S中的一个元素上(这种情况称为 哈希冲突)。
    4. 最重要的性质是很多不同的输入值所得到的返回值会均匀分布在S上。这是评价一个哈希函数优劣的关键不同输入值所得到的所有返回值越均匀地分布在S上,哈希函数越优秀,并且这种均匀分布与输入值出现的规律无关。比如,“aaa1”、“aaa2”、“aaa3”三个输入值比较类似,但经过优秀的哈希函数计算后得到的结果应该相差非常大。
    5. 哈希函数的离散性:举个例子就明白了,输入域是0-98的范围输出域是0 1 2

    给我99个不同的样本,依次计算不同的输出 0 1 2这三种值
    基本上在算完之后,可以说:
    有33个输入分布在0位置
    有33个输入分布在1位置
    有33个输入分布在2位置

    前3点性质是哈希函数的基础,第4点是评价一个哈希函数优劣的关键,不同输入值所得到的所有返回值越均匀地分布在S上,哈希函数越优秀,并且这种均匀分布与输入值出现的规律无关。

    比如,“aaa1”、“aaa2”、“aaa3”三个输入值比较类似,但经过优秀的哈希函数计算后得到的结果应该相差非常大。

    比如在一个房间里面。砸了一瓶香水,这些香水的分子,会固定不动。而哈希函数就是彻底把它打乱的过程。

    我们把每一个香水分子的运动轨迹通过哈希函数来确定,经过哈希函数计算后,香水分子会均匀分布在整个房间内!
    在这里插入图片描述

    哈希函数不是随机函数,其没有任何随机的成分,样本一旦固定,返回值一定是确定的!

    哈希函数会打乱输入规律。

    经哈希函数 计算完的返回值,和你原始的输入规律是没有关系的!
    在这里插入图片描述
    在这里插入图片描述
    且在0-1上也均匀分布。
    比如,
    在这里插入图片描述
    若是在0-98上均匀分布,那么在0-2上也是均匀分布

    面试官是不会让我们实现哈希函数的,因为哈希函数算法很多

    一个十六进制的字符等于4个二进制字节 16=2^4
    假设一个哈希函数得到2的64次方的范围
    所以需要2的8次方乘以2的16次方
    在这里插入图片描述
    我们把得到的结果批两段,
    在这里插入图片描述
    在这里插入图片描述
    h3相对h1和h2是独立的
    在这里插入图片描述
    我们可以通过改变系数,做出1000个哈希函数
    0位置得到0-f的均匀分布 和其他位置得到0-f的均匀分布是互相独立的
    所以,我们通过各个位置的组合 ,本身就可以得到多个哈希函数
    在这里插入图片描述

    哈希函数极其重要,甚至比哈希表还重要
    因为哈希表的实现一定要知道哈希函数的性质!

    初级6刚开始

    展开全文
  • 哈希表 哈希函数 时间 首先,什么是哈希函数? (First, what is a hash function?) Simply speaking, a hash function is a mathematical function that takes any input size and convert it to a fixed output ...

    哈希表 哈希函数 时间

    首先,什么是哈希函数? (First, what is a hash function?)

    Simply speaking, a hash function is a mathematical function that takes any input size and convert it to a fixed output size. Consider this simple hash function H(X) = Last digit of (X)

    简而言之,哈希函数是一种数学函数,它可以接受任何输入大小并将其转换为固定的输出大小。 考虑这个简单的哈希函数H(X)=(X)的最后一位

    • H(1234) = 4.

      高(1234)= 4。
    • H(12567) = 7.

      高(12567)= 7。
    • H(127) = 7.

      高(127)= 7。
    • H(1111111111) = 1.

      H(1111111111)= 1。
    • H(24)=4.

      H(24)= 4。
    • H(24)=4.

      H(24)= 4。

    So no matter what is the input and its size, we’re returning a one digit output. Another important property is that the same input will always give you the same output. H(24) will always be 4.

    因此,无论输入内容和大小如何,我们都将返回一位数字的输出。 另一个重要的特性是相同的输入将始终为您提供相同的输出。 H(24)将始终为4。

    In summary:

    综上所述:

    • A hash function generates a fixed size output (called digest or hash)

      哈希函数生成固定大小的输出(称为摘要或哈希)
    • For any input size or length, we get always the same fixed output size

      对于任何输入大小或长度,我们总是得到相同的固定输出大小
    • Totally deterministic: for the same input we get always the same output

      完全确定性的:对于相同的输入,我们总是得到相同的输出
    • It’s not a complicated operation to get the hash of any input (very easy)

      获取任何输入的哈希值并不复杂(非常简单)
    • Several inputs can have the same hash (like here 127 and 12567 both have 7 as hash). That’s called a hash collision. It’s natural since the output has a fixed size, and the input can be of ANY size, there are infinite inputs for a fixed number of outputs. For this hashing example, there can be only 10 possible outputs (1 digit — from 0 to 9). So it will be super easy to find a hash collision, giving there are infinite numbers as inputs.

      多个输入可以具有相同的哈希值(例如此处的127和12567都具有7作为哈希值)。 这就是所谓的哈希冲突。 这是自然的,因为输出具有固定的大小,并且输入可以是任何大小,对于固定数量的输出,存在无限的输入。 对于此哈希示例,只能有10个可能的输出(1位-从0到9)。 因此,如果有无限个数字作为输入,找到哈希冲突将非常容易。

    第二,什么是密码安全哈希函数? (Second, what is a cryptographic secure hash function?)

    The first example I gave you, is not really a cryptographic hash function, why? because you can easily reverse it. AKA: finding an input for a given output.

    我给您的第一个示例不是真正的密码哈希函数,为什么? 因为您可以轻松地将其反转。 又名:找到给定输出的输入。

    Basically if i tell you what input gives a hash of 6? Any number ending with 6 is a valid answer. Simple: 123456 is a candidate, 556 is another candidate. 96 is a third candidate. The ability to reverse a hash function is a bad Cryptographic property.

    基本上,如果我告诉你什么输入给出6的哈希值? 任何以6结尾的数字都是有效答案。 简单:123456是一个候选者,556是另一个候选者。 96是第三位候选人。 反转哈希函数的能力是不良的加密属性。

    So cryptographic hash functions have, in addition, the following properties:

    因此,加密哈希函数还具有以下属性:

    • It should be very hard, starting from a certain output, to get back one of the valid inputs.

      从某个输出开始,要返回一个有效输入应该非常困难。
    • It should be very hard and rare to find a collision (2 inputs generating the same hash)

      很难找到冲突(2个输入产生相同的哈希值)

    One famous cryptographic hash functions is the SHA256. For any input size, it generates 256 bits of digest. It’s so easy for any input to get the output, you can test it yourself here: https://passwordsgenerator.net/sha256-hash-generator/

    SHA256是一种著名的加密哈希函数。 对于任何输入大小,它都会生成256位摘要。 任何输入获取输出都很容易,您可以在这里自己测试: https : //passwordsgenerator.net/sha256-hash-generator/

    Image for post
    Test1234 has a hash 07480FB9E85B9396AF06F006CF1C95024AF2531C65FB505CFBD0ADD1E2F31573
    Test1234的哈希值为07480FB9E85B9396AF06F006CF1C95024AF2531C65FB505CFBD0ADD1E2F31573

    Go to this website and try the text Test1234 with capital “T”, you should get the following hash: 07480FB9E85B9396AF06F006CF1C95024AF2531C65FB505CFBD0ADD1E2F31573

    转到该网站 ,尝试使用大写字母 “ T”的文本Test1234 ,您将获得以下哈希值: 07480FB9E85B9396AF06F006CF1C95024AF2531C65FB505CFBD0ADD1E2F31573

    Anyone can easily validate that the text “Test1234” has actually that hash.

    任何人都可以轻松地验证文本“ Test1234”实际上具有该哈希。

    十六进制表示 (Hexadecimal representation)

    Note that the hash is written using 64 characters just as a compact way to represents the 256 bits. This is called HEX representation, standing for hexadecimal base. The way it works is the following:

    请注意,哈希是使用64个字符写入的,就像表示256位的紧凑方式一样。 这称为十六进制表示,代表十六进制。 它的工作方式如下:

    Image for post
    Hex to binary
    十六进制到二进制

    You have 16 characters in hex base ( the 0 -> 9 are 10 characters +6 letters: A,B,C,D,E,F = 16 characters in total), each can encode one of the combination of 4 bits.

    您有16个十六进制字符(0-> 9是10个字符+6个字母:A,B,C,D,E,F =总共16个字符),每个字符都可以编码4位组合之一。

    So when you get 64 hex for sha256, you’re getting directly 64 x 4 = 256 bits.

    因此,当您为sha256获得64十六进制时,您将直接获得64 x 4 = 256位。

    As you can see, a 0 in hex is actually 0000 in binary. 7 is 0111. So the hash of Test1234 is the following in binary:

    如您所见,十六进制的0实际上是二进制的0000。 7是0111。因此Test1234的哈希值如下所示:

    Replace 0 by 0000. Replace 7 by: 0111. Replace 4 by 0100. Replace 8 by: 1000. Replace 0 by 0000. Replace F by 1111. Replace B by 1011…

    将0替换为0000。将7替换为:0111。将4替换为0100。将8替换为:1000。将0替换为0000。将F替换为1111。将B替换为1011…

    So instead of : 0 7 4 8 0 F B … in Hex

    因此,用十六进制代替:0 7 4 8 0 FB…

    you get: 0000 0111 0100 1000 0000 1111 1011 … in Binary

    您会得到:0000 0111 0100 1000 0000 1111 1011…in Binary

    In summary, each hex digit is just a direct mapping of 4 bits in binary.

    总而言之,每个十六进制数字只是二进制形式的4位直接映射。

    反转安全哈希有多难? (How hard it it to reverse a secure hash?)

    Image for post

    A secure hash function should act like a random number generator. So if you change a tiny bit the input, half of the bits will change randomly at the output.

    安全散列函数的作用应类似于随机数生成器。 因此,如果您更改一点输入,则一半的位将在输出处随机更改。

    Actually even just changing one character from the input. Let’s say we try test1234 with small t instead of capital T.

    实际上,甚至只是从输入中更改一个字符。 假设我们尝试用小t代替大写T来测试test1234。

    You get the following hash of test1234:

    您得到以下test1234的哈希值:

    937E8D5FBB48BD4949536CD65B8D35C426B80D2F830C5C308E2CDEC422AE2244

    937E8D5FBB48BD4949536CD65B8D35C426B80D2F830C5C308E2CDEC422AE2244

    Nothing to do with the first hash of Test1234

    与Test1234的第一个哈希表无关

    07480FB9E85B9396AF06F006CF1C95024AF2531C65FB505CFBD0ADD1E2F31573

    07480FB9E85B9396AF06F006CF1C95024AF2531C65FB505CFBD0ADD1E2F31573

    So if a hash is very secure that it mixes well the bits before you get an output, it will cost you 2^bits to break the hash.

    因此,如果散列非常安全,可以在获得输出之前很好地混合比特,那么将花费2比特来破坏散列。

    So for 256 bits hash, you would need to try 2²⁵⁶ times that’s equal to 1.1x10⁷⁷ tries before you find an input (Almost the number of atoms in the universe!)

    因此,对于256位哈希,您将需要尝试2²倍的次数,等于1.1x10倍的尝试次数,然后才能找到输入(几乎是宇宙中的原子数!)

    If you don’t believe me, here is a challenge for you: try to find the text that generates the following hash, go to this website and try, type any random text as input, and see how close you can get to the following hash:

    如果您不相信我,这对您来说是一个挑战:尝试查找生成以下哈希的文本, 访问此网站并尝试 ,输入任意随机文本作为输入,并查看离以下内容有多接近杂凑:

    76B7EA4ADA84E973F394C9F5E6CDA618FC6CC246B2130B0BD2FE6092493D84A4

    76B7EA4ADA84E973F394C9F5E6CDA618FC6CC246B2130B0BD2FE6092493D84A4

    I would say, good luck! If you just get the starting 76B7E you would be very lucky! Let me know in the comments how many hex you manage to break?

    我会说, 祝你好运 ! 如果您只是获得入门的76B7E,您将非常幸运! 在评论中让我知道您设法破解了多少个十六进制?

    翻译自: https://medium.com/@assaad.moawad/hash-functions-explained-in-a-simple-way-bb08d508932

    哈希表 哈希函数 时间

    展开全文
  • 哈希查找的第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果有一个数组大小为M,那么就需要一个能够将任意键转换为该数组范围内的索引(0~M-1)的哈希函数哈希函数需要易于计算并且能够均匀...

    哈希查找的第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果有一个数组大小为M,那么就需要一个能够将任意键转换为该数组范围内的索引(0~M-1)的哈希函数。哈希函数需要易于计算并且能够均匀分布所有键。根据关键字的结构和分布的不同,可构造出许多不同的哈希函数。

    在实际中,键并不一定都是数字,更有可能是字符串,还有可能是几个值的组合等。

    1.整数

    获取整数哈希值做常用的方法是使用除留余数法。即对于大小为素数M的数组,对于任意整数k,计算k除以M的余数。M一般取素数。

    2.字符串

    将字符串作为键的时候,我们也可以将它作为一个大的整数,采用除留余数法。也可以将组成字符串的每一个字符取值然后进行哈希。

    参考

    1.浅谈算法和数据结构: 十一 哈希表

    展开全文
  • Hash(哈希)相关知识(哈希函数、哈希查找)

    万次阅读 多人点赞 2020-05-18 21:04:17
    函数特性1.1 基本的哈希函数1.2 加密的哈希函数2. 常见的哈希函数构造法2.1 直接寻址法2.2 数字分析法2.3 平方取中法2.4 折叠法2.5 随机数法2.6 除留余数法2.7 加密哈希函数3. 哈希函数总结二. 哈希查找1. 操作步骤...

    前言

    • 因为本人是小白(小菜鸡),所以有些地方说的可能不是很准确,大家可以参考一些很厉害的博主,在评论区指出我写的不对的地方。
    • 本来是想要单独写一下Hash(哈希)查找算法,但后来想到Java和区块链的入门里面都涉及到Hash,所以就说一下自己对Hash的理解。
    • 在写的过程中,有涉及到密码学的相关概念,我尽力用举例子的方式让读者明白,如果觉得我有哪里说的不准确,可以查找相关文献进行更深层次的理解,以免我误人子弟,顺便谢谢大家啦!

    一. 哈希函数

    1. 函数特性

    1.1 基本的哈希函数

    • 哈希函数是一个数学函数,特性有下面三点:
    • 其输入可为任意大小的字符串。
    • 它产生固定大小的输出。
    • 它能进行有效的计算,就是说对于特定的输入字符串,在合理时间内,能够计算出哈希函数的输出,对n位的字符串,哈希值计算的复杂度是O(n)。

    1.2 加密的哈希函数

    • 主要有附加的三个特性(相关文字说明源于BITCOIN AND CRYPTOCURRENCY TECHNOLOGIES 区块链技术驱动金融-数字货币与智能合约技术):
    • 碰撞阻力:对于两个不同的输入,能够产生相同的输出,就像y=x2,key1≠key2,但是产生了H(key1)=H(key2)。实际上世界上根本不存在具有防碰撞特性的哈希函数,现在技术上所用的加密哈希函数只不过是还没有找到碰撞的函数,就像之前人们都用的MD5,在前几年找到了碰撞后就逐渐淡出市场。
    • 隐秘性:如果我们无法通过输出y=H(x)来找到输入x,那么就保证了隐秘性。但要满足这样条件的x必须取自一个非常大的集合,否则x将很容易就被获取。例如,我们抛硬币,只需要知道结果就很容易穷举出x的确定值。
    • 谜题友好:这个特性听起来是人畜无害的,其实用我的话来解释就是盲目的穷举一个巨大无比的数据集,而要求是要找到一个小区域内的值。用人话来说就是,给你一个地球这么大的区域,让你通过穷举来寻找你家小区或者一个超市或者一个城市的区域,这个所要寻找的区域往往越小,难度越高(正常人都能看出来)。而这个谜题取自哪里也非常重要,谜题往往取自高阶最小熵分布,这样就保证了没有捷径能走。

    2. 常见的哈希函数构造法

    • 相信大家都接触过数据结构,在那里面讲到过很多种构建哈希函数的方法和存储方式,咱也列举一下(有的是复制粘贴的,因为在数据结构中都有讲到)。
    • 百度词条哈希表和相应问题处理方法

    2.1 直接寻址法

    • 取关键字或关键字的某个线性函数值为散列地址。即hash(k) = k 或 hash(k) = a · k + b,其中a、b为常数(这种散列函数叫做自身函数)。

    2.2 数字分析法

    • 这种方法是对重复性比较高的位进行查找,然后多选几位组成哈希地址,避免冲突增加。

    2.3 平方取中法

    • 取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

    2.4 折叠法

    • 将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。

    2.5 随机数法

    • 选择一个随机函数,取关键字的随机函数值作为它的哈希地址,即H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时的场合。

    2.6 除留余数法

    • 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key MOD p(p<=m)。
    • 不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

    2.7 加密哈希函数

    • 这里介绍安全哈希算法(SHA - 256),主要是被比特币采用的哈希函数。
    • 与它相关的概念叫压缩函数(compression function)。在通用术语中,将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数,这种转换过程叫MD(Merkle-Damgard)变换。一般来说这种基础型,可用于固定长度,并且具备碰撞阻力的哈希函数就是压缩函数。
    • SHA - 256就是利用了压缩函数将一个768位的输入压缩成256位的输出,每一个区块的大小是512位。
    • 对于以上所说的知识,可以在百度上搜,或者看区块链的书。

    3. 哈希函数总结

    • 哈希函数并不是越复杂越好,而是根据需求进行设计和使用,因为哈希函数越复杂,时间消耗越长,对性能也有一定的影响。

    二. 哈希查找

    1. 操作步骤

    • 用给定的哈希函数构造哈希表。
    • 根据选择的冲突处理方法解决地址冲突。
    • 在哈希表的基础上执行哈希查找。

    2.哈希表的查找

    • 哈希表的查找效率主要取决于哈希函数的构造方式、处理冲突的方式和装填因子。

    2.1 哈希冲突

    • 其实原理就是上面讲的碰撞,为了处理冲突,有这几种处理方法:
    • 百度词条哈希查找,这里面讲的还可以,有资源的可以在网上找具体操作,当然数据结构中的hash也讲过这几个方法,可以去找课件和书。

    2.1.1 开放寻址法

    • 如果产生冲突,就找个空地址塞进去,当然要保证散列地址足够大。
    • 这种方法细分为3种,分别是线性探测再散列、二次探测再散列、伪随机探测再散列,详细的设计方法和原理在上面的链接里也有。

    2.1.2 链地址法

    • 将所有同关键字的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针。
    • 这种方法有点像用链表构成树。

    2.1.3 再散列法

    • 提前准备多个散列函数,如果其中一个找不到合适的位置,那就换一个散列函数。

    2.1.4 建立公共溢出区

    • 粗暴方式,只要发生冲突就填进公共溢出区。

    2.2 装填因子

    • 散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度
    • α是散列表装满程度的标志因子。
    • 由于表长是定值,α与填入表中的元素个数成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
    • 实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。

    三. 总结

    • HashMap就是由数组+链表组合成的,也就是链地址法,在这篇里主要讲的就是哈希相关的东西,HashMap改天再说。
    • 哈希函数的构造不是越复杂越好,合适就行了,因为不同的应用由不同的需求,根据需求选择合适的结构就行了,性能方面也要考虑,例如HashMap只要尽量的减少它的链表就能提高它执行的性能。
    展开全文

空空如也

空空如也

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

哈希函数