精华内容
下载资源
问答
  • HASH 随机数

    万次阅读 2014-05-17 17:00:29
    本文主要介绍hash与多值

    本文主要介绍一下hash与多值hash,然后在讨论一下支撑hash的伪随机数生成器。不感兴趣者可以走了……


    一:hash 与 多值hash:

    野史

    第一次见到hash,是在算法导论里看到的,其中的桶排序就是使用了此类思想,当然也有专门介绍hash的章节。感觉却是高明。后来在sqlseveral中也经常接触,毕竟作为join的一种优化方法经常都很靠谱。而多值hash则是在《数学之美》中接触到的,其中用作垃圾邮件过滤器。两个字:神奇。后来在一些分类统计中经常使用,感触更深。hash的本质就是用一个函数根据内容本身计算出内容的存储位置然后存储之,取的时候自然也就是看到内容立刻就能计算出(而不是找出)目标的位置。

    碰撞

    这个计算位置的函数先放一下,假设已经有了,而且内容无规律,我们选择了随机函数;先讨论碰撞问题。假设在一个100万的序列中已经有1万个位置被占满,那么再放一个元素时他会落到别人的位置上的概率是1%。这就是碰撞的概率了。当然如果内容存在一定规律,我们不使用随机函数作为hash函数可能会完全不碰撞并且位置使用率很高,例如:如果要计算一篇文章的所有单字的字频统计,就可以使用汉字的编码所代表的数字做一个线性平移。但如果统计词组的频率呢?四字成语所代表数字可不小(2的64次方)。回到之前的问题,在一个100万的序列中存储一个元素时碰撞概率为1%的问题。如果我们把每个元素存放在2个随机的位置会发生什么呢?明显需要两个位置同时碰撞才会使信息真正遗失,而此时概率为0.01%。方法很简单,但有效。

    最优多值

    这个多值是不是月多越好呢?明显不是,当一个元素需要1千万个位置时恐怕那个百万序列存不了几个数字。在假设随机函数完全随机的情况下,我们要在一个M的序列中存放N个元素,每个元素占据K个位置。最优K一个近似的偏小的估计值是M/N/e(也就是那个接近2.7的无理数)。后来我找到了一个更精确的计算方法,但结果不那么容易记,在此也不说了。如果在实验时发现上面的最优值与实际测试出入较大,在怀疑它之前,先怀疑自己的随见函数是否真的是足够随机。这便是下面要讲的——构建一个好的随机数发生器。


    二:随机数发生器

    再看导论之前,用过随机数发生器,看过导论之后写过。至于那些七大类八大纲就不扯了,说一下我用的第一个hash函数和最让我满意的一个。

    乘法

    乘法是指用一个无理数(比如sqrt(6))与需要存储的内容所对应的唯一值(如ASCII码代表的值)进行乘法后取小数部分,然后再用这个小数乘以散列长度。但我在使用的时候发现其碰撞概率比我的估计值要大了几个数量级,最后看了几种不同随机数产生方法,把目标放在md5上。随机数算法要尽可能简单,下面是个逻辑过程,没有照抄md5,但很类似。散列长度2**24.【就是一些移位与异或,符号采取的是Python中的】

    1. a = ASCII(string); a1 = 0

    2. if a <2**64,a = a*138647902547865326901【随意一个大数,别取那些2^n的】

    3.while (a>0):

    4.       a1 = a1^(a&(2**24-1));  a = a>>24

    5.return(a1)

    这个方法还是不错的,在我的实验中,得到的碰撞概率比完全随机假设时的理论结果还要低。这个原因是因为多值hash时,多个随机数发生器对应同一个种子时更倾向于产生不同的位置,相互之间碰撞概率低于随机情况。至少目前我是这么解释。

    检验

    怎么说明随机函数是否随机呢?看分布图等很有说服力,但是不够严谨。在一过程中我之所以能够区分出孰优孰劣也是因为下面介绍的一个方法。

    假设一个长度为M的散列的散列函数完全随机,存储了N个不同元素后,其中有K个位置被占据。忽略高阶小量(三个或更多元素存在同一个位置),其中某一个元素发生碰撞的概率为(N-K)/N。而另一方面在在这个元素没有放进去之前,(K-1)位置已经存储元素(小概率被忽略),总长度M,碰撞概率(k-1)/M。于是根据我们存储的唯一元素个数N,占据位置数量K,和散列长度M,我们可以估计出两个概率,而它们的含义相同【(N-K)/N=(k-1)/M】。即 这两者也接近 函数越接近随机。当N已经较大时(比如大于M的0.01倍,太大时高阶小量就不能忽略了),在这个残酷的检验中MD5的方法比乘法以及另外一个求余法要好了不少。

    结语

    上周就说要写的,今天终于写完了,下次谈谈Hadoop的吧,哎,被老板拉去做些装机的苦力活,不知道会遇到些什么困难,又会学些什么东西。

    展开全文
  • 浏览器hash与history

    万次阅读 2021-04-16 11:08:18
    hash 改变hash会设置历史记录,可以通过hash进行页面传参,但hash变化不会先服务器发起请求, 但是使用了它,就禁用了#的锚点定位 设置hash window.location.hash 设置或读取 监听hash变化 window.addEventListener...

    hash

    改变hash会设置历史记录,可以通过hash进行页面传参,但hash变化不会先服务器发起请求,
    但是使用了它,就禁用了#的锚点定位

    设置hash

    window.location.hash 设置或读取

    监听hash变化

    window.addEventListener(‘hashchange’,function(){
    // 监听hash变化,点击浏览器向前向后切换
    });

    示例代码

    <!DOCTYPE html>
    <html lang="en">
      <head>
        <meta charset="UTF-8" />
        <title></title>
        <style></style>
      </head>
      <body>
        <button id="btn">随机彩票</button>
        <div id="container"></div>
        <script>
          var oContainer = document.getElementById("container");
          var oBtn = document.getElementById("btn");
          var obj = {};
    
          oBtn.addEventListener("click", function () {
            var arr = [];
    
            for (var i = 0; i < 7; i++) {
              arr.push(Math.floor(Math.random() * 35 + 1)); /*彩票1-35*/
            }
    
            var random = Math.random();
            location.hash = random; /*给hash设置一个随机数 用来区分页面内容*/
            obj[random] = arr; /*存为变量属性*/
            oContainer.innerHTML = arr; /*放到页面*/
            //        console.log(obj);
          });
    
          window.addEventListener("hashchange", function () {
            /*hash值改变事件*/ var str = location.hash.substring(
              1
            ); /*取hash值  1到最后  去掉# */
            if (str) {
              /*如果有值*/
              oContainer.innerHTML = obj[str]; /*取值*/
            }
          });
        </script>
      </body>
    </html>
    

    history

    可以进行复杂页面传参
    history不仅可以将参数写入url也可写入特定的对象

    设置history

    window.history.pushState(state,title,url);
    state: 需要保存的数据
    title: 标题,一般为null
    

    监听回退事件

    window.onpopstate=function (e) {/*浏览器回退触发事件*/
            xxxx.innerHTML=e.state;/*设置*/
    }
    
    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title></title>
        <style>
     
        </style>
    </head>
    <body>
     
     
    <button id="btn">随机彩票</button>
    <div id="container"></div>
    <script>
        var oContainer=document.getElementById('container');
        var oBtn=document.getElementById('btn');
     
        oBtn.addEventListener('click',function () {
            var arr=[];
            for (var i=0;i<7;i++){
                arr.push(Math.floor(Math.random()*35+1));
            }
            oContainer.innerHTML=arr;/*放到页面*/
            history.pushState(arr,'','/history.html');/*存历史记录*/
        });
        
        window.onpopstate=function (e) {/*浏览器回退触发事件*/
            oContainer.innerHTML=e.state;/*设置*/
        }
    </script>
    </body>
    </html>
    
    展开全文
  • Windows下LM-Hash与NTLM-Hash生成原理

    万次阅读 2015-12-06 17:02:00
    LM-Hash与NTLM-Hash在windows下通过SAMInside提取到的密码Hash时,可以看到有两条,分别是LM-Hash和NT-Hash,这是对同一个密码的两种不同的加密方式,下面对其生成原理做个实验。Windows下LM-Hash生成原理这里用实例...

    LM-Hash与NTLM-Hash

    在windows下通过SAMInside提取到的密码Hash时,可以看到有两条,分别是LM-Hash和NT-Hash,这是对同一个密码的两种不同的加密方式,下面对其生成原理做个实验。

    Windows下LM-Hash生成原理

    这里用实例展示LM-Hash的具体产生过程。

    我使用的明文口令是“123993”,可以看到在使用SAMInside提取出来的LM-Password是 < Disabled >的形式,这里是因为win7系统禁用了LM方式。
    使用如下方法启动:
    依次打开:控制面板>>所有控制面板项>>管理工具>>本地安全策略,再依次打开>>本地策略>>安全选项
    打开以下截图中的“策略”,并将“已启用”修改为“已禁用”。单击“应用”后再点击“确定”。
    因为该策略要求修改密码后生效,所以我需要修改密码。

    这里写图片描述

    这里写图片描述

    我将密码修改为123994,此时Administrator用户的LM-Password不再显示< Disabled >,并且获得其LM-Hash值FAE8BB9ECB799902AAD3B435B51404EE。

    这里写图片描述

    这种加密过程的第一步是将明文口令转换为其大写形式,接下来123994大写转换后仍为它本身,第二步是将字符串大写后转换为16进制字符串
    这里使用UltraEdit编辑器将123994转换为16进制字符串。
    在UltraEdit编辑器输入123994后右键选择“十六进制编辑”选项,如下图所示。
    【误区:使用win7自带的计算器并选择程序员模式,将十进制的123994转换为16进制,结果为1E45A,这里是把123994当作数值转换,没有按要求转换为16进制字符串。】

    这里写图片描述

    这种密码生成规则要求用户的密码最多仅能为14个字符,第三步是密码不足14字节要求用0补全。转换后的十六进制字符串按照二进制计算只有48bit(12*4),为了满足14字节(112bits)的要求,所以需要补全64bit(16*4)的二进制0,得最终补全后十六进制为:3132333939340000000000000000。
    第四步是将上述编码分成2组7字节(56bits=14*4)的数据,分别为31323339393400和00000000000000。
    第五步是将每一组7字节的十六进制转换为二进制,每7bit一组末尾加0,再转换成十六进制组成得到2组8字节的编码
    下图将31323339393400转换为二进制。

    这里写图片描述这里写图片描述

    然后从左到右按照每7bit一组罗列如下:这里务必注意将最前面的11补全为0011
    0011 000
    1 0011 00
    10 0011 0
    011 0011
    1001 001
    1 1001 00
    11 0100 0
    000 0000
    接下来在每7bits一组的末尾添0,再将其转换成16进制。
    0011 0000 -> 3 0
    1001 1000 -> 9 8
    1000 1100 -> 8 C
    0110 0110 -> 6 6
    1001 0010 -> 9 2
    1100 1000 -> C 8
    1101 0000 -> D 0
    0000 0000 -> 0 0
    从上往下得到31323339393400对应的8字节编码:30988C6692C8D000
    同理知00000000000000对应的8字节编码:
    0000000000000000。
    第六步将以上步骤得到的两组8字节编码,分别作为DES加密key为魔术字符串“KGS!@#$% ”进行加密
    该魔术字符串换算成16进制:4B47532140232425。
    从网上下载到DES计算器,依次计算使用30988C6692C8D000和0000000000000000加密4B47532140232425后的密文。

    这里写图片描述

    这里写图片描述

    第七步将两组DES加密后的编码拼接
    得到最终LM-Hash值为:
    FAE8BB9ECB799902AAD3B435B51404EE
    这与SAMInside中的LM-Hash值相同。

    注意:这种加密方法对于输入明文密码是数字、字母或者数字与字母的组合,或者其他如&、%等常用符号均适用;使用UltraEdit获取明文的十六进制字符串

    Windows下NTLM-Hash生成原理

    IBM设计的LM Hash算法存在几个弱点,微软在保持向后兼容性的同时提出了自己的挑战响应机制,NTLM Hash便应运而生。
    这里同样以上节的明文密码“123994”作为研究对象。首先在UltraEdit中输入123994,然后点击>>编辑>>十六进制函数>>十六进制编辑,
    再点击>>文件>>转换>>ASCII转Unicode,如下图所示获得Unicode字符串为310032003300390039003400,

    这里写图片描述

    开头的FF FE用于标识此文本文件为Unicode编码,参考链接:
    http://my.oschina.net/u/1024767/blog/351792?fromerr=KQ0hrIzn
    http://blog.sina.com.cn/s/blog_815b7fb901010am3.html

    对所获取的Unicode字符串进行标准MD4单向哈希加密,无论数据源有多少字节,MD4固定产生128-bit的哈希值,产生的哈希值就是最后的NTLM Hash。

    从网上下载HashCalc工具,打开后将310032003300390039003400输入数值框中,选择左侧数据格式为十六进制串,去掉HMAC前的对号。选中MD4加密,再点击计算,如下图所示。

    这里写图片描述

    获得MD4加密的哈希值为b648042caad9f1c0cbf5bb5cb66ee88f,
    与SAMInside中的NT-Hash:B648042CAAD9F1C0CBF5BB5CB66EE88F相同。

    展开全文
  • Hash取模一致性Hash

    千次阅读 2017-04-19 16:08:36
    直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如Java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。 但

    取模
    最简单的hash算法

    targetServer = serverList[hash(key) % serverList.size]

    直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如Java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。

    但是问题也很明显,server总数不能轻易变化。因为如果增加/减少memcached server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

    一致性hash
    为了解决这个问题,需要采用一致性hash算法(consistent hash)
    相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

    为了方便理解,可以把这个有限值域理解成一个环,值顺时针递增。
    circle space
    如上图所示,集群中一共有5个memcached server,已通过server的hash值分布到环中。

    如果现在有一个写入cache的请求,首先计算x=hash(key),映射到环中,然后从x顺时针查找,把找到的第一个server作为目标server来存储cache,如果超过了2^32仍然找不到,则命中第一个server。比如x的值介于A~B之间,那么命中的server节点应该是B节点
    image
    可以看到,通过这种算法,对于同一个key,存储和后续的查询都会定位到同一个memcached server上。

    那么它是怎么解决增/删server导致的cache不能命中的问题呢?
    假设,现在增加一个server F,如下图


    此时,cache不能命中的问题仍然存在,但是只存在于B~F之间的位置(由C变成了F),其他位置(包括F~C)的cache的命中不受影响(删除server的情况类似)。尽管仍然有cache不能命中的存在,但是相对于取模的方式已经大幅减少了不能命中的cache数量。

    虚拟节点
    但是,这种算法相对于取模方式也有一个缺陷:当server数量很少时,很可能他们在环中的分布不是特别均匀,进而导致cache不能均匀分布到所有的server上。

    展开全文
  • hash破解-hashcat

    千次阅读 2020-04-29 10:30:14
    hashcat破解hash值自己搭建实验环境:1.了解hashcat2.了解JohnTheRipper3.了解zip试验步骤: 今天分享一个称之为世界上最快的密码破解工具hashcat 在渗透测试中我们经常会碰到一些加密处理的一串hash,有的在线的...
  • HashMap中的hash与rehash

    千次阅读 2018-03-24 16:08:34
    HashMap中的hash与rehash我们知道HashMap中经常用到hash()方法。比如:put()方法中public V put(K key, V value){ if(key==null) return putForNullKey(value) ; int hash=hash(key.hashCode()); ...
  • hash算法原理详解

    万次阅读 多人点赞 2016-05-19 22:35:01
    一.概念 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为...
  • Hash详解

    万次阅读 多人点赞 2018-07-23 10:00:22
    Hash(哈希) Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。JAVA函数hashCode()...
  • 数据结构 Hash表(哈希表)

    万次阅读 多人点赞 2018-05-20 01:23:34
    什么是Hash表 要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引查找值进行比较。那么...
  • 开源hash代码uthash的原理用法

    千次阅读 2014-02-05 15:49:03
    本文从以下两篇文章参考整理而来: http://houjixin.blog.163.com/blog/static/356284102013101310454673/ ... 0.数据结构 uthash是用宏实现的,使用的时候非常方便,只用包含uthash.h即可。
  • GeoHash原理请自行百度 话不多说直接上util代码 import java.util.BitSet; import java.util.HashMap; public class GeoHash { private static int numbits = 6 * 5; final static char[] digits = {'0', '1',...
  • hash

    万次阅读 2019-07-27 17:35:34
    在 Python 中,设置字典的 键值对 时,会首先对 key 进行 hash 已决定如何在内存中保存字典的数据,以方便 后续对字典的操作:增、删、改、查 键值对的 key 必须是不可变类型数据 键值对的 value 可以是任意类型...
  • hash数组

    千次阅读 2018-12-12 12:29:17
    hashhash表的查找/插入/删除的时间复杂度均为o(1), (因为hash表本身是一个数组,查找o(1), 而插入/删除时,根据hash值直接插入/删除) 数组的插入/删除需要移动元素,送、so,,,,,,,,其时间复杂度为O(n), ...
  • Hash

    千次阅读 2011-08-18 18:00:27
    public class HashAlgorithms { /**//** * 加法hash * @param key 字符串 * @param prime 一个质数 * @return hash结果 */ public static int additiveHa
  • Murmurhash 哈希算法 介绍实现

    万次阅读 2019-10-31 15:38:18
    最近在项目代码中看到了一种hash算法,以前没有遇见过,在此记录下来。   一、介绍   MurmurHash 是一种非...其它流行的哈希函数相比,对于规律性较强的key,MurmurHash的随机分布特征表现更良好。—摘自w...
  • GeoHash算法用法

    千次阅读 2020-04-16 11:16:08
    * GeoHash算法 * * 可以到 http://geohash.co/ 进行geohash编码,以确定自己代码是否写错 * * @Description GeoHash字符串编码越长,表示的范围越小,位置也越精确。 * 因此我们就可以通过比较GeoHash匹配的...
  • c开源hash项目 uthash的用法总结

    万次阅读 多人点赞 2019-07-14 21:22:48
    uthash 是C的比较优秀的开源代码,它实现了常见的hash操作函数,例如查找、插入、删除等待。该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论...
  • Hash冲突

    万次阅读 2018-03-28 15:20:34
    hash : 翻译为“散列”,就是把任意长度的输入,通过散列算法,变成固定长度的输出,该输出就是散列值。 这种转换是一种压缩映射,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不...
  • 文件的hash指纹通常作为前端静态资源实现增量更新的方案之一,Webpack是目前最流行的开源编译工具之一,其强大的功能也带来很多坑(当然,大部分麻烦其实都可以在官方文档中找到答案)。 比如,在Webpack编译输出...
  • hash和一致性hash

    千次阅读 2019-07-25 09:19:45
    hash;简单的hash取余 优点: 计算简单,快速定位 缺点: 容错和扩展差,任何的增加机器或减少机器,都会伴随着重新set值 比如原来有五台机器做缓存,现在加一台,那么余5就变成余6,那么所有值都变了 操作不当的话...
  • 字典与hash

    千次阅读 2018-05-25 09:31:51
    ---》 存储位置=hash(键)在查找时,首先对键进行hash运算,把求得的值当做“键-值对”的存储位置,在结构中按照此位置取“键-值对”进行比较,若键相等,则表示搜索成功。在存储“键-值对”的时候,依照相同的hash...
  • 一致性Hash算法是对2^32取模,2^32个点组成的圆环称为Hash环。根据服务节点的IP或者机器名称进行哈希,就能确定每台机器就能确定其在哈希环上的位置; 将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环...
  • hash_map hash_set 详解

    千次阅读 2012-09-12 10:04:49
    1 数据结构:hash_map原理 这是一节让你深入理解hash_map的介绍,如果你只是想囫囵吞枣,不想理解其原理,你倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。 hash_map基于hash table(哈希表)。 ...
  • 一个 object 是可哈希的(hashable),是指这个 object 在其生存期内有一个不变的哈希值(hash value),也就是说同一个object用hash(object)计算出来的值是一样的, 如list 对象,改变了一个元素值之后,同一个list...
  • Hash算法特点

    千次阅读 2020-04-15 16:22:47
    2.2 Hash算法有什么特点 一个优秀的 hash 算法,将能实现: 正向快速:给定明文和 hash 算法,在有限时间和有限资源内能计算出 hash 值。 逆向困难:给定(若干) hash 值,在有限时间内很难(基本不可能)逆推出...
  • ora_hash() get_hash_value 区别

    千次阅读 2016-12-15 11:13:32
    一、ora_hash格式: ora_hash('strings', N, 0 )  strings: 输入值  N:最大hash bucket的值  0:起始hash bucket值,缺省是1 dbms_utility.get_hash_value(‘strings', min, max)  strings:输入值 ...
  • hash.js Javascript/jQuery 解析/监听url hash

    千次阅读 2016-08-16 18:18:49
    1、什么是hashsearch、hashpath 其实那,hashsearch、hashpath这两个词是我自造的。在javascript语言里称url改变该部分不会影响页面重新加载的部分为hash,在后台语言里称之为fragment(碎片)。在这里,我们统称...
  • hash算法比较

    千次阅读 2017-01-13 17:42:37
    常用的hash算法有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等。
  • 真正搞懂hashCode和hash算法

    万次阅读 多人点赞 2021-01-28 19:29:08
    自从搞懂hash,妈妈再也不担心我找不到工作啦
  • redis的hash与string区别

    千次阅读 2017-02-09 13:41:27
    Redis hash 是一个 string 类型的 field 和 value 的 映射表。它的添加、删除操作都是 0(1)(平均操作)。 hash 特别 适合用于存储对象。相较于将对象的每个字段存成单个 string 类型(string 类型可以存储对象序列...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,008,900
精华内容 403,560
关键字:

hash与反hash