精华内容
下载资源
问答
  • C语言实现hash算法

    2020-09-04 10:51:33
    C语言实现hash算法源码,实现了sha256,sha384,sha512三种哈希算法,项目中用到的,提取出来测试使用的。
  • 主要介绍了Java常用HASH算法,结合实例形式总结分析了Java常用的Hash算法,包括加法hash、旋转hash、FNV算法、RS算法hash、PJW算法、ELF算法、BKDR算法、SDBM算法、DJB算法、DEK算法、AP算法等,需要的朋友可以参考下
  • python爬虫 —Hash算法

    2021-01-07 20:23:26
    Hash算法 1.定义 Hash :散列,通过关于键值(key)的函数,将数据映射到内存存储中一个位置来访问。这个过程叫做Hash,这个映射函数称做散列函数,存放记录的数组称做散列表(Hash Table),又叫哈希表。 简单地说,它...
  • 一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。  首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们...
  • 实用标准文案 哈尔滨工程大学 实 验 报 告 实 验 名 称 Hash 算法 MD5 班 级 学 号 姓 名 实 验 时 间 2014 年 6 月 成 绩 指 导 教 师 实验室名称 哈尔滨工程大学实验室与资产管理处 制 文档 实用标准文案 一实验...
  • 一致性Hash算法,易于扩容; 添加了 单元测试,使用Spring提供的RestTemplate调用RestFul风格的API接口; 整合了 quartz 定时任务框架 ,并进行了封装,只需在构建完定时任务Job类后,在 application-quartz....
  • fasthash,go写的一个hash算法,比标准hash算法的速度更快,占用内存更低
  • 本文将粗略讲述一下Hash算法的概念特性,里边会结合分布式系统负载均衡实例对Hash的一致性做深入探讨。另外,探讨一下Hash算法在海量数据处理方案中的通用性。最后,从源代码出发,具体分析一下Hash算法在MapReduce...
  • Hash算法有三种,分别为平均哈希算法(aHash)、感知哈希算法你(pHash)和差异哈哈希算法(dHash)。 本代码针对平均哈希算法(aHash)
  • C++实现一致性hash算法

    2019-01-03 15:44:07
    一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)
  • MurmurHash算法由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc 、nginx、libmemcached,Redis,Memcached,Cassandra,HBase,Lucene等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的...
  • 主要介绍了PHP Hash算法:Times33算法代码实例,本文直接给出实现代码,需要的朋友可以参考下
  • geohash算法实现

    2016-02-01 15:36:00
    Geohash算法实现,经纬度到geohash编码的实现
  • 采用java实现的常用hash算法归总。
  • 主要介绍了PHP实现的一致性HASH算法,结合具体实例形式分析了hash算法的具体定义与使用技巧,需要的朋友可以参考下
  • 主要介绍了PHP实现的一致性Hash算法,结合实例形式详细分析了php一致性Hash算法的概念、原理及相关实现与使用技巧,需要的朋友可以参考下
  • 下面小编就为大家带来一篇常用Hash算法(C语言的简单实现)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • python版本的各种hash算法
  • Hash算法

    2012-03-11 20:43:30
    Hash算法
  • hash算法工具类

    2014-08-19 09:10:06
    一个hash算法的工具类,里面包含了一些常用的hash算法
  • php的hash算法介绍

    2020-12-18 22:08:59
    PHP的HashTable采用的拉链法来解决冲突, 这个自不用多说, 我今天主要关注的就是PHP的Hash算法, 和这个算法本身透露出来的一些思想。 PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with ...
  • Hash算法丨超级列表框快速去重复【易语言算法】-易语言
  • packagecom.conan;/***Hash算法大全*推荐使用FNV1算法**@algorithmNone*@authorGoodzzp2006-11-20*@lastEditGoodzzp2006-11-20*@editDetailCreate*/publicclassHashAlgorithms{/***加法hash**@paramkey*...

    packagecom.conan;/*** Hash算法大全

    * 推荐使用FNV1算法

    *

    * @algorithm None

    *@authorGoodzzp 2006-11-20

    * @lastEdit Goodzzp 2006-11-20

    * @editDetail Create*/publicclassHashAlgorithms {/*** 加法hash

    *

    *@paramkey

    *            字符串

    *@paramprime

    *            一个质数

    *@returnhash结果*/publicstaticintadditiveHash(String key,intprime) {inthash, i;for(hash=key.length(), i=0; i

    hash+=key.charAt(i);return(hash%prime);

    }/*** 旋转hash

    *

    *@paramkey

    *            输入字符串

    *@paramprime

    *            质数

    *@returnhash值*/publicstaticintrotatingHash(String key,intprime) {inthash, i;for(hash=key.length(), i=0; i

    hash=(hash<<4)^(hash>>28)^key.charAt(i);return(hash%prime);//return (hash ^ (hash>>10) ^ (hash>>20));}//替代://使用:hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask;//替代:hash %= prime;/*** MASK值,随便找一个值,最好是质数*/staticintM_MASK=0x8765fed1;/*** 一次一个hash

    *

    *@paramkey

    *            输入字符串

    *@return输出hash值*/publicstaticintoneByOneHash(String key) {inthash, i;for(hash=0, i=0; i

    hash+=key.charAt(i);

    hash+=(hash<<10);

    hash^=(hash>>6);

    }

    hash+=(hash<<3);

    hash^=(hash>>11);

    hash+=(hash<<15);//return (hash & M_MASK);returnhash;

    }/*** Bernstein's hash

    *

    *@paramkey

    *            输入字节数组

    *@paramlevel

    *            初始hash常量

    *@return结果hash*/publicstaticintbernstein(String key) {inthash=0;inti;for(i=0; i

    hash=33*hash+key.charAt(i);returnhash;

    }//Pearson's Hash//char pearson(char[]key, ub4 len, char tab[256])//{//char hash;//ub4 i;//for (hash=len, i=0; i> 8) ^ tab[(hash & 0xff) ^ key[i]];//return (hash & mask);//}/*** Universal Hashing*/publicstaticintuniversal(char[] key,intmask,int[] tab) {inthash=key.length, i, len=key.length;for(i=0; i>3];if((k&0x01)==0)

    hash^=tab[i+0];if((k&0x02)==0)

    hash^=tab[i+1];if((k&0x04)==0)

    hash^=tab[i+2];if((k&0x08)==0)

    hash^=tab[i+3];if((k&0x10)==0)

    hash^=tab[i+4];if((k&0x20)==0)

    hash^=tab[i+5];if((k&0x40)==0)

    hash^=tab[i+6];if((k&0x80)==0)

    hash^=tab[i+7];

    }return(hash&mask);

    }/*** Zobrist Hashing*/publicstaticintzobrist(char[] key,intmask,int[][] tab) {inthash, i;for(hash=key.length, i=0; i

    hash^=tab[i][key[i]];return(hash&mask);

    }//LOOKUP3//见Bob Jenkins(3).c文件//32位FNV算法staticintM_SHIFT=0;/*** 32位的FNV算法

    *

    *@paramdata

    *            数组

    *@returnint值*/publicstaticintFNVHash(byte[] data) {inthash=(int)2166136261L;for(byteb : data)

    hash=(hash*16777619)^b;if(M_SHIFT==0)returnhash;return(hash^(hash>>M_SHIFT))&M_MASK;

    }/*** 改进的32位FNV算法1

    *

    *@paramdata

    *            数组

    *@returnint值*/publicstaticintFNVHash1(byte[] data) {finalintp=16777619;inthash=(int)2166136261L;for(byteb : data)

    hash=(hash^b)*p;

    hash+=hash<<13;

    hash^=hash>>7;

    hash+=hash<<3;

    hash^=hash>>17;

    hash+=hash<<5;returnhash;

    }/*** 改进的32位FNV算法1

    *

    *@paramdata

    *            字符串

    *@returnint值*/publicstaticintFNVHash1(String data) {finalintp=16777619;inthash=(int)2166136261L;for(inti=0; i

    hash=(hash^data.charAt(i))*p;

    hash+=hash<<13;

    hash^=hash>>7;

    hash+=hash<<3;

    hash^=hash>>17;

    hash+=hash<<5;returnhash;

    }/*** Thomas Wang的算法,整数hash*/publicstaticintintHash(intkey) {

    key+=~(key<<15);

    key^=(key>>>10);

    key+=(key<<3);

    key^=(key>>>6);

    key+=~(key<<11);

    key^=(key>>>16);returnkey;

    }/*** RS算法hash

    *

    *@paramstr

    *            字符串*/publicstaticintRSHash(String str) {intb=378551;inta=63689;inthash=0;for(inti=0; i

    hash=hash*a+str.charAt(i);

    a=a*b;

    }return(hash&0x7FFFFFFF);

    }/*End Of RS Hash Function*//*** JS算法*/publicstaticintJSHash(String str) {inthash=1315423911;for(inti=0; i

    hash^=((hash<<5)+str.charAt(i)+(hash>>2));

    }return(hash&0x7FFFFFFF);

    }/*End Of JS Hash Function*//*** PJW算法*/publicstaticintPJWHash(String str) {intBitsInUnsignedInt=32;intThreeQuarters=(BitsInUnsignedInt*3)/4;intOneEighth=BitsInUnsignedInt/8;intHighBits=0xFFFFFFFF<

    hash=(hash<

    hash=((hash^(test>>ThreeQuarters))&(~HighBits));

    }

    }return(hash&0x7FFFFFFF);

    }/*End Of P. J. Weinberger Hash Function*//*** ELF算法*/publicstaticintELFHash(String str) {inthash=0;intx=0;for(inti=0; i

    hash=(hash<<4)+str.charAt(i);if((x=(int) (hash&0xF0000000L))!=0) {

    hash^=(x>>24);

    hash&=~x;

    }

    }return(hash&0x7FFFFFFF);

    }/*End Of ELF Hash Function*//*** BKDR算法*/publicstaticintBKDRHash(String str) {intseed=131;//31 131 1313 13131 131313 etc..inthash=0;for(inti=0; i

    hash=(hash*seed)+str.charAt(i);

    }return(hash&0x7FFFFFFF);

    }/*End Of BKDR Hash Function*//*** SDBM算法*/publicstaticintSDBMHash(String str) {inthash=0;for(inti=0; i

    hash=str.charAt(i)+(hash<<6)+(hash<<16)-hash;

    }return(hash&0x7FFFFFFF);

    }/*End Of SDBM Hash Function*//*** DJB算法*/publicstaticintDJBHash(String str) {inthash=5381;for(inti=0; i

    hash=((hash<<5)+hash)+str.charAt(i);

    }return(hash&0x7FFFFFFF);

    }/*End Of DJB Hash Function*//*** DEK算法*/publicstaticintDEKHash(String str) {inthash=str.length();for(inti=0; i

    hash=((hash<<5)^(hash>>27))^str.charAt(i);

    }return(hash&0x7FFFFFFF);

    }/*End Of DEK Hash Function*//*** AP算法*/publicstaticintAPHash(String str) {inthash=0;for(inti=0; i

    hash^=((i&1)==0)?((hash<<7)^str.charAt(i)^(hash>>3))

    : (~((hash<<11)^str.charAt(i)^(hash>>5)));

    }//return (hash & 0x7FFFFFFF);returnhash;

    }/*End Of AP Hash Function*//*** JAVA自己带的算法*/publicstaticintjava(String str) {inth=0;intoff=0;intlen=str.length();for(inti=0; i

    h=31*h+str.charAt(off++);

    }returnh;

    }/*** 混合hash算法,输出64位的值*/publicstaticlongmixHash(String str) {longhash=str.hashCode();

    hash<<=32;

    hash|=FNVHash1(str);returnhash;

    }

    }

    展开全文
  • Hash算法总结

    千次阅读 2019-03-02 16:04:20
    1. Hash是什么,它的作用 先举个例子。我们每个活在世上的人,为了能够参与各种社会活动,都需要一个用于识别自己的标志。也许你觉得名字或是身份证就足以代表你这个人,但是这种代表性非常脆弱,因为重名的人很多...

    1. Hash是什么,它的作用

    先举个例子。我们每个活在世上的人,为了能够参与各种社会活动,都需要一个用于识别自己的标志。也许你觉得名字或是身份证就足以代表你这个人,但是这种代表性非常脆弱,因为重名的人很多,身份证也可以伪造。最可靠的办法是把一个人的所有基因序列记录下来用来代表这个人,但显然,这样做并不实际。而指纹看上去是一种不错的选择,虽然一些专业组织仍然可以模拟某个人的指纹,但这种代价实在太高了。

    而对于在互联网世界里传送的文件来说,如何标志一个文件的身份同样重要。比如说我们下载一个文件,文件的下载过程中会经过很多网络服务器、路由器的中转,如何保证这个文件就是我们所需要的呢?我们不可能去一一检测这个文件的每个字节,也不能简单地利用文件名、文件大小这些极容易伪装的信息,这时候,我们就需要一种指纹一样的标志来检查文件的可靠性,这种指纹就是我们现在所用的Hash算法(也叫散列算法)。

    散列算法(Hash Algorithm),又称哈希算法,杂凑算法,是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样,散列算法就是一种以较短的信息来保证文件唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。因此,当原有文件发生改变时,其标志值也会发生改变,从而告诉文件使用者当前的文件已经不是你所需求的文件。

    这种标志有何意义呢?之前文件下载过程就是一个很好的例子,事实上,现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。而另一方面,我们在进行文件系统同步、备份等工具时,使用散列算法来标志文件唯一性能帮助我们减少系统开销,这一点在很多云存储服务器中都有应用。

    以Git为代表的众多版本控制工具都在使用SHA1等散列函数检查文件更新

    当然,作为一种指纹,散列算法最重要的用途在于给证书、文档、密码等高安全系数的内容添加加密保护。这一方面的用途主要是得益于散列算法的不可逆性,这种不可逆性体现在,你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件,也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。散列算法的这种不可逆性维持着很多安全框架的运营,而这也将是本文讨论的重点。

    2. Hash算法有什么特点

    一个优秀的 hash 算法,将能实现:

    • 正向快速:给定明文和 hash 算法,在有限时间和有限资源内能计算出 hash 值。
    • 逆向困难:给定(若干) hash 值,在有限时间内很难(基本不可能)逆推出明文。
    • 输入敏感:原始输入信息修改一点信息,产生的 hash 值看起来应该都有很大不同。
    • 冲突避免:很难找到两段内容不同的明文,使得它们的 hash 值一致(发生冲突)。即对于任意两个不同的数据块,其hash值相同的可能性极小;对于一个给定的数据块,找到和它hash值相同的数据块极为困难。

    但在不同的使用场景中,如数据结构和安全领域里,其中对某一些特点会有所侧重。

    2.1 Hash在管理数据结构中的应用

    在用到hash进行管理的数据结构中,就对速度比较重视,对抗碰撞不太看中,只要保证hash均匀分布就可以。比如hashmap,hash值(key)存在的目的是加速键值对的查找,key的作用是为了将元素适当地放在各个桶里,对于抗碰撞的要求没有那么高。换句话说,hash出来的key,只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能,直接与hash值产生的速度有关,所以这时候的hash值的产生速度就尤为重要,以JDK中的String.hashCode()方法为例:

    public int hashCode() {
        int h = hash;
        //hash default value : 0 
        if (h == 0 && value.length > 0) {
            //value : char storage
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
    
    

    很简洁的一个乘加迭代运算,在不少的hash算法中,使用的是异或+加法进行迭代,速度和前者差不多。

    2.1 Hash在在密码学中的应用

    在密码学中,hash算法的作用主要是用于消息摘要和签名,换句话说,它主要用于对整个消息的完整性进行校验。举个例子,我们登陆知乎的时候都需要输入密码,那么知乎如果明文保存这个密码,那么黑客就很容易窃取大家的密码来登陆,特别不安全。那么知乎就想到了一个方法,使用hash算法生成一个密码的签名,知乎后台只保存这个签名值。由于hash算法是不可逆的,那么黑客即便得到这个签名,也丝毫没有用处;而如果你在网站登陆界面上输入你的密码,那么知乎后台就会重新计算一下这个hash值,与网站中储存的原hash值进行比对,如果相同,证明你拥有这个账户的密码,那么就会允许你登陆。银行也是如此,银行是万万不敢保存用户密码的原文的,只会保存密码的hash值而而已。在这些应用场景里,对于抗碰撞和抗篡改能力要求极高,对速度的要求在其次。一个设计良好的hash算法,其抗碰撞能力是很高的。以MD5为例,其输出长度为128位,设计预期碰撞概率为2^128,这是一个极小极小的数字——而即便是在MD5被王小云教授破解之后,其碰撞概率上限也高达,也就是说,至少需要找次才能有1/2的概率来找到一个与目标文件相同的hash值。而对于两个相似的字符串,MD5加密结果如下:

    MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
    MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";
    

    可以看到仅仅一个比特位的改变,二者的MD5值就天差地别了

    ps : 其实把hash算法当成是一种加密算法,这是不准确的,我们知道加密总是相对于解密而言的,没有解密何谈加密呢,HASH的设计以无法解为目的的。并且如果我们不附加一个随机的salt值,HASH口令是很容易被字典攻击入侵的。

    3. Hash算法是如何实现的?

    密码学和信息安全发展到现在,各种加密算法和散列算法已经不是只言片语所能解释得了的。在这里我们仅提供几个简单的概念供大家参考。

    作为散列算法,首要的功能就是要使用一种算法把原有的体积很大的文件信息用若干个字符来记录,还要保证每一个字节都会对最终结果产生影响。那么大家也许已经想到了,求模这种算法就能满足我们的需要。

    事实上,求模算法作为一种不可逆的计算方法,已经成为了整个现代密码学的根基。只要是涉及到计算机安全和加密的领域,都会有模计算的身影。散列算法也并不例外,一种最原始的散列算法就是单纯地选择一个数进行模运算,比如以下程序。

    #  构造散列函数
    def hash(a):
        return a % 8
    
    #  测试散列函数功能
    print(hash(233))
    print(hash(234))
    print(hash(235))
    
    # 输出结果
    - 1
    - 2
    - 3
    

    很显然,上述的程序完成了一个散列算法所应当实现的初级目标:用较少的文本量代表很长的内容(求模之后的数字肯定小于8)。但也许你已经注意到了,单纯使用求模算法计算之后的结果带有明显的规律性,这种规律将导致算法将能难保证不可逆性。所以我们将使用另外一种手段,那就是异或。

    再来看下面一段程序,我们在散列函数中加入一个异或过程。

    #  构造散列函数
    def hash(a):
        return (a % 8) ^ 5
    
    #  测试散列函数功能
    print(hash(233))
    print(hash(234))
    print(hash(235))
    
    # 输出结果
    - 4
    - 7
    - 6
    

    很明显的,加入一层异或过程之后,计算之后的结果规律性就不是那么明显了。

    当然,大家也许会觉得这样的算法依旧很不安全,如果用户使用连续变化的一系列文本与计算结果相比对,就很有可能找到算法所包含的规律。但是我们还有其他的办法。比如在进行计算之前对原始文本进行修改,或是加入额外的运算过程(如移位),比如以下程序。

    #  构造散列函数
    def hash(a):
        return (a + 2 + (a << 1)) % 8 ^ 5
    
    #  测试散列函数功能
    print(hash(233))
    print(hash(234))
    print(hash(235))
    
    # 输出结果
    - 0
    - 5
    - 6
    

    这样处理得到的散列算法就很难发现其内部规律,也就是说,我们并不能很轻易地给出一个数,让它经过上述散列函数运算之后的结果等于4——除非我们去穷举测试。

    上面的算法是不是很简单?事实上,下面我们即将介绍的常用算法MD5和SHA1,其本质算法就是这么简单,只不过会加入更多的循环和计算,来加强散列函数的可靠性。

    4. Hash有哪些流行的算法

    目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2。

    • MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。

    • MD5(RFC 1321)是 Rivest 于1991年对 MD4 的改进版本。它对输入仍以 512 位分组,其输出是 128 位。MD5 比 MD4 复杂,并且计算速度要慢一点,更安全一些。MD5 已被证明不具备"强抗碰撞性"。

    • SHA (Secure Hash Algorithm)是一个 Hash 函数族,由 NIST(National Institute of Standards and Technology)于 1993 年发布第一个算法。目前知名的 SHA-1 在 1995 年面世,它的输出为长度 160 位的 hash 值,因此抗穷举性更好。SHA-1 设计时基于和 MD4 相同原理,并且模仿了该算法。SHA-1 已被证明不具"强抗碰撞性"。

    • 为了提高安全性,NIST 还设计出了 SHA-224、SHA-256、SHA-384,和 SHA-512 算法(统称为 SHA-2),跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

    可以看出,上面这几种流行的算法,它们最重要的一点区别就是"强抗碰撞性"。

    5. 那么,何谓Hash算法的「碰撞」?

    你可能已经发现了,在实现算法章节的第一个例子,我们尝试的散列算法得到的值一定是一个不大于8的自然数,因此,如果我们随便拿9个数去计算,肯定至少会得到两个相同的值,我们把这种情况就叫做散列算法的「碰撞」(Collision)。

    这很容易理解,因为作为一种可用的散列算法,其位数一定是有限的,也就是说它能记录的文件是有限的——而文件数量是无限的,两个文件指纹发生碰撞的概率永远不会是零。

    但这并不意味着散列算法就不能用了,因为凡事都要考虑代价,买光所有彩票去中一次头奖是毫无意义的。现代散列算法所存在的理由就是,它的不可逆性能在较大概率上得到实现,也就是说,发现碰撞的概率很小,这种碰撞能被利用的概率更小。

    随意找到一组碰撞是有可能的,只要穷举就可以。散列算法得到的指纹位数是有限的,比如MD5算法指纹字长为128位,意味着只要我们穷举2^128次,就肯定能得到一组碰撞——当然,这个时间代价是难以想象的,而更重要的是,仅仅找到一组碰撞并没有什么实际意义。更有意义的是,如果我们已经有了一组指纹,能否找到一个原始文件,让它的散列计算结果等于这组指纹。如果这一点被实现,我们就可以很容易地篡改和伪造网络证书、密码等关键信息。

    你也许已经听过MD5已经被破解的新闻——但事实上,即便是MD5这种已经过时的散列算法,也很难实现逆向运算。我们现在更多的还是依赖于海量字典来进行尝试,也就是通过已经知道的大量的文件——指纹对应关系,搜索某个指纹所对应的文件是否在数据库里存在。

    5.1 MD5的实际碰撞案例

    下面让我们来看看一个真实的碰撞案例。我们之所以说MD5过时,是因为它在某些时候已经很难表现出散列算法的某些优势——比如在应对文件的微小修改时,散列算法得到的指纹结果应当有显著的不同,而下面的程序说明了MD5并不能实现这一点。

    import hashlib
    
    #  两段HEX字节串,注意它们有细微差别
    a = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef")
    
    b = bytearray.fromhex("0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef")
    
    #  输出MD5,它们的结果一致
    print(hashlib.md5(a).hexdigest())
    print(hashlib.md5(b).hexdigest())
    
    ### a和b输出结果都为:
    cee9a457e790cf20d4bdaa6d69f01e41
    cee9a457e790cf20d4bdaa6d69f01e41
    
    

    而诸如此类的碰撞案例还有很多,上面只是原始文件相对较小的一个例子。事实上现在我们用智能手机只要数秒就能找到MD5的一个碰撞案例,因此,MD5在数年前就已经不被推荐作为应用中的散列算法方案,取代它的是SHA家族算法,也就是安全散列算法(Secure Hash Algorithm,缩写为SHA)。

    5.2 SHA家族算法以及SHA1碰撞

    安全散列算法与MD5算法本质上的算法是类似的,但安全性要领先很多——这种领先型更多的表现在碰撞攻击的时间开销更大,当然相对应的计算时间也会慢一点。

    SHA家族算法的种类很多,有SHA0、SHA1、SHA256、SHA384等等,它们的计算方式和计算速度都有差别。其中SHA1是现在用途最广泛的一种算法。包括GitHub在内的众多版本控制工具以及各种云同步服务都是用SHA1来区别文件,很多安全证书或是签名也使用SHA1来保证唯一性。长期以来,人们都认为SHA1是十分安全的,至少大家还没有找到一次碰撞案例。

    但这一事实在2017年2月破灭了。CWI和Google的研究人员们成功找到了一例SHA1碰撞,而且很厉害的是,发生碰撞的是两个真实的、可阅读的PDF文件。这两个PDF文件内容不相同,但SHA1值完全一样。(对于这件事的影响范围及讨论,可参考知乎上的讨论:如何评价 2 月 23 日谷歌宣布实现了 SHA-1 碰撞?)

    所以,对于一些大的商业机构来说, MD5 和 SHA1 已经不够安全,推荐至少使用 SHA2-256 算法。

    6. Hash在Java中的应用

    6.1 HashMap的复杂度

    在介绍HashMap的实现之前,先考虑一下,HashMap与ArrayList和LinkedList在数据复杂度上有什么区别。下图是他们的性能对比图:

    获取查找添加/删除空间
    ArrayListO(1)O(1)O(N)O(N)
    LinkedListO(N)O(N)O(1)O(N)
    HashMapO(N/Bucket_size)O(N/Bucket_size)O(N/Bucket_size)O(N)

    可以看出HashMap整体上性能都非常不错,但是不稳定,为O(N/Buckets),N就是以数组中没有发生碰撞的元素,Buckets是因碰撞产生的链表。

    注:发生碰撞实际上是非常稀少的,所以N/Bucket_size约等于1

    HashMap是对Array与Link的折衷处理,Array与Link可以说是两个速度方向的极端,Array注重于数据的获取,而处理修改(添加/删除)的效率非常低;Link由于是每个对象都保持着下一个对象的指针,查找某个数据需要遍历之前所有的数据,所以效率比较低,而在修改操作中比较快。

    6.2 HashMap的实现

    本文以JDK8的API实现进行分析

    6.2.1 对key进行Hash计算

    在JDK8中,由于使用了红黑树来处理大的链表开销,所以hash这边可以更加省力了,只用计算hashCode并移动到低位就可以了。

    static final int hash(Object key) {
        int h;
        //计算hashCode,并无符号移动到低位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    

    举个例子: 363771819^(363771819 >>> 16)

    0001 0101 1010 1110 1011 0111 1010 1011(363771819)
    0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
    --------------------------------------- =
    0001 0101 1010 1110 1010 0010 0000 0101(363766277)
    

    这样做可以实现了高地位更加均匀地混到一起。

    下面给出在Java中几个常用的哈希码(hashCode)的算法。

    1. Object类的hashCode. 返回对象的经过处理后的内存地址,由于每个对象的内存地址都不一样,所以哈希码也不一样。这个是native方法,取决于JVM的内部设计,一般是某种C地址的偏移。

    2. String类的hashCode. 根据String类包含的字符串的内容,根据一种特殊算法返回哈希码,只要字符串的内容相同,返回的哈希码也相同。

    3. Integer等包装类,返回的哈希码就是Integer对象里所包含的那个整数的数值,例如Integer i1=new Integer(100), i1.hashCode的值就是100 。由此可见,2个一样大小的Integer对象,返回的哈希码也一样。

    4. int,char这样的基础类,它们不需要hashCode,如果需要存储时,将进行自动装箱操作,计算方法同上。

    6.2.2 获取到数组的index的位置

    计算了Hash,我们现在要把它插入数组中了

    i = (tab.length - 1) & hash;
    

    通过位运算,确定了当前的位置,因为HashMap数组的大小总是2^n,所以实际的运算就是 (0xfff...ff) & hash ,这里的tab.length-1相当于一个mask,滤掉了大于当前长度位的hash,使每个i都能插入到数组中。

    6.2.3 生成包装类

    这个对象是一个包装类,Node<K,V>,内部有key,value,hash还有next,可以看出来它是一个链表。

    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            //getter and setter .etc.
    }
    

    6.2.4 插入包装类到数组

    (1). 如果输入当前的位置是空的,就插进去,如图,左为插入前,右为插入后

        0           0
        |           |
        1 -> null   1 - > null
        |           |
        2 -> null   2 - > null
        |           | 
        ..-> null   ..- > null
        |           | 
        i -> null   i - > new node
        |           |
        n -> null   n - > null
    

    (2). 如果当前位置已经有了node,且它们发生了碰撞,则新的放到前面,旧的放到后面,这叫做链地址法处理冲突。

        0           0
        |           |
        1 -> null   1 - > null
        |           |
        2 -> null   2 - > null
        |           | 
        ..-> null   ..- > null
        |           | 
        i -> old    i - > new - > old
        |           |
        n -> null   n - > null
    

    我们可以发现,失败的hashCode算法会导致HashMap的性能由数组下降为链表,所以想要避免发生碰撞,就要提高hashCode结果的均匀性。

    6.3 扩容

    如果当表中的75%已经被占用,即视为需要扩容了

    (threshold = capacity * load factor ) < size
    

    它主要有两个步骤:

    6.3.1 容量加倍

    左移1位,就是扩大到两倍,用位运算取代了乘法运算

    newCap = oldCap << 1;
    newThr = oldThr << 1;
    

    6.3.2 遍历计算Hash

    for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果发现当前有Bucket
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果这里没有碰撞
                if (e.next == null)
                    //重新计算Hash,分配位置
                    newTab[e.hash & (newCap - 1)] = e;
                //这个见下面的新特性介绍,如果是树,就填入树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //如果是链表,就保留顺序....目前就看懂这点
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    

    由此可以看出扩容需要遍历并重新赋值,成本非常高,所以选择一个好的初始容量非常重要。

    6.4 扩容如何提升性能?

    • 解决扩容损失:如果知道大致需要的容量,把初始容量设置好以解决扩容损失;
      比如我现在有1000个数据,需要 1000/0.75 = 1333 个坑位,又 1024 < 1333 < 2048,所以最好使用2048作为初始容量。

    • 解决碰撞损失:使用高效的HashCode与loadFactor,这个...由于JDK8的高性能出现,这儿问题也不大了。

    6.5 HashMap与HashTable的主要区别

    在很多的Java基础书上都已经说过了,他们的主要区别其实就是Table全局加了线程同步保护

    • HashTable线程更加安全,代价就是因为它粗暴的添加了同步锁,所以会有性能损失。
    • 其实有更好的concurrentHashMap可以替代HashTable,一个是方法级,一个是Class级。

    6.6 在Android中使用SparseArray代替HashMap

    官方推荐使用SparseArray([spɑ:s][ə'reɪ],稀疏的数组)或者LongSparseArray代替HashMap。官方总结有一下几点好处:

    • SparseArray使用基本类型(Primitive)中的int作为Key,不需要Pair<K,V>或者Entry<K,V>这样的包装类,节约了内存;

    • SpareArray维护的是一个排序好的数组,使用二分查找数据,即O(log(N)),每次插入数据都要进行排序,同样耗时O(N);而HashMap使用hashCode来加入/查找/删除数据,即O(N/buckets_size);

    • 总的来说,就是SparseArray针对Android嵌入式设备进行了优化,牺牲了微小的时间性能,换取了更大的内存优化;同时它还有别的优化,比如对删除操作做了优化;

    • 如果你的数据非常少(实际上也是如此),那么使用SpareArray也是不错的;

    总结

    「The Algorithm Design Manual」一书中提到,雅虎的 Chief Scientist ,Udi Manber 曾说过,在 yahoo 所应用的算法中,最重要的三个是:Hash,Hash 和 Hash。其实从上文中所举的git用sha1判断文件更改,密码用MD5生成摘要后加盐等等对Hash的应用可看出,Hash的在计算机世界扮演着多么重要的角色。另书中还举了一个很有趣的显示中例子:

    一场拍卖会中,物品是价高者得,如果每个人只有一次出价机会,同时提交自己的价格后,最后一起公布,出价最高则胜出。这种形式存在作弊的可能,如果有出价者能 hack 进后台,然后将自己的价格改为最高价 +1,则能以最低的代价获得胜利。如何杜绝这种作弊呢?

    答案很简单,参与者都提交自身出价的 hash 值就可以了,即使有人能黑进后台也无法得知明文价格,等到公布之时,再对比原出价与 hash 值是否对应即可。是不是很巧妙?

    是的,上面的做法,与上文提到的网站上储存密码用MD5 值而非明文,是同一种思想,殊途同归。

    可以看到无论是密码学、数据结构、现实生活中的应用,到处可以看到Hash的影子,通过这篇文章的介绍,相信你不仅知其名,也能懂其意。

    Reference

         转自:    https://www.jianshu.com/p/bf1d7eee28d0

    1. https://jizhi.im/blog/post/sha1decrypt
    2. http://www.jianshu.com/p/e54047b2b563
    3. https://www.zhihu.com/question/26762707
    4. http://mp.weixin.qq.com/s?__biz=MzA5ODUzOTA0OQ==&mid=2651688220&idx=1&sn=a3f9cb1e186ffe22d9825bca00e85c76&chksm=8b692e5abc1ea74ce61a819f5666dd7d73ee45d6145c92b993de271a315d4f3d3fb3874f9be3&mpshare=1&scene=23&srcid=0414EOLCuLSu17uo8Aw8refB#rd
    5. http://mp.weixin.qq.com/s/oRLkR7jplqO2qhHtUeTMIA





    展开全文
  • GeoHash算法原理及实现

    万次阅读 2020-05-19 17:36:54
    GeoHash原理及代码实现

    GeoHash算法原理

    GeoHash是目前比较主流实现位置服务的技术,Geohash算法将经纬度二维数据编码为一个字符串,本质是一个降维的过程

    样例数据(基于15次区域分割)

    位置经纬度Geohash
    北京站116.433589,39.910508wx4g19
    天安门116.403874,39.913884wx4g0f
    首都机场116.606819,40.086109wx4uj3

    GeoHash算法思想

    我们知道,经度范围是东经180到西经180,纬度范围是南纬90到北纬90,我们设定西经为负,南纬为负,所以地球上的经度范围就是[-180, 180],纬度范围就是[-90,90]。如果以本初子午线、赤道为界,地球可以分成4个部分。

    GeoHash的思想就是将地球划分的四部分映射到二维坐标上。

    [-90˚,0˚)代表0,(0˚,90˚]代表1,[-180˚,0)代表0,(0˚,180˚]代表1
    映射到二维空间划分为四部分则如下图

    在这里插入图片描述
    但是这么粗略的划分没有什么意义,想要更精确的使用GeoHash就需要再进一步二分切割
    在这里插入图片描述
    通过上图可看出,进一步二分切割将原本大略的划分变为细致的区域划分,这样就会更加精确。GeoHash算法就是基于这种思想,递归划分的次数越多,所计算出的数据越精确。

    GeoHash算法原理

    GeoHash算法大体上分为三步:1. 计算经纬度的二进制、2. 合并经纬度的二进制、3. 通过Base32对合并后的二进制进行编码。

    1. 计算经纬度的二进制
    	//根据经纬度和范围,获取对应的二进制
    	private BitSet getBits(double l, double floor, double ceiling) {
    		BitSet buffer = new BitSet(numbits);
    		for (int i = 0; i < numbits; i++) {
    			double mid = (floor + ceiling) / 2;
    			if (l >= mid) {
    				buffer.set(i);
    				floor = mid;
    			} else {
    				ceiling = mid;
    			}
    		}
    		return buffer;
    	}
    

    上述代码numbits为:private static int numbits = 3 * 5; //经纬度单独编码长度也就是说将地球进行15次二分切割

    注: 这里需要对BitSet类进行一下剖析,没了解过该类的话指定懵。

    了解BitSet只需了去了解它的set()、get()方法就足够了

    • BitSet的set方法
     /**
         * Sets the bit at the specified index to {@code true}.
         *
         * @param  bitIndex a bit index
         * @throws IndexOutOfBoundsException if the specified index is negative
         * @since  JDK1.0
         */
        public void set(int bitIndex) {
            if (bitIndex < 0)
                throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    
            int wordIndex = wordIndex(bitIndex);
            expandTo(wordIndex);
    
            words[wordIndex] |= (1L << bitIndex); // Restores invariants
    
            checkInvariants();
        }
    

    set方法内wordIndex(bitIndex)底层将bitIndex右移6位然后返回,ADDRESS_BITS_PER_WORD为常量6

    /**
        * Given a bit index, return word index containing it.
        */
       private static int wordIndex(int bitIndex) {
           return bitIndex >> ADDRESS_BITS_PER_WORD;
       }
    

    set方法内的expandTo(wordIndex)只是一个判断数组是否需要扩容的方法

    /**
         * Ensures that the BitSet can accommodate a given wordIndex,
         * temporarily violating the invariants.  The caller must
         * restore the invariants before returning to the user,
         * possibly using recalculateWordsInUse().
         * @param wordIndex the index to be accommodated.
         */
        private void expandTo(int wordIndex) {
            int wordsRequired = wordIndex+1;
            if (wordsInUse < wordsRequired) {
                ensureCapacity(wordsRequired);
                wordsInUse = wordsRequired;
            }
        }
    

    set内重要的一行代码words[wordIndex] |= (1L << bitIndex),这里只解释一下|=

    a|=b就是a=a|b,就是说将a、b转为二进制按位与,同0为0,否则为1

    • BitSet的get方法
     /**
        * Returns the value of the bit with the specified index. The value
        * is {@code true} if the bit with the index {@code bitIndex}
        * is currently set in this {@code BitSet}; otherwise, the result
        * is {@code false}.
        *
        * @param  bitIndex   the bit index
        * @return the value of the bit with the specified index
        * @throws IndexOutOfBoundsException if the specified index is negative
        */
       public boolean get(int bitIndex) {
           if (bitIndex < 0)
               throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    
           checkInvariants();
    
           int wordIndex = wordIndex(bitIndex);
           return (wordIndex < wordsInUse)
               && ((words[wordIndex] & (1L << bitIndex)) != 0);
       }
    

    get方法用一句话概括就是:如果传入的下标有值,返回true;反之为false

    以天安门坐标为例:39.913884, 116.403874

    	BitSet latbits = getBits(lat, -90, 90);
       	BitSet lonbits = getBits(lon, -180, 180);
       	// 纬度
       	for (int i = 0; i < numbits; i++) {
       		System.out.print(latbits.get(i) + " ");
       	}
       	// 经度
        for (int i = 0; i < numbits; i++) {
       		System.out.print(lonbits.get(i) + " ");
       	}
    

    纬度经过转换为:

    true false true true true false false false true true false false false true false 
    

    转为二进制:

    1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 
    

    经度经过转换为:

    true true false true false false true false true true false false false true true 
    

    转为二进制:

    1 1 0 1 0 0 1 0 1 1 0 0 0 1 1 
    
    1. 合并经纬度二进制
      合并原则:经度占偶数位,纬度占奇数位。也就是说经纬度交替合并,首位0位置为经度的0位置

    合并后二进制编码为:

    11100 11101 00100 01111 00000 01110
    
    1. 使用Base32对合并后的经纬度二进制进行编码
    • 代码实现
    // Base32进行编码
    	public String encode(double lat, double lon) {
    		BitSet latbits = getBits(lat, -90, 90);
    		BitSet lonbits = getBits(lon, -180, 180);
    		StringBuilder buffer = new StringBuilder();
    		for (int i = 0; i < numbits; i++) {
    			buffer.append((lonbits.get(i)) ? '1' : '0');
    			buffer.append((latbits.get(i)) ? '1' : '0');
    		}
    		String code = base32(Long.parseLong(buffer.toString(), 2));
    		return code;
    	}
    

    本文案例经纬度编码后

    wx4g0f
    

    后续问题

    如果要使用此功能实现附近的人。假如红点为使用者,经过Geohash算法分割后只会推荐同区域0011中的绿点,但是如下图所示,蓝色点相对于绿色点更接近用户,所以区域划分的弊端就展现在这里。
    在这里插入图片描述
    针对上述问题,我们可以人为获取红色用户所在的0011区域周边八个区域中的用户,即获取0011的同时还要获取0100,0110,1100,0001,1001,0000,0010,1000

    • 代码实现
    	public ArrayList<String> getArroundGeoHash(double lat, double lon) {
    		ArrayList<String> list = new ArrayList<>();
    		double uplat = lat + minLat;
    		double downLat = lat - minLat;
    
    		double leftlng = lon - minLng;
    		double rightLng = lon + minLng;
    
    		String leftUp = encode(uplat, leftlng);
    		list.add(leftUp);
    
    		String leftMid = encode(lat, leftlng);
    		list.add(leftMid);
    
    		String leftDown = encode(downLat, leftlng);
    		list.add(leftDown);
    
    		String midUp = encode(uplat, lon);
    		list.add(midUp);
    
    		String midMid = encode(lat, lon);
    		list.add(midMid);
    
    		String midDown = encode(downLat, lon);
    		list.add(midDown);
    
    		String rightUp = encode(uplat, rightLng);
    		list.add(rightUp);
    
    		String rightMid = encode(lat, rightLng);
    		list.add(rightMid);
    
    		String rightDown = encode(downLat, rightLng);
    		list.add(rightDown);
    
    		return list;
    	}
    

    然后根据球体两点间的距离计算红色用户与周边区域用户距离,从而进行附近的人功能实现

    • 通过两经纬度计算距离java代码实现
    	static double getDistance(double lat1, double lon1, double lat2, double lon2) {
    		// 经纬度(角度)转弧度。弧度用作参数,以调用Math.cos和Math.sin
    		double radiansAX = Math.toRadians(lon1); // A经弧度
    		double radiansAY = Math.toRadians(lat1); // A纬弧度
    		double radiansBX = Math.toRadians(lon2); // B经弧度
    		double radiansBY = Math.toRadians(lat2); // B纬弧度
    
    		// 公式中“cosβ1cosβ2cos(α1-α2)+sinβ1sinβ2”的部分,得到∠AOB的cos值
    		double cos = Math.cos(radiansAY) * Math.cos(radiansBY) * Math.cos(radiansAX - radiansBX)
    				+ Math.sin(radiansAY) * Math.sin(radiansBY);
    		double acos = Math.acos(cos); // 反余弦值
    		return EARTH_RADIUS * acos; // 最终结果
    	}
    

    GeoHash算法代码实现

    public class GeoHash {
    	public static final double MINLAT = -90;
    	public static final double MAXLAT = 90;
    	public static final double MINLNG = -180;
    	public static final double MAXLNG = 180;
    
    	private static int numbits = 3 * 5; //经纬度单独编码长度
    
    	private static double minLat;
    	private static double minLng;
    
    	private final static char[] digits = {'0', '1', '2', '3', '4', '5', '6', '7', '8',
    			'9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
    			'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    
    	//定义编码映射关系
    	final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
    
    	//初始化编码映射内容
    	static {
    		int i = 0;
    		for (char c : digits)
    			lookup.put(c, i++);
    	}
    
    	public GeoHash() {
    		setMinLatLng();
    	}
    
    	// Base32进行编码
    	public String encode(double lat, double lon) {
    		BitSet latbits = getBits(lat, -90, 90);
    		BitSet lonbits = getBits(lon, -180, 180);
    		StringBuilder buffer = new StringBuilder();
    		for (int i = 0; i < numbits; i++) {
    			buffer.append((lonbits.get(i)) ? '1' : '0');
    			buffer.append((latbits.get(i)) ? '1' : '0');
    		}
    		String code = base32(Long.parseLong(buffer.toString(), 2));
    		return code;
    	}
    
    	public ArrayList<String> getArroundGeoHash(double lat, double lon) {
    		ArrayList<String> list = new ArrayList<>();
    		double uplat = lat + minLat;
    		double downLat = lat - minLat;
    
    		double leftlng = lon - minLng;
    		double rightLng = lon + minLng;
    
    		String leftUp = encode(uplat, leftlng);
    		list.add(leftUp);
    
    		String leftMid = encode(lat, leftlng);
    		list.add(leftMid);
    
    		String leftDown = encode(downLat, leftlng);
    		list.add(leftDown);
    
    		String midUp = encode(uplat, lon);
    		list.add(midUp);
    
    		String midMid = encode(lat, lon);
    		list.add(midMid);
    
    		String midDown = encode(downLat, lon);
    		list.add(midDown);
    
    		String rightUp = encode(uplat, rightLng);
    		list.add(rightUp);
    
    		String rightMid = encode(lat, rightLng);
    		list.add(rightMid);
    
    		String rightDown = encode(downLat, rightLng);
    		list.add(rightDown);
    
    		return list;
    	}
    
    	//根据经纬度和范围,获取对应的二进制
    	private BitSet getBits(double l, double floor, double ceiling) {
    		BitSet buffer = new BitSet(numbits);
    		for (int i = 0; i < numbits; i++) {
    			double mid = (floor + ceiling) / 2;
    			if (l >= mid) {
    				buffer.set(i);
    				floor = mid;
    			} else {
    				ceiling = mid;
    			}
    		}
    		return buffer;
    	}
    
    	//将经纬度合并后的二进制进行指定的32位编码
    	private String base32(long i) {
    		char[] buf = new char[65];
    		int charPos = 64;
    		boolean negative = (i < 0);
    		if (!negative) {
    			i = -i;
    		}
    		while (i <= -32) {
    			buf[charPos--] = digits[(int) (-(i % 32))];
    			i /= 32;
    		}
    		buf[charPos] = digits[(int) (-i)];
    		if (negative) {
    			buf[--charPos] = '-';
    		}
    		return new String(buf, charPos, (65 - charPos));
    	}
    
    	private void setMinLatLng() {
    		minLat = MAXLAT - MINLAT;
    		for (int i = 0; i < numbits; i++) {
    			minLat /= 2.0;
    		}
    		minLng = MAXLNG - MINLNG;
    		for (int i = 0; i < numbits; i++) {
    			minLng /= 2.0;
    		}
    	}
    
    	//根据二进制和范围解码
    	private double decode(BitSet bs, double floor, double ceiling) {
    		double mid = 0;
    		for (int i = 0; i < bs.length(); i++) {
    			mid = (floor + ceiling) / 2;
    			if (bs.get(i))
    				floor = mid;
    			else
    				ceiling = mid;
    		}
    		return mid;
    	}
    
    	//对编码后的字符串解码
    	public double[] decode(String geohash) {
    		StringBuilder buffer = new StringBuilder();
    		for (char c : geohash.toCharArray()) {
    			int i = lookup.get(c) + 32;
    			buffer.append(Integer.toString(i, 2).substring(1));
    		}
    
    		BitSet lonset = new BitSet();
    		BitSet latset = new BitSet();
    
    		//偶数位,经度
    		int j = 0;
    		for (int i = 0; i < numbits * 2; i += 2) {
    			boolean isSet = false;
    			if (i < buffer.length())
    				isSet = buffer.charAt(i) == '1';
    			lonset.set(j++, isSet);
    		}
    
    		//奇数位,纬度
    		j = 0;
    		for (int i = 1; i < numbits * 2; i += 2) {
    			boolean isSet = false;
    			if (i < buffer.length())
    				isSet = buffer.charAt(i) == '1';
    			latset.set(j++, isSet);
    		}
    
    		double lon = decode(lonset, -180, 180);
    		double lat = decode(latset, -90, 90);
    
    		return new double[]{lat, lon};
    	}
    
    	public static void main(String[] args) {
    		GeoHash geoHash = new GeoHash();
    		// 北京站
    		String encode = geoHash.encode(39.910508, 116.433589);
    		System.out.println(encode);
    
    		// 天安门
    		System.out.println(geoHash.encode(39.913884, 116.403874));
    
    		// 首都机场
    		System.out.println(geoHash.encode(40.086109, 116.606819));
    
    		BitSet latbits = geoHash.getBits(39.913884, -90, 90);
    		BitSet lonbits = geoHash.getBits(116.403874, -180, 180);
    
    //		for (int i=0; i< latbits.length(); i++) {
    //			System.out.println(latbits.get(i));
    //		}
    
    		for (int i = 0; i < numbits; i++) {
    //			System.out.print(latbits.get(i));
    			System.out.print(latbits.get(i) ? '1' : '0');
    			System.out.print(" ");
    		}
    
    		System.out.println();
    		StringBuilder buffer = new StringBuilder();
    		for (int i = 0; i < numbits; i++) {
    			buffer.append((lonbits.get(i)) ? '1' : '0');
    			buffer.append((latbits.get(i)) ? '1' : '0');
    		}
    
    		System.out.println(buffer.toString());
    
    		System.out.println(geoHash.encode(39.913884, 116.403874));
    	}
    
    }
    

    写在最后

    如果嫌GeoHash算法麻烦,但是还想用它,没关系。
    Redis知道你懒Redis官网GeoHash用法

    展开全文
  • Hash算法的讲解

    千次阅读 2020-02-15 17:31:59
    散列表,又叫哈希表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的... 散列表(Hash table,也叫哈希表),是根据关键码值(Key value...

    散列表,又叫哈希表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,而是可能存在空隙。

          散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。比如我们存储70个元素,但我们可能为这70个元素申请了100个元素的空间。70/100=0.7,这个数字称为负载因子。我们之所以这样做,也 是为了“快速存取”的目的。我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置,这样就可以避免遍历性质的线性搜索,以达到快速存取。但是由于此随机性,也必然导致一个问题就是冲突。所谓冲突,即两个元素通过散列函数H得到的地址相同,那么这两个元素称为“同义词”。这类似于70个人去一个有100个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址,每个存储单位称为“桶”。设一个散列表有m个桶,则散列函数的值域应为[0,m-1]。      

         解决冲突是一个复杂问题。冲突主要取决于:

       (1)散列函数,一个好的散列函数的值应尽可能平均分布。

       (2)处理冲突方法。

       (3)负载因子的大小。太大不一定就好,而且浪费空间严重,负载因子和散列函数是联动的。      

         解决冲突的办法:     

       (1)线性探查法:冲突后,线性向前试探,找到最近的一个空位置。缺点是会出现堆积现象。存取时,可能不是同义词的词也位于探查序列,影响效率。     

       (2)双散列函数法:在位置d冲突后,再次使用另一个散列函数产生一个与散列表桶容量m互质的数c,依次试探(d+n*c)%m,使探查序列跳跃式分布。

    常用的构造散列函数的方法

      散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位:

      1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b,其中a和b为常数(这种散列函数叫做自身函数)

      2. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相 同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会 明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

      3. 平方取中法:取关键字平方后的中间几位作为散列地址。

      4. 折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。

      5. 随机数法:选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。

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

      散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按 处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平 均查找长度来衡量。

      查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:

      1. 散列函数是否均匀;

      2. 处理冲突的方法;

      3. 散列表的装填因子。

      散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度

      α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。

      实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。

      了解了hash基本定义,就不能不提到一些著名的hash算法,MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法,而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢?

      这里简单说一下:

      (1) MD4

      MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。

      (2) MD5

      MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好

      (3) SHA-1 及其他

      SHA1是由NIST NSA设计为同DSA一起使用的,它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。

      哈希表不可避免冲突(collision)现象:对不同的关键字可能得到同一哈希地址 即key1≠key2,而hash(key1)=hash(key2)。因此,在建造哈希表时不仅要设定一个好的哈希函数,而且要设定一种处理冲突的方法。可如下描述哈希表:根据设定的哈希函数H(key)和所选中的处理冲突的方法,将一组关键字映象到一个有限的地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置,这种表被称为哈希表。

      对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的 录在表中的位置,通常称这个函数f(key)为哈希函数。(注意:这个函数并不一定是数学函数)

      哈希函数是一个映象,即:将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可。

      现实中哈希函数是需要构造的,并且构造的好才能使用的好。

      那么这些Hash算法到底有什么用呢?

      Hash算法在信息安全方面的应用主要体现在以下的3个方面:

      (1) 文件校验

      我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检测并纠正数据传输中的信道误码,但却不能防止对数据的恶意破坏。

      MD5 Hash算法的"数字指纹"特性,使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。

      (2) 数字签名

      Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。 对 Hash 值,又称"数字摘要"进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

      (3) 鉴权协议

      如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。

    文件hash值

      MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何,它的Hash函数计算结果是一个固定长度的数字。与加密算法不 同,这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法,如MD5、SHA时,两个不同的文件几乎不可能得到相同的Hash结果。因 此,一旦文件被修改,就可检测出来。

          Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:
    1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。

    2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。

    3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。 应用于加密的Hash函数已经探讨过太多了,在作者的博客里面有更详细的介绍。所以,本文只探讨用于查找的Hash函数。 Hash函数应用的主要对象是数组(比如,字符串),而其目标一般是一个int类型。

    以下我们都按照这种方式来说明。 一般的说,Hash函数可以简单的划分为如下几类:

    1. 加法Hash; 2. 位运算Hash; 3. 乘法Hash; 4. 除法Hash; 5. 查表Hash; 6. 混合Hash;

    下面详细的介绍以上各种方式在实际中的运用。

     

    一 加法Hash

    所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    static int additiveHash(String key, int prime)

     

    {

     

    int hash, i;

     

    for (hash = key.length(), i = 0; i < key.length(); i++)  

     

    hash += key.charAt(i);

     

    return (hash % prime);

     

    }

      

    这里的prime是任意的质数,看得出,结果的值域为[0,prime-1]。

    二 位运算Hash

    这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。比如,标准的旋转Hash的构造如下:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    static int rotatingHash(String key, int prime) {

     

    int hash, i;

     

     for (hash=key.length(), i=0; i    hash = (hash<<4>>28)^key.charAt(i);

     

    return (hash % prime);

     

    }

      

    先移位,然后再进行各种位运算是这种类型Hash函数的主要特点。比如,以上的那段计算hash的代码还可以有如下几种变形:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    hash = (hash<<5>>27)^key.charAt(i);

     

     hash += key.charAt(i);

     

    hash += (hash << 10);

     

    hash ^= (hash >> 6);

     

     if((i&1) == 0) {

     

    hash ^= (hash<<7>>3);

     

    else {

     

    hash ^= ~((hash<<11>>5));

     

     } hash += (hash<<5> hash = key.charAt(i) + (hash<<6>>16) ? hash; hash ^= ((hash<<5>>2));

      

    三 乘法Hash

    这种类型的Hash函数利用了乘法的不相关性(乘法的这种性质,最有名的莫过于平方取头尾的随机数生成算法,虽然这种算法效果并不好)。比如,

    1

    2

    3

    4

    5

    6

    7

    static int bernstein(String key) {

     

    int hash = 0int i;

     

    for (i=0; i return hash;

     

    }

      

    jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过,它使用的乘数是31。推荐的乘数还有:131, 1313, 13131, 131313等等。 使用这种方式的著名Hash函数还有:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    // 32位FNV算法 int M_SHIFT = 0;  

     

    public int FNVHash(byte[] data)   {     

     

     int hash = (int)2166136261L;     

     

     for(byte b : data)          

     

    hash = (hash * 16777619) ^ b;      

     

    if (M_SHIFT == 0)          

     

    return hash;     

     

     return (hash ^ (hash >> M_SHIFT)) & M_MASK;

     

    }

      

    以及改进的FNV算法:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    public static int FNVHash1(String data) {     

     

     final int p = 16777619;   

     

       int hash = (int)2166136261L;     

     

     for(int i=0;i         

     

     hash = (hash ^ data.charAt(i)) * p;     

     

     hash += hash << 13;     

     

     hash ^= hash >> 7;     

     

     hash += hash << 3;     

     

     hash ^= hash >> 17;      

     

    hash += hash << 5;      

     

    return hash;

     

    }

      

    除了乘以一个固定的数,常见的还有乘以一个不断改变的数,比如:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    static int RSHash(String str) {      

     

    int b    = 378551;      

     

    int a    = 63689;     

     

     int hash = 0;

     for(int i = 0; i < str.length(); i++) {      

     

      hash = hash * a + str.charAt(i);      

     

      a    = a * b;      }   

     

      return (hash & 0x7FFFFFFF);

     

    }

      

    虽然Adler32算法的应用没有CRC32广泛,不过,它可能是乘法Hash里面最有名的一个了。关于它的介绍,大家可以去看RFC 1950规范。

    四 除法Hash

    除法和乘法一样,同样具有表面上看起来的不相关性。不过,因为除法太慢,这种方式几乎找不到真正的应用。需要注意的是,我们在前面看到的hash的  结果除以一个prime的目的只是为了保证结果的范围。如果你不需要它限制一个范围的话,可以使用如下的代码替代”hash%prime”: hash = hash ^ (hash>>10) ^ (hash>>20)。

    五 查表Hash

    查表Hash最有名的例子莫过于CRC系列算法。虽然CRC系列算法本身并不是查表,但是,查表是它的一种最快的实现方式。下面是CRC32的实现:

    static int crctab[256] = { 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,  0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,  0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,  0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,  0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,  0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d }; int crc32(String key, int hash) { int i; for (hash=key.length(), i=0; i   hash = (hash >> 8) ^ crctab[(hash & 0xff) ^ k.charAt(i)]; return hash; }

    查表Hash中有名的例子有:Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。
    六 混合Hash

    混合Hash算法利用了以上各种方式。各种常见的Hash算法,比如MD5、Tiger都属于这个范围。它们一般很少在面向查找的Hash函数里面使用

     

    作者:July、wuliming、pkuoliver

      说明:本文分为三部分内容, 第一部分为一道百度面试题Top K算法的详解;第二部分为关于Hash表算法的详细阐述;第三部分为打造一个最快的Hash表算法。

      第一部分:Top K 算法详解

      问题描述(百度面试题):

      搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

      必备知识:

      什么是哈希表?

      哈希表(Hash table,也叫散列表),是根据key而直接进行访问的数据结构。也就是说,它通过把key映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

      哈希表的做法其实很简单,就是把key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

        而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位文章第二、三部分,会针对Hash表详细阐述

      问题解析:

      要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。

      即,此问题的解决分为以下两个步骤:

      第一步:Query统计

      Query统计有以下俩个方法,可供选择:

      1、直接排序法

      首先我们最先想到的的算法就是排序了,首先对这个日志里面的所有Query都进行排序,然后再遍历排好序的Query,统计每个Query出现的次数了。

      但是题目中有明确要求,那就是内存不能超过1G,一千万条记录,每条记录是255Byte,很显然要占据2.375G内存,这个条件就不满足要求了。

      让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(nlogn)。

      排完序之后我们再对已经有序的Query文件进行遍历,统计每个Query出现的次数,再次写入文件中。

      综合分析一下,排序的时间复杂度是O(nlogn),而遍历的时间复杂度是O(n),因此该算法的总体时间复杂度就是O(n+nlogn)=O(nlogn)。

      2、Hash Table法

      在第1个方法中,我们采用了排序的办法来统计每个Query出现的次数,时间复杂度是O(nlogn),那么能不能有更好的方法来存储,而时间复杂度更低呢?

      题目中说明了,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query 255Byte,因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里,Hash Table绝对是我们优先的选择,因为Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度。

      那么,我们的算法就有了:维护一个Key为Query字串,Value为该Query出现次数的HashTable,每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(n)的时间复杂度内完成了对该海量数据的处理。

      本方法相比算法1:在时间复杂度上提高了一个数量级,为O(n),但不仅仅是时间复杂度上的优化,该方法只需要IO数据文件一次,而算法1的IO次数较多的,因此该算法2比算法1在工程上有更好的可操作性。

      第二步:找出Top 10

      算法一:普通排序

        我想对于排序算法大家都已经不陌生了,这里不在赘述,我们要注意的是排序算法的时间复杂度是O(nlogn),在本题目中,三百万条记录,用1G内存是可以存下的。

      算法二:部分排序

      题目要求是求出Top 10,因此我们没有必要对所有的Query都进行排序,我们只需要维护一个10个大小的数组,初始化放入10个Query,按照每个Query的统计次数由大到小排序,然后遍历这300万条记录,每读一条记录就和数组最后一个Query对比,如果小于这个Query,那么继续遍历,否则,将数组中最后一条数据淘汰,加入当前的Query。最后当所有的数据都遍历完毕之后,那么这个数组中的10个Query便是我们要找的Top10了。

      不难分析出,这样,算法的最坏时间复杂度是N*K, 其中K是指top多少。

      算法三:堆

      在算法二中,我们已经将时间复杂度由NlogN优化到NK,不得不说这是一个比较大的改进了,可是有没有更好的办法呢?

      分析一下,在算法二中,每次比较完成之后,需要的操作复杂度都是K,因为要把元素插入到一个线性表之中,而且采用的是顺序比较。这里我们注意一下,该数组是有序的,一次我们每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降到了logK,可是,随之而来的问题就是数据移动,因为移动数据次数增多了。不过,这个算法还是比算法二有了改进。

      基于以上的分析,我们想想,有没有一种既能快速查找,又能快速移动元素的数据结构呢?回答是肯定的,那就是堆。

      借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。

      思想与上述算法二一致,只是算法在算法三,我们采用了最小堆这种数据结构代替数组,把查找目标元素的时间复杂度有O(K)降到了O(logK)。

      那么这样,采用堆数据结构,算法三,最终的时间复杂度就降到了N‘logK,和算法二相比,又有了比较大的改进。 

      总结:

      至此,算法就完全结束了,经过上述第一步、先用Hash表统计每个Query出现的次数,O(N);然后第二步、采用堆数据结构找出Top 10,N*O(logK)。所以,我们最终的时间复杂度是:O(N)+N'*O(logK)。(N为1000万,N’为300万)。如果各位有什么更好的算法,欢迎留言评论。

      第二部分、Hash表算法的详细解析

      什么是Hash

      Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

      Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系。

      数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:

        左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

      元素特征转变为数组下标的方法就是散列法。散列法当然不止一种,下面列出三种比较常用的:

      1,除法散列法 

      最直观的一种,上图使用的就是这种散列法,公式: 

          index = value % 16 

      学过汇编的都知道,求模数其实是通过一个除法运算得到的,所以叫“除法散列法”。

      2,平方散列法 

      求index是非常频繁的操作,而乘法的运算要比除法来得省时(对现在的CPU来说,估计我们感觉不出来),所以我们考虑把除法换成乘法和一个位移操作。公式: 

          index = (value * value) >> 28   右移,除以2^28。记法:左移变大,是乘。右移变小,是除。

      如果数值分配比较均匀的话这种方法能得到不错的结果,但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题,value如果很大,value * value不会溢出吗?答案是会的,但我们这个乘法不关心溢出,因为我们根本不是为了获取相乘结果,而是为了获取index。

      3,斐波那契(Fibonacci)散列法

      平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。

      1,对于16位整数而言,这个乘数是40503。

      2,对于32位整数而言,这个乘数是2654435769。

      3,对于64位整数而言,这个乘数是11400714819323198485。

      这几个“理想乘数”是如何得出来的呢?这跟一个法则有关,叫黄金分割法则,而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列,即如此形式的序列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,…。另外,斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。

      对我们常见的32位整数而言,公式: 

      index = (value * 2654435769) >> 28

      如果用这种斐波那契散列法的话,那上面的图就变成这样了:

      很明显,用斐波那契散列法调整之后要比原来的取摸散列法好很多。 

      适用范围

      快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。

      基本原理及要点

      hash函数选择,针对字符串、整数、排列,具体相应的hash方法。 

      碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。

      扩展 

      d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。

      问题实例(海量数据处理) 

      我们知道hash 表在海量数据处理中有着广泛的应用,下面,请看另一道百度面试题:

      题目:海量日志数据,提取出某日访问百度次数最多的那个IP。

      方案:IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将IP直接存入内存,然后进行统计。 

      第三部分、最快的Hash表算法

      接下来,咱们来具体分析一下一个最快的Hash表算法。

      我们由一个简单的问题逐步入手:有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但...也只能如此了。

      最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数。当然,无论如何,一个32位整数是无法对应回一个字符串的,但在程序中,两个字符串计算出的Hash值相等的可能非常小,下面看看在MPQ中的Hash算法:

      函数一、以下的函数生成一个长度为0x500(合10进制数:1280)的cryptTable[0x500]

    void prepareCryptTable()
    { 
        unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
        for( index1 = 0; index1 < 0x100; index1++ )
        { 
            for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )
            { 
                unsigned long temp1, temp2;
                seed = (seed * 125 + 3) % 0x2AAAAB;
                temp1 = (seed & 0xFFFF) << 0x10; 
                seed = (seed * 125 + 3) % 0x2AAAAB;
                temp2 = (seed & 0xFFFF); 
                cryptTable[index2] = ( temp1 | temp2 ); 
           } 
       }
    } 

      函数二、以下函数计算lpszFileName字符串的hash值,其中dwHashType为hash的类型(在下面的函数三GetHashTablePos函数中调用此函数二),其可以取的值为0、1、2;该函数返回lpszFileName 字符串的hash值: 

    unsigned long HashString( char *lpszFileName, unsigned long dwHashType )
    { 
        unsigned char *key  = (unsigned char *)lpszFileName;
        unsigned long seed1 = 0x7FED7FED;
        unsigned long seed2 = 0xEEEEEEEE;
        int ch;
        while(*key != 0)
        { 
            ch = toupper(*key++);
            seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
            seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3; 
        }
        return seed1; 
    }

      Blizzard的这个算法是非常高效的,被称为"One-Way Hash"(A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)。举个例子,字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。

      是不是把第一个算法改进一下,改成逐个比较字符串的Hash值就可以了呢?答案是,远远不够。要想得到最快的算法,就不能进行逐个的比较,通常是构造一个哈希表(Hash Table)来解决问题。哈希表是一个大数组,这个数组的容量根据程序的要求来定义,例如1024,每一个Hash值通过取模运算 (mod) 对应到数组中的一个位置。这样,只要比较这个字符串的哈希值对应的位置有没有被占用,就可以得到最后的结果了,想想这是什么速度?是的,是最快的O(1),现在仔细看看这个算法吧:

    typedef struct
    {
        int nHashA;
        int nHashB;
        char bExists;
        ......
    } SOMESTRUCTRUE;

      一种可能的结构体定义?

      函数三、下述函数为在Hash表中查找是否存在目标字符串,有则返回要查找字符串的Hash值,无则,return -1.

    int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable ) 
    //lpszString要在Hash表中查找的字符串,lpTable为存储字符串Hash值的Hash表。
    { 
        int nHash = HashString(lpszString);  //调用上述函数二,返回要查找字符串lpszString的Hash值。
        int nHashPos = nHash % nTableSize; 
        if ( lpTable[nHashPos].bExists  &&  !strcmp( lpTable[nHashPos].pString, lpszString ) ) 
        //如果找到的Hash值在表中存在,且要查找的字符串与表中对应位置的字符串相同
        {  
            return nHashPos;    //则返回上述调用函数二后,找到的Hash值
        } 
        else
        {
            return -1;  
        } 
    }

        看到此,我想大家都在想一个很严重的问题:“如果两个字符串在哈希表中对应的位置相同怎么办?”,毕竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用“链表”,感谢大学里学的数据结构教会了这个百试百灵的法宝,我遇到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。事情到此似乎有了完美的结局,如果是把问题独自交给我解决,此时我可能就要开始定义数据结构然后写代码了。

      然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是:他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。 

      MPQ使用文件名哈希表来跟踪内部的所有文件。但是这个表的格式与正常的哈希表有一些不同。首先,它没有使用哈希作为下标,把实际的文件名存储在表中用于验证,实际上它根本就没有存储文件名。而是使用了3种不同的哈希:一个用于哈希表的下标,两个用于验证。这两个验证哈希替代了实际文件名。

      当然了,这样仍然会出现2个不同的文件名哈希到3个同样的哈希。但是这种情况发生的概率平均是:1:18889465931478580854784,这个概率对于任何人来说应该都是足够小的。现在再回到数据结构上,Blizzard使用的哈希表没有使用链表,而采用"顺延"的方式来解决问题,看看这个算法:

      函数四、lpszString为要在hash表中查找的字符串;lpTable为存储字符串hash值的hash表;nTableSize 为hash表的长度: 

    int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )
    {
        const int  HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
        int  nHash = HashString(lpszString, HASH_OFFSET);
        int  nHashA = HashString(lpszString, HASH_A);
        int  nHashB = HashString(lpszString, HASH_B);
        int  nHashStart = nHash % nTableSize;
        int  nHashPos = nHashStart; 
        while ( lpTable[nHashPos].bExists )
       {
         /* 如果仅仅是判断在该表中时候存在这个字符串,就比较这两个hash值就可以了,不用对结构体中的字符串进行比较。这样会加快运行的速度?减少hash表占用的空间?这种
    方法一般应用在什么场合?*/
           if (lpTable[nHashPos].nHashA == nHashA
           &&  lpTable[nHashPos].nHashB == nHashB )
           {
                return nHashPos;
           }
           else
           {
                nHashPos = (nHashPos + 1) % nTableSize;
           }
            if (nHashPos == nHashStart) break;
        }
         return -1;
    }

      上述程序解释:

      1. 计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)

      2. 察看哈希表中的这个位置

      3. 哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回-1。

      4. 如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返回其Hash值。

      5. 移到下一个位置,如果已经移到了表的末尾,则反绕到表的开始位置起继续查询 

      6. 看看是不是又回到了原来的位置,如果是,则返回没找到

      7. 回到3

      ok,这就是本文中所说的最快的Hash表算法。什么?不够快?:D。欢迎,各位批评指正。

      --------------------------------------------

      补充1、一个简单的hash函数:

    /*key为一个字符串,nTableLength为哈希表的长度
    *该函数得到的hash值分布比较均匀*/
    unsigned long getHashIndex( const char *key, int nTableLength )
    {
        unsigned long nHash = 0;
        while (*key)
        {
            nHash = (nHash<<5) + nHash + *key++;
        }
        return (nHash % nTableLength);
    }

      补充2、一个完整测试程序:  

      哈希表的数组是定长的,如果太大,则浪费,如果太小,体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数。当然,根据不同的数据量,会有不同的哈希表的大小。对于数据量时多时少的应用,最好的设计是使用动态可变尺寸的哈希表,那么如果你发现哈希表尺寸太小了,比如其中的元素是哈希表尺寸的2倍时,我们就需要扩大哈希表尺寸,一般是扩大一倍。 

        下面是哈希表尺寸大小的可能取值:

         17,            37,          79,        163,          331,  

        673,           1361,        2729,       5471,         10949,        

       21911,          43853,      87719,      175447,      350899,

      701819,         1403641,    2807303,     5614657,     11229331,   

     22458671,       44917381,    89834777,    179669557,   359339171,  

    718678369,      1437356741,  2147483647

      以下为该程序的完整源码,已在Linux下测试通过:

    #include <stdio.h>  
    #include <ctype.h>     //多谢citylove指正。  
    //crytTable[]里面保存的是HashString函数里面将会用到的一些数据,在prepareCryptTable  
    //函数里面初始化  
    unsigned long cryptTable[0x500];  
    //以下的函数生成一个长度为0x500(合10进制数:1280)的cryptTable[0x500]  
    void prepareCryptTable()  
    {   
        unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;  
        for( index1 = 0; index1 < 0x100; index1++ )  
        {   
            for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )  
            {   
                unsigned long temp1, temp2;  
                seed = (seed * 125 + 3) % 0x2AAAAB;  
                temp1 = (seed & 0xFFFF) << 0x10;  
                seed = (seed * 125 + 3) % 0x2AAAAB;  
                temp2 = (seed & 0xFFFF);  
                cryptTable[index2] = ( temp1 | temp2 );   
           }   
       }   
    }  
    //以下函数计算lpszFileName 字符串的hash值,其中dwHashType 为hash的类型,  
    //在下面GetHashTablePos函数里面调用本函数,其可以取的值为0、1、2;该函数  
    //返回lpszFileName 字符串的hash值;  
    unsigned long HashString( char *lpszFileName, unsigned long dwHashType )  
    {   
        unsigned char *key  = (unsigned char *)lpszFileName;  
    unsigned long seed1 = 0x7FED7FED;  
    unsigned long seed2 = 0xEEEEEEEE;  
        int ch;  
        while( *key != 0 )  
        {   
            ch = toupper(*key++);  
            seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);  
            seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;   
        }  
        return seed1;   
    }  
    //在main中测试argv[1]的三个hash值:  
    //./hash  "arr/units.dat"  
    //./hash  "unit/neutral/acritter.grp"  
    int main( int argc, char **argv )  
    {  
        unsigned long ulHashValue;  
        int i = 0;  
        if ( argc != 2 )  
        {  
            printf("please input two arguments/n");  
            return -1;  
        }  
         /*初始化数组:crytTable[0x500]*/  
         prepareCryptTable();  
         /*打印数组crytTable[0x500]里面的值*/  
         for ( ; i < 0x500; i++ )  
         {  
             if ( i % 10 == 0 )  
             {  
                 printf("/n");  
             }  
             printf("%-12X", cryptTable[i] );  
         }  
         ulHashValue = HashString( argv[1], 0 );  
         printf("/n----%X ----/n", ulHashValue );  
         ulHashValue = HashString( argv[1], 1 );  
         printf("----%X ----/n", ulHashValue );  
         ulHashValue = HashString( argv[1], 2 );  
         printf("----%X ----/n", ulHashValue );  
         return 0;  
    }  

     

    展开全文
  • Hash算法实验

    2013-05-13 19:42:34
    密码学实验六 利用LibTomCrypt密码算法库中提供的MD5相关函数对一个文件进行处理,计算该文件的Hash值,提交程序代码和运算结果;
  • Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 352,234
精华内容 140,893
关键字:

hash算法

友情链接: 0Bootstrap.zip