数据结构哈希算法

哈希表是一种数据结构～

哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录， 那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。 (关键字就是所要存储的数据，存储位置相当于数组的索引)

当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到

eg1. 将26个小写字母存储到数组  int [26] a。

a对应a[0]，b对应a[1]，c对应a[3]……以此类推。

那么，数组 int [26] a 就是一个哈希表！

例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？

关键字的ASCII值减去a的ASCII值！

上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。

这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。

关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要O(1)的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。

哈希表中 哈希函数的设计 是相当重要的，这也是建哈希表过程中的关键问题之一。

假如，我们所要存储的数据其关键字是一个人的身份证号(18位数字)，这个时候我们该怎么计算关键字对应的索引呢？

比如一个人的身份证号是 411697199702076425，我们很难像例1那样直接让关键字与数字建立一一对应的关系，并且保证数字适合作为数组的索引。

在这种情况下，通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。这就是 哈希冲突

当索引相同时，我们该怎么存储数据呢？如何解决哈希冲突，是我们建哈希表的另一个关键问题。

哈希表充分体现了空间换时间这种经典的算法思想。

关键字是大整数时，比如上面我们举的身份证号例子，411697199702076425

假如我们能开辟一个 999999999999999999 大的空间，这样就能直接把身份证号作为关键字存储到数组中，这样可以用O(1)时间完成各项操作

假如我们只有 1 的空间，我们需要把所有信息存储到这个空间中(也就是所有数据都会产生哈希冲突)，我们只能用O(n)时间完成各项操作

事实上，我们不可能开辟一个如此大的空间，也不可会开辟如此小的空间

无限空间时，时间为O(1)

1的空间时，时间为O(n)

而哈希表就是在二者之间产生一个平衡，即 空间和时间的平衡 。

1.哈希函数的设计

2.解决哈希冲突

3.哈希表实现时间和空间的平衡

后续会详细说明这三个关键问题～

有一个人每次打开区块链文章，都意气风发，暗暗下决心要发愤图强，看了一会儿，发现很难看懂什么，硬逼着自己学习，却已是强弩之末，最后只能末学肤受，学了个皮毛而已。

那个人就是我哈，希望大家不要末学肤受，而能食髓知味，深刻理解区块链知识。

这四个成语。

意气风发～发奋图强～强弩之末～末学肤受

每个成语的第一个字，是前一个成语的最后一个字，组成了一个成语链的链式结构。

我们来类比一下，区块链的链式结构。

区块链0，1，2，3的链式结构是靠什么形成的呢？

是靠前一个区块的哈希值，也叫做父区块哈希值。

区块0是区块1的父区块。

区块1是区块0的子区块。

区块0的哈希值对区块1而言，就是父区块的哈希值。

父区块哈希值，就是上面成语链式结构里，把前后两个成语连接起来的那个字。

要理解区块链链式结构，还要理解什么叫哈希。

再讲个故事哈。

小黑同学要把一袋猫粮快递给大白老师。

他让哈希公司的快递员上门取件，打包完成后，拿到了快递单号。

这个寄快递的过程中，有三个关键步骤。

1.选择要寄送的物品。

2.选择哈希快递公司，对物品进行快递打包。

3.拿到快递单号。

哈希公司给的快递单号就是哈希值。

大白老师对小黑选择的哈希公司很满意。

1.不论小黑寄的东西有多大，经过哈希公司打包后，拿到手的快递包裹都一样大。

2.哈希公司打印出来的快递单号也就是哈希值，除了让你查询物流的实时状况，还可以让你知道包裹中的物品有没有被人调包或撰改。

比如小黑寄给大白的猫粮，在运送过程中，哪怕袋子上的配料表，被人改了一个标点符号，哈希公司给的快递单号，也就是哈希值都会实时发生变化，警示小黑快递包裹发生了异常情况。

哈希公司确实很厉害哈。

哈希算法就是一种特殊的函数，不论输入多长的一串字符，只要通过这个函数都可以得到一个固定长度的输出值，这就好像身份证号码一样，永远都是十八位而且全国唯一。

