hash 算法原理及应用漫谈( 二 ) _hash算法

散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大，说明冲突越多，性能越差。
3.3 两种方案的demo示例
假设散列长为8，散列函数H(K)=K mod 7，给定的关键字序列为{32,14,23,2, 20}
当使用链表法时，相应的数据结构如下图所示：

文章插图
链表法demo
当使用线性探测法时，相应的数据结果如下图所示：

文章插图
开放地址-线性探测法
这里的两种算法的区别是2这个元素，在链表法中还是在节点2的位置上，但是在线性探测法遇到冲突时会将冲突数据放到下一个空的位置下面。
4、hash算法在日常活动中的应用
在日常运营活动中，我们活动开发经常遇到的应用场景是信息加密、数据校验、负载均衡。下面分别对这三种应用场景进行讲解。
4.1 信息加密
首先我们看一下信息加密的应用。2011年CSDN脱库事件，导致超过600W的用户的密码泄露，让人失望的是，CSDN是明文存储用户的注册邮箱和密码的。作为用户的非常隐私的信息，最简单的保护措施就是对密码进行hash加密。在客户端对用户输入的密码进行hash运算，然后在服务端的数据库中保存用户密码的hash值。由于服务器端也没有存储密码的明文，所以目前很多网站也就不再有找回密码的功能了。

这里也友情提示一下大家：如果在使用中发现某网站还有提供找回密码的功能，就要好好担心下这个网站的安全性了。

看到这里有些同学会觉得那么我们是不是对用户输入的密码进行一次MD5加密就可以了呢，这样就算恶意用户知道了hash值，也没有办法拿到用户的真实密码。假设用户的密码是123456789，经过一次md5以后得到的值是:
25f9e794323b453885f5181f1b624d0b
那么是不是使用了这个加密后的字符串来存密码就万无一失了呢，理想总是很丰满，而现实总是很骨感的。
大家可以看一下这个网站：
https://www.cmd5.com/
这里是该网站的相关介绍：

本站针对md5、sha1等全球通用公开的加密算法进行反向查询，通过穷举字符组合的方式，创建了明文密文对应查询数据库，创建的记录约90万亿条，占用硬盘超过500TB，查询成功率95%以上，很多复杂密文只有本站才可查询。已稳定运行十余年，国内外享有盛誉

文章插图
md5反查结果
那么一般针对这种问题，我们的解决之道就是引入salt(加盐)，即利用特殊字符（盐）和用户的输入合在一起组成新的字符串进行加密。通过这样的方式，增加了反向查询的复杂度。但是这样的方式也不是万无一失，如果发生了盐被泄露的问题，就需要所有用到的地方来重置密码。
针对salt泄露的问题，其实还有一种解决办法，即使用Hmac进行加密（Hash-based Message Authentication Code）。这种算法的核心思路是加密使用的key是从服务器端获取的，每一个用户的是不一样的。如果发生了泄露，那么也就是这一个用户的会被泄露，不会影响到全局。
这里也留给大家一个思考点，如果恶意用户直接抓取了你的活动参与链接，也就是拿到了你计算后的hash值，那从技术的角度上说，我们还有没有其他可以提升恶意用户的违法成本呢？
4.2 数据校验
- git commit id
使用过git的同学都应该清楚，每次git提交后都有一个commit id，比如:
19d02d2cc358e59b3d04f82677dbf3808ae4fc40
就是一次git commit的结果，那么这个id是如何生成出来的呢？查阅了相关资料，使用如下代码可以进行查看：
printf "commit %s" $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD
git的commit id主要包括了以下几部分内容：Tree 哈希，parent哈希、作者信息和本次提交的备注。