精华内容
下载资源
问答
  • Hash表的平均查找长度ASL计算方法

    千次阅读 2019-07-11 10:13:24
    Hash表的“查找成功的ASL”和“查找不成功的ASL” ASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子(用来计算表长的): 0.7 处理冲突: 线性探测再...

    Hash表的“查找成功的ASL”和“查找不成功的ASL”
    ASL指的是 平均查找时间

    关键字序列:(7、8、30、11、18、9、14)

    散列函数:
    H(Key) = (key x 3) MOD 7

    装载因子(用来计算表长的):
    0.7

    处理冲突:
    线性探测再散列法

    查找成功的ASL计算方法:

    因为现在的数据是7个,填充因子是0.7。所以数组大小=7/0.7=10,即写出来的散列表大小为10,下标从0~9。
    第一个元素7,带入散列函数,计算得0。
    第二个元素8,带入散列函数,计算得3。
    第三个元素30,带入散列函数,计算得6。
    第四个元素11,带入散列函数,计算得5。
    第五个元素18,带入散列函数,计算得5;此时和11冲突,使用线性探测法,得7。
    第六个元素9,带入散列函数,计算得6;此时和30冲突,使用线性探测法,得8。
    第七个元素14,带入散列函数,计算得0;此时和7冲突,使用线性探测法,得1。
    所以散列表:

    地址0
    key7

    所以查找成功的计算:
    如果查找7,则需要查找1次。
    如果查找8,则需要查找1次。
    如果查找30,则需要查找1次。
    如果查找11,则需要查找1次。
    如果查找18,则需要查找3次:第一次查找地址5,第二次查找地址6,第三次查找地址7,查找成功。
    如果查找9,则需要查找3次:第一次查找地址6,第二次查找地址7,第三次查找地址8,查找成功。
    如果查找地址14,则需要查找2次:第一次查找地址0,第二次查找地址1,查找成功。
    所以,ASL=(1+2+1+1+1+3+3)/ 7=12/ 7

    查找不成功的ASL计算方法:

    鉴于网络上有各种版本,本人认为此种计算方法比较合理。验证实例可以参考2010年的计算机408考研真题的第一道计算大题和答案。

    1. 定义什么叫查找不成功
    举个例子来说吧。在已知上面散列表的基础上,如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5。此时在地址为5的地方取出那个数字,发现key=11,不等于4。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为6的值,发现key=30,依然不等。这个时候到了地址为6,但是依然没有找到。那么就说明根本就没有key=4这个关键字,说明本次查找不成功。注意:为什么到地址6?因为散列函数中有 mod7 ,对应的地址为06,即06查找失败的查找次数。
    再举一个例子。查找key为0的关键字,根据散列函数可以计算Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字,发现key=7,不等于0。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为1的值,发现key=14,依然不等。这个时候到了地址为3,发现为空,依然没有找到。所以停止查找,本次查找不成功。因为如果key=0这个关键字存在的话,依照冲突处理函数,就一定能找到它。总不能丢了吧。

    2. 根据第一点定义的不成功,依次推下去:
    查找地址为0的值所需要的次数为3,
    查找地址为1的值所需要的次数为2,
    查找地址为2的值所需要的次数为1,
    查找地址为3的值所需要的次数为2,
    查找地址为4的值所需要的次数为1,
    查找地址为5的值所需要的次数为5,
    查找地址为6的值所需要的次数为4。
    3.计算
    查找不成功ASL=(3+2+1+2+1+5+4)/ 7=18/ 7

    展开全文
  • Geohash长度与对应精度

    千次阅读 2019-07-23 08:45:54
    转自:... geohash长度 Lat位数 Lng位数 Lat误差 Lng误差 km误差 1 2 3 ±23 ±23 ±2500 2 5 5 ± 2.8 ±5.6 ±630 3 7 8 ± ...

     

    转自:https://segmentfault.com/a/1190000002513514

    geohash长度Lat位数Lng位数Lat误差Lng误差km误差
    123±23±23±2500
    255± 2.8±5.6±630
    378± 0.70± 0.7±78
    41010± 0.087± 0.18±20
    51213± 0.022± 0.022±2.4
    61515± 0.0027± 0.0055±0.61
    71718±0.00068±0.00068±0.076
    82020±0.000086±0.000172±0.01911
    92223±0.000021±0.000021±0.00478
    102525±0.00000268±0.00000536±0.0005971
    112728±0.00000067±0.00000067±0.0001492
    123030±0.00000008±0.00000017±0.0000186
    展开全文
  • 最近做了几个题目,又学到新的知识点,是有关Hash长度扩展攻击 参考了一波P牛的博客还有我们学校的博客: http://www.cnblogs.com/pcat/p/5478509.html ... 正文 ...

    最近做了几个题目,又学到新的知识点,是有关Hash长度扩展攻击

    参考了一波P牛的博客还有我们学校的博客:
    http://www.cnblogs.com/pcat/p/5478509.html
    http://www.bxsteam.xyz/2017/05/23/hash%e9%95%bf%e5%ba%a6%e6%89%a9%e5%b1%95%e6%94%bb%e5%87%bb/

    正文

    实验吧 让我进去

    既然说是admin才能进去,那我就先抓个包,看一下包里面是否又要改的东西。。。。
    发现有一个source=0,毫不犹豫把它改为1,
    这里写图片描述
    发包获得源代码

    if (urldecode($username) === "admin" && urldecode($password) != "admin") {
            if ($COOKIE["getmein"] === md5($secret . urldecode($username . $password))) {
                echo "Congratulations! You are a registered user.\n";
                die ("The flag is ". $flag);

    看一下源代码发现这里有urldecode但是不会太影响,最最关键的应该是md5($secret . urldecode($username . $password))这个东西

    这里写图片描述

    关键代码就这一部分而已,其余的什么setcookie都没啥用,再看看包里面的内容,发现这个点,谷歌搜一波发现P牛的解析
    这里写图片描述
    而后按照他的步骤安装了hashpump,最后把题目完成
    先是新的签名,把它设置到cookiegetmein里。
    第二个先把\x替换为%后,post提交

    我最后发的包

    POST /web/kzhan.php HTTP/1.1
    Host: ctf5.shiyanbar.com
    User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:58.0) Gecko/20100101 Firefox/58.0
    Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
    Accept-Language: zh-CN,zh;q=0.8,zh-TW;q=0.7,zh-HK;q=0.5,en-US;q=0.3,en;q=0.2
    Accept-Encoding: gzip, deflate
    Referer: http://ctf5.shiyanbar.com/web/kzhan.php
    Content-Type: application/x-www-form-urlencoded
    Content-Length: 227
    Cookie: sample-hash=571580b26c65f306376d4f64e53cb5c7; source=1; Hm_lvt_34d6f7353ab0915a4c582e4516dffbc3=1520492842,1520518767,1520572017; Hm_cv_34d6f7353ab0915a4c582e4516dffbc3=1*visitor*132367%2CnickName%3A0verWatch; Hm_lpvt_34d6f7353ab0915a4c582e4516dffbc3=1520584378; PHPSESSID=qljr4nu3o68169kr8ejb2htp87;getmein=7db18a2831cdab27425f299ca09f034e;
    Connection: close
    Upgrade-Insecure-Requests: 1
    
    username=admin&password=admin%2580%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%2500%25c8%2500%2500%2500%2500%2500%2500%2500abc

    cumt平台上的一道题目

    is hash safe??

    点进去发现要admin才能看,常规操作抓包,看里面有没有要改的,果不其然,把guest改为admin发现没啥用。。。。
    这里写图片描述

    然后再看看页面源代码啥都没有,那应该就是源码泄露了,尝试.swp
    发现泄露文件
    放进kali里面用vim -r 命令复原源代码文件
    得到源码
    这里写图片描述

    跟那个实验吧的题目很相似,但又有不同,实验吧那一题是有两个字符串连接符,然后使其长度为20位,发现role是guest
    于是我们来hashpump一波,根据提示密文长度为13,并且要绕过admin字符串,于是得到
    这里写图片描述
    抓包发送,得到flag
    这里写图片描述

    小结

    怎么说呢,这几个题好像只考了工具怎么使用,但是一些必要的条件还是要自己找出来的,通过抓包之类的,还有一点点的代码审计,有些地方还是有些不懂,过段时间再继续完善一下自己的体会吧。。。。

    展开全文
  • 主要介绍了PHP实现的各类hash算法长度及性能测试,结合具体实例形式分析了php hash计算的相关操作技巧,需要的朋友可以参考下
  • 其实好多查询搜索的底层都是利用hash实现最快O(1)时间复杂度。hash的概念课本上,网上有甚多。其中,hash函数实现方法是让我最觉得好奇的。 hash函数:直接寻址法,直接定址法是以数据元素关键字k本身或它的线性...

            在学习PHP数组底层实现原理的时候,发现就是通过hash表的方法实现。其实好多查询搜索的底层都是利用hash实现最快O(1)时间复杂度。hash的概念课本上,网上有甚多。其中,hash函数实现方法是让我最觉得好奇的。

            hash函数:直接寻址法,直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址,    实际生活中,关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费,因此这种方法适应性并不强

    数字分析法、数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

    平方取中法,

    这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方,然后根据可使用空间的大小,选取平方数是中间几位为哈希地址。

    哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别,平方值的中间几位和这个数的每一位都相关,则对不同的关键字得到的哈希函数值不易产生冲突,由此产生的哈希地址也较为均匀。

    折叠法,所谓折叠法是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位),这方法称为折叠法。

    随机数法,

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

    那么对p 的选择,关键字不仅可以通过直接对取模,还可以在上述数字分析,平方取中,折叠之后,在进行取模。这样使得关键字在通过hash函数映射到内存单元的任意地址是均匀的,减少冲突。

    在取模的过程中对P为什么要使用质数或素数呢?

    因为质数是只有1和他本身的因子。而合数除了1和他本身外还有其他因子。这样在取模的时候,就会出现相同的hash地址,进而增加冲突。  b = ak +n   n为取余之后的值,那么当a为合数的时候,同样是n,k的取值或b的取值是密集,增加冲突。可以参考博客:为什么求模运算要用素数(质数)—— 哈希表设计

    关于hash函数的其他方法介绍,可以学习:哈希函数的构造方法

    展开全文
  • 成功的ASL很简单,就是首先确定你要找的那个值,然后用hash进行查找计算,如果直接找到就是1次,如果hash(不一定就是原来的hash)的计算不止一次,就按你找到总共的次数计入。然后再套用公式计算就可以了,公式如下...
  • 用MD5实现hash长度扩展攻击 By Assassin

    千次阅读 2017-04-28 21:48:11
    今天心血来潮,看到了扩展攻击,猛然想到了之前看的扩展攻击的原理还没有弄懂,这里补充一下,hash长度扩展攻击到底是怎么实现的。题目首先从实验吧上面见到的经典的题目,下面给出源码$flag = "flag{flag is here}...
  • 计算hash值的方法

    千次阅读 2020-11-28 17:22:57
    计算hash值得方法: 对于key的hashCode做hash操作,无符号右移16位然后做异或运算。 还有平方取中法,伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。 集合中的初始化容量(必须...
  • hash表】hash表平均查找长度(ASL)

    千次阅读 2019-08-28 14:00:41
      hash 表在处理 collision 的时候有...  本文记录使用开链法的情况下,Hash 表查找成功和查找不成功的平均查找长度(ASL - ),其他方法同理。   首先开链法是指,每一个表格元素维护一个list,hash function...
  • Hash表的“查找成功的ASL”和“查找不成功的ASL” ASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数:  H(Key) = (key x 3) MOD 7 装载因子:  0.7 处理冲突:线性探测再散列法 ...
  • 什么是hash算法及hash扩展攻击http://www.freebuf.com/articles/web/69264.htmlhttp://www.freebuf.com/articles/web/31756.html大部分教程都是直接告诉什么是hash扩展攻击,但都没讲为什么(对小白很不友好),其实...
  • 哈希(Hash长度扩展攻击

    千次阅读 2019-03-22 23:40:49
    以实现字符串abcde的md5的值的计算为例 切换到win 在winhex中打开并输入如下内容 2.对消息进行补位,使得位长mod512得值为448,即len(message) % 512 == 448(单位为bit)。补位的方式为二进制情况下数据后面加上1...
  • Java计算文件的hash

    万次阅读 多人点赞 2017-12-21 14:04:02
    如何知道一个文件是否改变了呢?当然是用比较文件hash值的方法,...我用的是MD5算法,java中,计算MD5可以用MessageDigest这个类。 下面提供两个工具类(任选其一即可) 第一个工具类: 代码如下: package com.te
  • 一、线性探测再散列法 Hash表: 元素的值(value)和在数组中索引位置(index)有一个确定关系 Index = Hash(key) ==&gt; y = f(x) Index有可能相同,怎么处理冲突?不同的老师、教材在“处理冲突”上可能会有不同的...
  • 文件hash算法,对大文件进行hash计算

    热门讨论 2009-12-25 14:37:15
    文件hash算法,对大文件进行hash计算,并可以返回base64编码.文件hash算法,对大文件进行hash计算,并可以返回base64编码.
  • SHA-256:一种哈希函数...这个摘要相当于是个长度为32个字节的数组,通常用一个长度为64的十六进制字符串来表示。 String password = "123"; StringBuilder sb = new StringBuilder(); MessageDigest object = Me...
  • MySQL中计算索引长度

    千次阅读 2016-10-12 22:08:15
    首先,我们来看一道题目,针对表t,包含了三个字段a、b、c,假设其默认值都非空...因为查询缓冲,hashkey值,是以sql语句来计算的,且区分大小写,所以在写SQL语句的时候,尽量保存一致,防止相同的查询被缓存多次。
  • 哈希长度扩展攻击是一个很有意思的东西,利用了 md5、sha1 等加密算法的缺陷,可以在不知道原始密钥的情况下来进行计算出一个对应的 hash 值。  这里是 ISCC 中题目中的 admin.php 的算法: $auth = false; if ...
  • IPFS-文件HASH计算

    千次阅读 2020-05-20 15:41:30
    IPFS采用了SHA2-256这个安全级别还算高的算法,对任意长度的内容,生成的HASH长度固定,都是32个字节。 在Linux下,直接用sha256sum可以计算SHA2-256格式的HASH值: [root@VM_0_14_centos bin]# sha256sum ...
  • Hash值的长度短至64一bits或72一bits即可达到2^64或者2^72的安全度。文中研究表明,在数字签名中由于存在来自签名者的生日攻击,如此短的Hash值并不能达到规定的安全度。并提出了一个简单的修改方案,使得在不增加...
  • 简单计算一下:hash(5)=5, 所以数据5应该放在hash表的第5个槽里;hash(28)=1,所以数据28应该放在hash表的第1个槽里;hash(19)=1,也就是说,数据19也应该放在hash表的第1个槽里——于是就造成了碰撞(也称为冲突,...
  • 计算两个字符的hash值工具类,输入项为(string1,string2,hashAlgorithm),根据hash算法计算string1和string2的hash值,再将两个hash值拼接后再计算出一个hash值输出。hashAlgorithm名为配置文件可配。 这是师傅给...
  • perl中获得哈希(hash长度的办法

    万次阅读 2009-03-19 16:31:00
    $length = keys %hashname; 则$length中得到的直接是该hash的key的个数。
  • hash表的实现主要包括构造哈希和处理哈希冲突两个方面: (1) 对于构造哈希来说,主要包括直接地址法、平方取中法、除留余数法等。 (2) 对于处理哈希冲突来说,最常用的处理冲突的方法有开放定址法、再哈 希法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 250,180
精华内容 100,072
关键字:

如何计算hash长度