哈希算法的输出值就叫做哈希值。哈希算法也被称为“散列”，是区块链的四大核心技术之一。是能计算出一个数字消息所对应的、长度固定的字符串。

哈希算法原理：

Hash算法的原理是把输入空间的值映射到Hash空间内，由于Hash值的空间远小于输入的空间，而且借助抽屉原理 ，可以得出一定会存在不同的输入被映射成相同输出的情况，如果一个Hash算法足够好，那么他就一定会有更小的发生冲突的概率，也就是说，一个好的Hash算法应该具有优秀的 抗碰撞能力。

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

MD5信息摘要算法 （英语：MD5 Message-Digest Algorithm），一种被广泛使用的 密码散列函数 ，可以产生出一个128位（16 字节 ）的散列值（hash value），用于确保信息传输完整一致。2004年，证实MD5算法无法防止碰撞（collision）（如网站： CMD5 ），因此不适用于安全性认证，如 SSL 公开密钥认证或是 数字签名 等用途。

MD5 是哈希算法的一种。

密码加密常见的有以下几种方式：

HMAC是密钥相关的哈希运算消息认证码（Hash-based Message Authentication Code）的缩写，并在 IPSec 和其他网络协议（如 SSL ）中得以广泛应用，现在已经成为事实上的Internet安全标准。它可以与任何迭代散列函数捆绑使用。

如上图中，共有两个流程：

授权设备登录流程：

1、输入账号过后，就把账号作为参数向服务器发送请求

2、服务器根据账号生成对应的key，并传递给客户端

3、客户端拿到key，进行HMAC运算，并将运算结果的哈希值传给服务器

其他设备登录流程：

1、输入账号过后，在本地缓存中找服务器传过来的key，有就登录，没有就把账号作为参数向服务器发送请求

2、服务器要先看这个账号是否开启了设备锁，没有开启就不允许登录，开启了，就向授权设备发送请求，是否授权，如果授权，就将这个账号的key传给其他客户端

3、客户端拿到key，进行HMAC运算，并将运算结果的哈希值传给服务器

但是在这之中有一个潜在的安全隐患问题： 当别人拿到账号和传递的哈希值过后，也就能拿到登录权限，从而不安全。

为了防止上面的问题，注册流程不变，服务器还是保存的有加了key的HMAC哈希值。

1、只是登录的时候，客户端将哈希值与时间戳拼接过后，进行MD5加密，再传给服务器。

2、服务器将注册保存的账号对应的HMAC哈希值，分别与当前时间，和前一分钟拼接再MD5加密，再和客户端传过来的进行匹配，匹配成功则登录成功，否则不成功。

3、注意这里的时间戳是服务器给的时间戳。

常见的加密算法：

应用模式：

AES加密解密都是用到的CCCrypt函数，并且需要导入 CommonCrypto 框架。

纳税人识别号是税务登记证上的号码，通常简称为“税号”，每个企业的纳税人识别号都是唯一的。这个属于每个人自己且终身不变的数字代码很可能成为我们的第二张“身份证”。

2015年1月12日，根据国家税务总局本周公布的《中华人民共和国税收征收管理法修订草案(征求意见稿)》，未来每个公民可能都将拥有一个由税务部门编制的唯一且终身不变、用来确认其身份的数字代码标识。

关键字 2 8 31 20 19 18 53 27 （18）

哈希地址2 8 5 7 6 5 1 1 5

有冲突

13个元素 0 1 2 3 4 5 6 7 8 9 10 11 12

219 8

有冲突处理 第一个 18冲突 哈系地址（5+1）%13 求 的6 6号位置有冲突 则（5+2）%13=7 kan 7号位置是否有冲突 有则类推 没有则填如就可以

显然不合适。因为，并不是所有的身份证号都是18位的，对于那些位数在17位以下的，就太浪费这个大空间了。

设计哈希函数的原则是，将我们所关心的键通过哈希函数求出索引， “键”通过哈希函数得到的“索引”分布越均匀越好 (实际上，实现起来非常困难)

那么，对于像身份证号这样的大整数为关键字时，该怎么计算对应的索引呢？

