精华内容
下载资源
问答
  • JDK8:HashMap源码解析:hash方法

    千次阅读 多人点赞 2018-06-05 01:20:08
    一、概述 我们知道在HashMap中,一个键值对...这里要注意区分三个概念:hashCode值、hash值、hash方法、数组下标 hashCode值:是KV对中的K对象的hashCode方法的返回值(若没有重写则默认用Object类的hashCode方法...

    一、概述

    我们知道在HashMap中,一个键值对存储在HashMap内部数据的哪个位置上和K的hashCode值有关,这也是因为HashMap的hash算法要基于hashCode值来进行。

    这里要注意区分三个概念:hashCode值、hash值、hash方法、数组下标

    hashCode值:是KV对中的K对象的hashCode方法的返回值(若没有重写则默认用Object类的hashCode方法的生成值)

    hash值:是在hashCode值的基础上又进行了一步运算后的结果,这个运算过程就是hash方法

    数组下标:根据该hash值和数组长度计算出数组下标,计算公式:hash值  &(数组长度-1)= 下标。

    我们要讨论的就是上面提到的hash方法,首先他是HashMap类中的一个静态方法,该方法的代码特别简单,只有两行,语法很容易懂,可以其中具体用意确值得好好深入研究下。

    我们首先讨论下数组下标计算过程,这个有助于我们理解hash方法的设计思想

     

    二、数组下标计算

    hash:hash值
    length:数组长度
    计算公式:hash  &(length-1)
    
    若length=16,hash=1,那么下标值计算过程如下:
        0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15,15对应的二进制值为1111
        0000 0000 0000 0000 0000 0000 0000 0001    1的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算,最终结果是1
    
    若length=16,hash=17,那么下标值计算过程如下:
        0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15,15对应的二进制值为1111
        0000 0000 0000 0000 0000 0000 0001 0001    17的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算,最终结果是1
    
    若length=16,hash=33,那么下标值计算过程如下:
        0000 0000 0000 0000 0000 0000 0000 1111    16-1 = 15,15对应的二进制值为1111
        0000 0000 0000 0000 0000 0000 0010 0001    33的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算,最终结果是1
    
    若length=32,hash=1,那么下标值计算过程如下:
        0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31,31对应的二进制值为11111
        0000 0000 0000 0000 0000 0000 0000 0001    1的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算,最终结果是1
    
    若length=32,hash=17,那么下标值计算过程如下:
        0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31,31对应的二进制值为11111
        0000 0000 0000 0000 0000 0000 0001 0001    17的二进制
        0000 0000 0000 0000 0000 0000 0001 0001    上两行进行与运算,最终结果是17
    
    若length=32,hash=33,那么下标值计算过程如下:
        0000 0000 0000 0000 0000 0000 0001 1111    32-1 = 31,31对应的二进制值为11111
        0000 0000 0000 0000 0000 0000 0010 0001    33的二进制
        0000 0000 0000 0000 0000 0000 0000 0001    上两行进行与运算,最终结果是1
    
    
    (1,16)->1、(17,16)->1、(33,16)->1
    (1,32)->1、(17,32)->17、(33,32)->1
    总结:
    hash  &(length-1)的运算效果等同于 hash%length。
    我们知道hashMap的扩容规则是2倍扩容、数组长度一定是2的N次方。假设数组长度不是2的N次方,那么再重复以上的计算过程,就达不到求模的效果了。

    讨论完hashMap数组下标寻址过程后,我们可以得知

    在put(K,V)的时候,会根据K的hash值和当前数组长度求模,得到该键值对应该存储在数组的哪个位置。

    在get(K)的时候,同样会根据K的hash值和当前数组长度求模,定位到应该去数组的哪个位置寻找V。

    按照上面举得例子,put(K,V),多个hash值和数组长度求模之后的结果相同时,大家都存储在数据的同一位置,这种情况也叫hash碰撞,发生了这种碰撞时,大家会以先来后到的方式以链表的方式组织起来,那么也就意味着我在get(K)的时候,虽然能够定位到数组位置,还需要遍历链表,通过equals逐个对比之后才能确定需要返回的V。

    假设hash值都不相同,那么hashMap数组的长度越大,碰撞的机率越小。

    在数组长度为16时,当hash值为1、17、33时,大家都定位到下标1,那么此时我们也可以这么想一下,当我的hashMap数组的长度不变或者不会再变得时候,大于数组长度的hash值(17、33)对我hashMap来讲和hash值1的效果是等同的。

    在数组长度为65535时,当hash值为1、131071、262143时,大家都定位到下标1,那么此时我们也可以这么想一下,当我的hashMap数组的长度不变或者不会再变得时候,大于数组长度的hash值(131071、262143)对我hashMap来讲和hash值1的效果是等同的。

    以上两种场景,如果假设:hash值 = hashCode值,就意味着无论是我们自己定义的hashCode还是默认的hashCode生成方式,大于数组长度的值并没有产生我们想要达到的理想效果(我们希望,不同的hashCode能够让他分布到一个不会碰撞的位置),因为取模之后,他的位置可能至少会和某个小于数组长度的值碰撞。

    什么场景下可以避免碰撞:hashMap数组最大长度可知(要存储的数据不超过数组最大长度),创建时就指定初始容量为最大长度,每个K的hash值各不同,且每个hash值都小于数组最大长度。这种场景有么?有,但是我们大部分的应用场景都不会如此巧合或如此故意而为之。

    再看下我们可能最常用的场景:

    Map<String,Object> user = new HashMap<String,Object>(); // 默认内部数据长度为16
    user.put("name", "kevin");
    user.put("sex", 1);
    user.put("level", 1);
    user.put("phone", "13000000000");
    user.put("address", "beijing fengtai");

    以字符串作为key应该是比较常用的情况了,那么这些K对应的hashCode是什么呢?如果根据hashCode来定位下标的话又是什么?

    System.out.println("\"name\".hashCode()	: " +"name".hashCode());
    System.out.println("\"sex\".hashCode()	: " +"sex".hashCode());
    System.out.println("\"level\".hashCode()	: " +"level".hashCode());
    System.out.println("\"phone\".hashCode()	: " +"phone".hashCode());
    System.out.println("\"address\".hashCode()	: " +"address".hashCode());
    
    System.out.println("--------*****---------");
    
    System.out.println("\"name\".hashCode() & (16 - 1) 	:" + ("name".hashCode() & (16 - 1)));
    System.out.println("\"sex\".hashCode() & (16 - 1) 	:" + ("sex".hashCode() & (16 - 1)));
    System.out.println("\"level\".hashCode() & (16 - 1)	:" + ("level".hashCode() & (16 - 1)));
    System.out.println("\"phone\".hashCode() & (16 - 1) 	:" + ("phone".hashCode() & (16 - 1)));
    System.out.println("\"address\".hashCode() & (16 - 1) :" + ("address".hashCode() & (16 - 1)));
    
    输出结果:
    
    "name".hashCode()	: 3373707
    "sex".hashCode()	: 113766
    "level".hashCode()	: 102865796
    "phone".hashCode()	: 106642798
    "address".hashCode()	: -1147692044
    --------*****---------
    "name".hashCode() & (16 - 1) 	:11
    "sex".hashCode() & (16 - 1) 	:6
    "level".hashCode() & (16 - 1)	:4
    "phone".hashCode() & (16 - 1) 	:14
    "address".hashCode() & (16 - 1) :4

    如上输出结果,我们向hashMap里put了5个键值对,每个K的hashCode值均不相同,但是根据hashCode计算出来的下标却存在碰撞(有两个4),虽然hashCode的值很随机,但是限于我们数组长度,即便是很少的几个数据,也是有很高机率碰撞的,这也就说明了这些看起来(绝对值)很大hashCode值和【0-15】范围内的值对于长度为16的初始数组容量来讲效果等同。

    但是在数据量很少的情况下,即便发生了碰撞,性能上的劣势也几乎可以忽略不计。

    但是我们上面的下标求值是一种假设,假设直接根据K的hashCode和数组长度求模,但是实际上是根据K的hash值和数组长度求模

    那么K的hash值是什么,如何计算出来的呢,接下来就来讨论hash值的计算过程,hash方法。

     

    三、hash方法解析

    static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    1、如果key为空,那么hash值置为0。HashMap允许null作为键,虽然这样,因为null的hash值一定是0,而且null==null为真,所以HashMap里面最多只会有一个null键。而且这个null键一定是放在数组的第一个位置上。但是如果存在hash碰撞,该位置上形成链表了,那么null键对应的节点就不确定在链表中的哪个位置了(取决于插入顺序,并且每次扩容其在链表中的位置都可能会改变)。

    2、如果key是个不为空的对象,那么将key的hashCode值h和h无符号右移16位后的值做异或运算,得到最终的hash值。

    从代码中目前我们可确定的信息是:hashCode值(h)是计算基础,在h的基础上进行了两次位运算(无符号右移、异或)

    我们还针对前面的user的key来重新进行一下测试

    System.out.println("hash(\"name\")	: " + hash("name"));
    System.out.println("hash(\"sex\")	: " + hash("sex"));
    System.out.println("hash(\"level\")	: " + hash("level"));
    System.out.println("hash(\"phone\")	: " + hash("phone"));
    System.out.println("hash(\"address\")	: " + hash("address"));
    
    System.out.println("--------*****---------");
    
    System.out.println("hash(\"name\") & (16 - 1) 	:" + (hash("name") & (16 - 1)));
    System.out.println("hash(\"sex\") & (16 - 1) 		:" + (hash("sex") & (16 - 1)));
    System.out.println("hash(\"level\") & (16 - 1)	:" + (hash("level") & (16 - 1)));
    System.out.println("hash(\"phone\") & (16 - 1) 	:" + (hash("phone") & (16 - 1)));
    System.out.println("hash(\"address\") & (16 - 1) 	:" + (hash("address") & (16 - 1)));
    
    输出结果:
    
    hash("name")	: 3373752
    hash("sex")	: 113767
    hash("level")	: 102866341
    hash("phone")	: 106642229
    hash("address")	: -1147723677
    --------*****---------
    hash("name") & (16 - 1) 	:8
    hash("sex") & (16 - 1) 		:7
    hash("level") & (16 - 1)	:5
    hash("phone") & (16 - 1) 	:5
    hash("address") & (16 - 1) 	:3

    我们对比一下两次的输出结果

    "name".hashCode()	    : 3373707               hash("name")	: 3373752
    "sex".hashCode()	    : 113766                hash("sex")	        : 113767
    "level".hashCode()	    : 102865796             hash("level")	: 102866341
    "phone".hashCode()	    : 106642798             hash("phone")	: 106642229
    "address".hashCode()	    : -1147692044           hash("address")	: -1147723677
    --------*****---------
    "name".hashCode() & (16 - 1) 	:11                 hash("name") & (16 - 1) 	:8
    "sex".hashCode() & (16 - 1) 	:6                  hash("sex") & (16 - 1) 	:7
    "level".hashCode() & (16 - 1)	:4                  hash("level") & (16 - 1)	:5
    "phone".hashCode() & (16 - 1) 	:14                 hash("phone") & (16 - 1) 	:5
    "address".hashCode() & (16 - 1) :4                  hash("address") & (16 - 1) 	:3

    虽然经过hash算法之后与直接使用hashCode的输出不同,但是数组下标还是出现了碰撞的情况(有两个5)。所以hash方法也不能解决碰撞的问题(实际上碰撞不算是问题,我们只是想尽可能的少发生)。那么为什么不直接用hashCode而非要经过这么一种位运算来产生一个hash值呢。
     

    我们先通过几个例子来看下 h ^ (h >>> 16)  的计算过程

    若h=17,那么h ^ (h >>> 16)的计算可体现为如下过程:
        0000 0000 0000 0000 0000 0000 0001 0001    此时就是:h(17)的二进制。【高位是16个0】
        0000 0000 0000 0000 0000 0000 0000 0000    h(17)的二进制无符号右移16位后,此时就是:(h >>> 16)的二进制
        0000 0000 0000 0000 0000 0000 0001 0001    上两行进行异或运算,此时就是:h ^ (h >>> 16)的二进制
    最终可知(当h=17时):h ^ (h >>> 16) = 17,并没有发生变化。
    
    若h=65535,那么h ^ (h >>> 16)的计算可体现为如下过程:
        0000 0000 0000 0000 1111 1111 1111 1111    h【高位还是16个0】
        0000 0000 0000 0000 0000 0000 0000 0000    h >>> 16
        0000 0000 0000 0000 1111 1111 1111 1111    h ^ (h >>> 16)
    最终可知(当h=65535时):h ^ (h >>> 16) = 65535,并没有发生变化。
    
    若h=65536,那么h ^ (h >>> 16)的计算可体现为如下过程:
        0000 0000 0000 0001 0000 0000 0000 0000     h【高位含有一个1】
        0000 0000 0000 0000 0000 0000 0000 0001     h >>> 16
        0000 0000 0000 0001 0000 0000 0000 0001     h ^ (h >>> 16)
    最终可知(当h=65536时):h ^ (h >>> 16) = 65537,hash后的值和原值不同。
    
    若h=1147904,那么h ^ (h >>> 16)的计算可体现为如下过程:
        0000 0000 0001 0001 1000 0100 0000 0000     h【高位含有两个1,并不连续】
        0000 0000 0000 0000 0000 0000 0001 0001     h >>> 16
        0000 0000 0001 0001 1000 0100 0001 0001     h ^ (h >>> 16)
    最终可知(当h=1147904时):h ^ (h >>> 16) = 1147921,hash后的值和原值不同。
    
    再来看个负数的情况,负数的情况稍微复杂些,主要因为负数的二进制和十进制之间的转换会有【加|减|取反】等操作。
    若h=-5,那么h ^ (h >>> 16)的计算可体现为如下过程:
        0000 0000 0000 0000 0000 0000 0000 0101    先得到5的二进制
        1111 1111 1111 1111 1111 1111 1111 1010    5的二进制取反
    
        1111 1111 1111 1111 1111 1111 1111 1011    5的二进制取反后加1,此时就是:h(-5)的二进制。
        0000 0000 0000 0000 1111 1111 1111 1111    h(-5)的二进制无符号右移16位后,此时就是:(h >>> 16)的二进制
        1111 1111 1111 1111 0000 0000 0000 0100    上两行进行异或运算,此时就是:h ^ (h >>> 16)的二进制
                                                   接下来求一下这个二进制对应的10进制数值
        1111 1111 1111 1111 0000 0000 0000 0011    上一个二进制值减1
        0000 0000 0000 0000 1111 1111 1111 1100    再取反,此时十进制值为65532,但是需要加个负号
    最终可知(当h=-5时):h ^ (h >>> 16) = -65532,hash后的值和原值相差比较悬殊

     

    1)上面的例子只考虑了正数的情况,但可以得出以下结论
    当h(hashCode值)在【0-65535】时,位运算后的结果仍然是h
    当h(hashCode值)在【65535-N】时,位运算后的结果和h不同

    当h(hashCode值)为负数时,位运算后的结果和h也不尽相同

    2)我们上面user对象里的key的hashCode值都没有在【0-65535】范围内,所以计算出来的结果与hashCode值存在差异。

     

    为什么【0-65535】范围内的数值h,h ^ (h >>> 16) = h ?

    从例子中的二进制的运算描述我们可以发现,【0-65535】范围内的数值的二进制的高16位都是0,在进行无符号右移16位后,原来的高16位变成了现在的低16位,现在的高16位补了16个0,这种操作之后当前值就是32个0,以32个0去和任何整数值N做异或运算结果都还是N。而不再【0-65535】范围内的数值的高16位都包含有1数字位,在无符号右移16位后,虽然高位仍然补了16个0,但是当前的低位任然包含有1数字位,所以最终的运算结果会发生变化。

    而我们use对象里的key的hashCode要么大于65535、要么小于0所以最终的hash值和hashCode都不相同,因为在异或运算中hashCode的高位中的非0数字位参与到了运算中。

     

    四、hash方法的作用

    前文通过实例已经印证了hash方法并不能杜绝碰撞。

    "name".hashCode()	    : 3373707               hash("name")	: 3373752
    "sex".hashCode()	    : 113766                hash("sex")	        : 113767
    "level".hashCode()	    : 102865796             hash("level")	: 102866341
    "phone".hashCode()	    : 106642798             hash("phone")	: 106642229

    而且通过对比观察,hash后的值和hashCode值虽然不尽相同,而对于正数的hashCode的产生的hash值即便和原值不同,差别也不是很大。为什么不直接使用hashCode作为hash值呢?为什么非要经过 h ^ (h >>> 16)  这一步运算呢?

    在hash方法的注释是这样描述的:

    /**
    * Computes key.hashCode() and spreads (XORs) higher bits of hash
    * to lower.  Because the table uses power-of-two masking, sets of
    * hashes that vary only in bits above the current mask will
    * always collide. (Among known examples are sets of Float keys
    * holding consecutive whole numbers in small tables.)  So we
    * apply a transform that spreads the impact of higher bits
    * downward. There is a tradeoff between speed, utility, and
    * quality of bit-spreading. Because many common sets of hashes
    * are already reasonably distributed (so don't benefit from
    * spreading), and because we use trees to handle large sets of
    * collisions in bins, we just XOR some shifted bits in the
    * cheapest possible way to reduce systematic lossage, as well as
    * to incorporate impact of the highest bits that would otherwise
    * never be used in index calculations because of table bounds.
    */

    大概意思就是:

    寻址计算时,能够参与到计算的有效二进制位仅仅是右侧和数组长度值对应的那几位,意味着发生碰撞的几率会高。

    通过移位和异或运算让hashCode的高位能够参与到寻址计算中。

    采用这种方式是为了在性能、实用性、分布质量上取得一个平衡。

    有很多hashCode算法都已经是分布合理的了,并且大量碰撞时,还可以通过树结构来解决查询性能问题。

    所以用了性能比较高的位运算来让高位参与到寻址运算中,位运算对于系统损耗相对低廉。

    还提到了Float keys,个人认为说的应该是浮点数类型的对象作为key的时候,也顺便测试了下

    System.out.println("Float.valueOf(0.1f).hashCode()		:" + Float.valueOf(0.1f).hashCode());
    System.out.println("Float.valueOf(1.3f).hashCode()		:" + Float.valueOf(1.3f).hashCode());
    System.out.println("Float.valueOf(100.4f).hashCode()	:" + Float.valueOf(1.4f).hashCode());
    System.out.println("Float.valueOf(987607.3f).hashCode()	:" + Float.valueOf(100000.3f).hashCode());
    System.out.println("Float.valueOf(2809764.4f).hashCode()	:" + Float.valueOf(100000.4f).hashCode());
    System.out.println("Float.valueOf(-100.3f).hashCode()	:" + Float.valueOf(-100.3f).hashCode());
    System.out.println("Float.valueOf(-100.4f).hashCode()	:" + Float.valueOf(-100.4f).hashCode());
    
    System.out.println("--------*****---------");
    
    System.out.println("hash(0.1f)		:" + hash(0.1f));
    System.out.println("hash(1.3f)		:" + hash(1.3f));
    System.out.println("hash(1.4f)	:" + hash(1.4f));
    System.out.println("hash(100000.3f)	:" + hash(100000.3f));
    System.out.println("hash(100000.4f)	:" + hash(100000.4f));
    System.out.println("hash(-100.3f)	:" + hash(-100.3f));
    System.out.println("hash(-100.4f)	:" + hash(-100.4f));
    
    输出结果:
    
    Float.valueOf(0.1f).hashCode()		:1036831949
    Float.valueOf(1.3f).hashCode()		:1067869798
    Float.valueOf(100.4f).hashCode()	:1068708659
    Float.valueOf(987607.3f).hashCode()	:1203982374
    Float.valueOf(2809764.4f).hashCode()	:1203982387
    Float.valueOf(-100.3f).hashCode()	:-1027040870
    Float.valueOf(-100.4f).hashCode()	:-1027027763
    --------*****---------
    hash(0.1f)	:1036841217
    hash(1.3f)	:1067866560
    hash(1.4f)	:1068698752
    hash(100000.3f)	:1203967973
    hash(100000.4f)	:1203967984
    hash(-100.3f)	:-1027056814
    hash(-100.4f)	:-1027076603

    示例中的浮点数数值大小跨度还是比较大的,但是生成hashCode相差都不大,因为hashCode相差不大,所以最终的hash值相差也不大。那么要怎么证明hash之后就会减少碰撞呢?这个不太理解,看来还得看看大神们的分析。

     

    展开全文
  • iOS 重写 isequal方法需重写hash方法

    千次阅读 2015-07-19 22:24:09
    在项目中,有时候比较两个对象是否相等时,只是比较内容,...一般重写isequal方法时,都需要重写hash方法,原因是:如果不这么做的话,就会违反Object.hashCode的通用约定,从而导致该类无法与所有基于散列值(hash)的

    在项目中,有时候比较两个对象是否相等时,只是比较内容,而不是必须为同一对象。

    而nsobject提供的isequal 判断是否为同一对象。系统的nsstring, nsarray等,都已重写isequal方法。


    一般重写isequal方法时,都需要重写hash方法,原因是:如果不这么做的话,就会违反Object.hashCode的通用约定,从而导致该类无法与所有基于散列值(hash)的集合类结合在一起正常运行,这样的集合类包括HashMap(nsdictionary)、HashSet(nsset)、Hashtable(nsarray)。

    什么是hash, 作用是什么? 

    见http://blog.csdn.net/kafeidev/article/details/6224407

    展开全文
  • 基于hash方法的相似计算

    千次阅读 2012-08-31 11:44:55
    3 基于hash方法的相似计算  基于hash的相似度计算方法,是一种基于概率的高维度数据的维度削减的方法,主要用于大规模数据的压缩与实时或者快速的计算场景下,基于hash方法的相似度计算经常用于高维度大数据量的...

    3 基于hash方法的相似计算

           基于hash的相似度计算方法,是一种基于概率的高维度数据的维度削减的方法,主要用于大规模数据的压缩与实时或者快速的计算场景下,基于hash方法的相似度计算经常用于高维度大数据量的情况下,将利用原始信息不可存储与计算的问题转化为映射空间的可存储计算问题,在海量文本重复性判断方面,近似文本查询方面有比较多的应用,google的网页去重[1],google news的协同过滤[2,3]等都是采用hash方法进行近似相似度的计算,比较常见的应用场景Near-duplicate detection、Image similarity identification、nearest neighbor search,常用的一些方法包括I-match,Shingling、Locality-Sensitive Hashing族等方法,下面针对几种常见的hash方法进行介绍。

    3.1 minhash方法介绍

           Minhash方法是Locality-sensitive hashing[4,5]算法族里的一个常用方法,基本的思想是,对于每一个对象的itemlist,将输入的item进行hash,这样相似的item具有很高的相似度被映射到相同的buckets里面,这样尽量保证了hash之后两个对象之间的相似程度和原来是高相似的,而buckets的数量是远远小于输入的item的,因此又达到降低复杂度的目的。

           minhash方法用Jaccard进行相似度的计算方法,则对于两个集合和 , 和 的相似性的计算方法为:

    当两个集合越相似,则该值越接近1,否则越接近0。用minhash方法,将一个集合映射到[0-R-1]之间的值,以相同的概率随机的抽取一个[0-R-1[的一个排列,依次排列查找第一次出现1的行。

    设随机排列为43201(edcab),对于C1列,第一次出现1的行是R4,所以h(C1) = 3,同理有h(C2)=2, h(C3)=4, h(C4)=3。

    通过多次抽取随机排列得到n个minhash函数h1,h2,…,hn,依此对每一列都计算n个minhash值。对于两个集合,看看n个值里面对应相等的比例,即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列,得到一个n行C列的签名矩阵。因为n可远小于R,这样在压缩了数据规模的同时,并且仍能近似计算出相似度。

    3.2 simhash方法介绍

    simhash方法是在大文本重复识别常用的一个方法,该方法主要是通过将对象的原始特征集合映射为一个固定长度的签名,将对象之间的相似度的度量转化为签名的汉明距离,通过这样的方式,极大限度地进行了降低了计算和存储的消耗。

    3.2.1 签名计算过程

           该方法通过对输入特征集合的计算步骤可以描述如下:

    1. 将一个f维的向量V初始化为0;f位的二进制数S初始化为0;
    2. 对每一个特征:用传统的hash算法对该特征产生一个f位的签名b。对i=1到f:

          如果b的第i位为1,则V的第i个元素加上该特征的权重;

    否则,V的第i个元素减去该特征的权重。 

    1. 如果V的第i个元素大于0,则S的第i位为1,否则为0;
    2. 输出S作为签名。

    通过上述步骤将输入的表示对象的特征集合转化为该对象的一个签名,在完成签名之后,度量两个对象的相似度的差异即变成了对量二者的指纹的K位的差异情况。

    3.2.2 汉明距离查找优化

    对于如何快速查找出某一个签名是否与其存在最大差异不超过K个bit的指纹,Detecting Near-Duplicates for Web Crawling这篇论文中进行了介绍。该查找方法的基本思想是利用空间换时间的方法,该方法的依据是需要查找的两个指纹的差异很小,这样可以通过将原始指纹进行分块索引,如果两个指纹的差异很小,则合理的分块后,根据鸽笼原理,其中存在一定数量的块是一致的,通过利用相同的块进行相似的指纹的召回,只需要比对召回的块中有差异的块的bit差异,这样减少了需要比对的数量,节省了比对的时间开销。

    3.3 小结

           hash方法的相似度计算的主要应用场景,一般是针对大规模数据进行压缩,在保证效果损失可接受的情况下,节省存储空间,加快运算速度,针对该方法的应用,在目前的大规模的互联网处理中,很多相似度的计算都是基于这种近似性的计算,并取得了比较好的效果。

    设随机排列为43201(edcab),对于C1列,第一次出现1的行是R4,所以h(C1) = 3,同理有h(C2)=2, h(C3)=4, h(C4)=3。

    通过多次抽取随机排列得到n个minhash函数h1,h2,…,hn,依此对每一列都计算n个minhash值。对于两个集合,看看n个值里面对应相等的比例,即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列,得到一个n行C列的签名矩阵。因为n可远小于R,这样在压缩了数据规模的同时,并且仍能近似计算出相似度。

    转自:http://huangbo929.blog.edu.cn/2012/758781.html

    展开全文
  • 字符串hash方法

    千次阅读 2018-07-27 20:51:01
    网上整理的一篇文章,感觉不错,贴此...•比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod •字符串:abc,bbc,aba,aadaabac •字符串下标从0开始 •先把a映射为1,b映射为2,c-&gt;3,d-&gt;4,即idx(a)=1, idx...

    网上整理的一篇文章,感觉不错,贴此供用.

    求一个字符串的hash值:

    现在我们希望找到一个hash函数,使得每一个字符串都能够映射到一个整数上

    比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod

    •字符串:abc,bbc,aba,aadaabac

    •字符串下标从0开始

    •先把a映射为1,b映射为2,c->3,d->4,即idx(a)=1, idx(b)=2, idx(c)=3,idx(d)=4;

    •好!开始对字符串进行hash

    假设我们取p=13 ,mod=101

    先把abc映射为一个整数

    hash[0]=1,表示 a 映射为1

    hash[1]=(hash[0]*p+idx(b))%mod=15,表示 ab 映射为 15

    hash[2]=(hash[1]*p+idx(c))%mod=97

    这样,我们就把 abc 映射为 97 这个数字了。

    •用同样的方法,我们可以把bbc,aba,aadaabac都映射到一个整数

    •用同样的hash函数,得到如下结果

    • abc  ->  97

    • bbc  ->  64

    • aba  ->  95

    • aadaabac  ->  35

    •那么,我们发现,这是一个字符串到整数的映射

    •这样子,我们就可以记录下每个字符串对应的整数,当下一次出现了一个已经出现的字符串时,查询整数是否出现过,就可以知道 字符串是否重复出现。

    •现在要判断两个字符串是否一致,怎么办呢?直接用它们的hash值判断即可,若hash值一致,则认为字符串一致;若hash值不一致,则认为是不同的字符串。

    •我们要判断两个字符串是否一致,没有那么麻烦,直接先判断长度是否一致,然后再判断每个对应的字符是否一致即可。

    •但,如果要判断多个字符串里有多少个不同的字符串,怎么办呢?

    •两两字符串都进行比较?时间复杂度太高

    •把每个字符串hash成一个整数,然后把所有整数进行一个去重操作,即可知道答案了。

    当遇到冲突时,我们可以想办法调整p和mod,使得冲突概率减小之又小。我们一般认为p和mod一般取素数,p取一个较大的素数即可(6位到8位),mod取一个大素数,比如1e9+7,或者1e9+9。

     

    如何求一个子串的hash值?

    •在之前,我们求出了hash[i],表示第i个前缀的hash值。现在怎么求出每个子串的hash值呢?

    •我们看下hash的公式:

    • hash[i]=(hash[i-1]*p+idx(s[i]))%mod

    •这表示第 i 个前缀的hash值,是一个hash的前缀和。

    •hash[i]=(hash[i-1]*p+idx(s[i]))%p;

    •那么,我要求S[l…r]这个子串的hash值

    • hash[l..r]=(hash[r]-hash[l-1]*(p^(r-1+1)))%mod(假设字符串下标从1开始)

    •但注意下取模时候的问题!

    •hash[l..r]=(hash[r]-hash[l-1]*(p^(r-1+1)))%mod

    • hash[l..r]是不是可能有负数?

    •怎么办呢?当得到的hash[l..r]<0的时候,hash[l..r]+=mod,就好啦。

    •这样就可以保证每个子串的hash值在[0, mod-1]的范围内,准确地用hash值来处理字符串

     

    常用的几个字符串hash法

    •1. unsigned long long hash[N];

         hash[i]=hash[i-1]*p(自动取模)

    解释:

    unsigned long long hash[N];

    定义一个unsigned long long类型的变量,它的范围是在[0, 2^64) 内,这就相当于,当数超不过2^64-1后,它会溢出!这就相当于一个数模2^64的过程。

    那么hash函数可以理解为:

           hash[i]=(hash[i-1]*p)%(2^64)

    P取一个大素数,一般习惯取1e9+7或1e9+9

    安全指数:三星(所以并不是很安全)

     

    •2. hash[i]=(hash[i-1]*p+idx(s[i]))%mod

    解释:

    这个之前已经提到过了。   

     hash[i]=(hash[i-1]*p+idx(s[i]))%mod

    p取一个6到8位的素数,mod取一个大素数,一般取1e9+7或1e9+9

    安全指数:四星 (还可以)

     

    •3. 双hash

     hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1

     hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2

    一般可以定义结构体里存两个变量(可见本人牛客多校那道题的写法)

     pair<hash1,hash2>表示一个字符串!

    解释:

    double hash

    即取两个mod值,mod1和mod2

     hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1

     hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2

     mod1一般取1e9+7,mod2一般取1e9+9为什么这么取?

    1000000007和1000000009是一对孪生素数,取它们,冲突的概率极低!

    安全指数:五星!(非常稳!)

     

    小结:

    •可以这么说,hash某种程度上就是乱搞,把hash函数弄的越没有规律越好,使得冲突的概率小到 大部分数据都卡不掉。

    •如果你开心,你想triple hash,ultra hash,rampage hash… 都没有问题!

     但请注意,hash的维度越高,耗时越高,耗内存越大!一般情况下,single hash可以被hack掉,但double hash极难被hack掉, 用double hash足以解决问题

    展开全文
  • RedisTemplate 中hash方法的使用

    千次阅读 2019-11-20 09:29:37
    键值对的的操作在java里面也是很频繁的,下面记录了RedisTemplate 操作hash方法。 package com; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.Map;...
  • const ( c1_32 uint32 = 0xcc9e2d51 c2_32 uint32 = 0x1b873593 ...// GetHash returns a murmur32 hash for the data slice. func GetHash(data []byte) uint32 { // Seed is set to 37, same as C# versi
  • ruby--Hash方法汇总

    千次阅读 2012-07-31 09:37:31
    一。给Hash添加默认值 : h = {1,2,3,4} #=> {1 => 2, 3 => 4}  h.default = 7  h[1] #=> 2  h[3] #=> 4  h[4] #=> 7  h[5] #=> 7
  • 利用NSString的Hash方法比较字符串

    千次阅读 2015-05-10 21:42:31
    实际编程总会涉及到比较两个字符串的内容,一般会用 [string1 isEqualsToString:string2] 来比较两个字符串是否一致。对于字符串的isEqualsToString方法,需要逐个比较字符串的内容,是比较耗时的操作。
  • 改变hash的五种方法

    千次阅读 2019-11-25 10:04:08
    一、location的方法 1、利用location的hash属性 location.hash = 'now' 代码演示 使用前: 使用后: 由上两张图可见,使用之后改变了链接中的hash值 2、使用html5中的history方法 1) pushState方法 history.push...
  • hash算法详解

    万次阅读 多人点赞 2018-05-09 12:36:53
    你知道HashMap中hash方法的具体实现吗?你知道HashTable、ConcurrentHashMap中hash方法的实现以及原因吗?你知道为什么要这么实现吗?你知道为什么JDK 7和JDK 8中hash方法实现的不同以及区别吗?如果你不能很好的...
  • 计算hash值的方法

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

    千次阅读 2020-04-09 18:55:32
    static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 1、计算出key值的hashcode; 2、h = key.hashCode()) ^ (h >>> 16)...
  • 全网最透彻的Hash分析

    万次阅读 2018-03-13 13:34:20
    你知道HashMap中hash方法的具体实现吗?你知道HashTable、ConcurrentHashMap中hash方法的实现以及原因吗?你知道为什么要这么实现吗?你知道为什么JDK 7和JDK 8中hash方法实现的不同以及区别吗?如果你不能很好的...
  • Ruby中Hash常用方法

    千次阅读 2015-10-16 16:00:46
    Hash添加默认值 : 哈希常用方法" title="ruby 哈希常用方法" style="margin:0px; padding:0px; border:0px none; list-style:none; vertical-align:top">h = {1,2,3,4} #=> {1 => 2, 3 => 4} 哈希常用方法...
  • 构造hash表的方法

    千次阅读 2014-04-28 18:44:04
    一、整数的Hash函数 常用的方法有三种:直接取余法、乘积取整法、平方取中法。下面我们对这三种方法分别进行讨论。以下假定我们的关键字是,Hash表的容量是,Hash函数为 。 1.直接取余法 我们用关键字 ...
  • 先看看string的默认hash方法,代码如下 /** * Returns a hash code for this string. The hash code for a * {@code String} object is computed as * &lt;blockquote&gt;&lt;pre&gt; * s[0]*31...
  • LM Hash 计算方法

    千次阅读 2012-05-06 13:30:03
    如何从明文口令生成LM Hash 假设明文口令是”Welcome”,首先全部转换成大写,再做如下变换 “WELCOME” -> 57454C434F4D4500000000000000 也就是说在明文口令不足14字节的情况下,后面添加0×00补足14字节。有些...
  • 解决Hash碰撞冲突方法总结

    千次阅读 2018-06-28 10:17:21
    https://blog.csdn.net/zeb_perfect/article/details/52574915Hash碰撞冲突我们知道,对象Hash的前提是实现equals()和hashCode()两个方法,那么HashCode()的作用就是保证对象返回唯一hash值,但当两个对象计算值一样...
  • c++中std::hash的以及万能hash使用方法

    千次阅读 2020-07-11 13:24:41
    首先是标准库中的std::hash函数,对于内置的类型,标准库中是已经提供了的(包括std::string),但是若是自己自定义的类型想要求其哈希值的话,就需要自己定义其哈希值的求值方式。下面是简单示范 #include <map&...
  • 使用方法:直接导入generate_password_hash方法,然后传入 想加密的字符串 即可。需要注意的是,如果要保存到数据库中记得设置String(128),64可能不太够存储。 check_password_hash 使用说明:导入check_...
  • Java中hash算法细述

    万次阅读 多人点赞 2018-05-09 21:59:09
    你知道HashMap中hash方法的具体实现吗?你知道HashTable、ConcurrentHashMap中hash方法的实现以及原因吗?你知道为什么要这么实现吗?你知道为什么JDK 7和JDK 8中hash方法实现的不同以及区别吗?如果你不能很好的...
  • Facebook KeyHash生成方法

    千次阅读 2014-10-07 09:41:58
    1、 去 ...下载OpenSSL工具   2、 在C盘根目录下新建一个openssl的文件夹,并将OpenSSL压缩包解压到此文件夹中 ...3、 找到debug.keystore文件(C:\Users\zgp.IT\.android)复制粘贴到Java JDK的bin目录...KeyHash
  • Linux 下的密码 Hash破解方法

    千次阅读 2018-07-23 13:56:32
    Linux 下的密码 Hash破解方法   0x00 前言 Linux 系统下,用户的密码会被加密保存在文件/etc/shadow 中,关于密码的加密方式与破解方法有哪些呢?本文尝试对这一部分内容进行整理,介绍相关基础知识,测试常用...
  • Hash算法解决冲突的方法

    万次阅读 2017-02-10 21:40:20
    Hash算法解决冲突的方法一般有以下几种常用的解决方法 1, 开放定址法: 所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入 公式为:fi...
  • 解决Hash冲突四种方法

    万次阅读 多人点赞 2017-06-18 11:19:48
    Hash算法只是一个定义,并没有规定具体的实现 简述 把任意长度的输入,通过Hash算法变换成固定长度的输出,这个输出就是Hash值。哈希值的空间远小于输入的空间,所以可能会发生“哈希碰撞”,即两个不同的输入,...
  • 解决Hash冲突的方法

    万次阅读 2018-08-28 09:23:43
     这种方法是按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有 折叠法 与 移位法。 移位法是将分割后的每部分...
  • 【算法学习】字符串Hash入门

    万次阅读 多人点赞 2018-07-02 01:41:35
    Hash方法 自然溢出方法 Hash公式 单Hash方法 Hash公式 举例 双Hash方法 Hash公式 获取子串的Hash 例子 公式 字符串Hash的应用 字符串Hash入门 字符串Hash可以通俗的理解为,把一个字符串转换为一个...
  • hash

    万次阅读 2019-07-27 17:35:34
    可变和不可变类型 不可变类型,内存中的数据不允许被修改: 数字类型 int, bool, float, complex, long(2.x) ...1.可变类型的数据变化,是通过 方法 来实现的 2.如果给一个可变类型的变量,赋值了一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 529,594
精华内容 211,837
关键字:

hash的方法