或者像复合类、字符串、浮点数这样类型的关键字，该如何计算它们对应的索引呢？

对于哈希函数来说，我们只能将整型数据作为关键字来求解索引。所以，不管什么类型的关键字，我们应该先将其转化为整型类型的数据。

按照这个思路，以下介绍几种最简单、最基础、最一般、最通用的哈希函数

小范围正整数直接使用

例如，上一篇讲的ASCII值作为关键字

再例如，一个班有30个学生，1—30表示每位学生对应的学号，并作为关键字

像这样的小范围正整数，可以直接将关键字作为索引，存储到数组中去

小范围负整数进行偏移

例如，-100～100的数作为关键字，这时可以每个数都加上100，变为0～200的正整数

这样，就可以将关键字直接作为索引存储到数组中去

大整数取模

例如，身份证号作为关键字，412637199707096354

取后四位(6354)。也就是，mod 10000

假如，取后六位(096354)。即，mod 100 0000 这样，会 分布不均匀

对于身份证号来说，后六位的前两位(09)代表着日期数，也就是1～31的数字。那么，这个六位数不会达到32 0000这么大，中国这么多人口，显然这个数字是不够的，这也就造成了索引分布不均匀

这也就体现了哈希函数的复杂性，也说明了具体问题要具体分析。

上面的取模方式还有一个问题，没有 有效利用所有信息。 我们这样取模，只是利用了关键字的一部分，也就是不管这个人是哪个地区哪个年份出生的，都有可能存储到一个地址中去，这样会增加哈希冲突的概率。那么，该如何解决这个问题呢？

一个简单的解决办法： 模一个素数

为什么要模一个素数呢？简单举个例子

显然，模一个素数，结果会分布的更均匀，哈希冲突的概率也会变小。我们该如何选择这个素数呢？相关的领域专家已经为我们研究出了答案。

假如，需要存储的数在2^5～2^6之间，模上53就可以了。

注：这个表并不是唯一的，一个区间内可以有多个素数

将浮点型解析成大整型，之后再相应取模(如上)

先看一个例子

把一个整数用科学计数法来表示，同样，字符串也可以类似表示。将这个字符串看成26进制，是因为有26个小写字母，如果字符串中有大写字母或者标点符号，那么看成26进制显然是不够的，可以看成是100进制或者256进制等。显然，这个进制是用户可以自己选择的，我们用 B 来表示这个进制

每一个小写字母对应一个数字，这样我们把字符串也转化成了大整型，之后就可以利用上面取模的方式计算哈希值了。

这样就可以计算出字符串的哈希值了。当B是一个比较大的数或者字符串比较长时，求B的k次方是比较浪费时间的，所以我们可以优化这个表达式

这样就省去了求次方运算。但是，还有可能会出现整型溢出的情况，当B是一个很大的数字或者字符串很长的时候，我们可以再次优化这个表达式

这样，每退出一个小括号，数字都会变成比M先得数字，就不会出现溢出情况了

假如我们自己定义一个类，日期类

Date：year，month，day

为这个Date类设计哈希函数，可以像字符串那样，将类的属性值看着是一个字符

这样，就求出了复合类的哈希值。

一致性： 当关键字相同时，经过哈希函数求出的哈希值也是相同的。

反过来是不成立的，即当哈希值相同时关键字不一定相同。哈希值相同，取模后得到的索引也相同，即不同的关键字对应的存储位置相同，这也就是所谓的哈希冲突。

高效性： 我们设计哈希函数就是为了高效存储数据，如果哈希函数的设计就消耗过多性能，那么就得不偿失了

均匀性： 通过哈希函数求出的索引必须是分布均匀的。

以上，就是转化为整型求哈希函数。但是， 这并不是求哈希函数唯一的方法 。

通常用户在交易所进行转账，交易所就会提供给用户一个相应的哈希值。

哈希值相当于银行转账的交易号，通过哈希值用户可以查询到转账的具体进程。

因为电话号码不重复，所有你的hashCode=区号+电话号就可以。

不用再加其他的了。

但是注意通常，从写hashcode后，根据程序业务通常需要重写equals方法。