哈希算法详解,哈希 算法
前言
程序员应该对hash算法比较熟悉，比如MD5、SHA、CRC等等，业界比较知名的；在日常开发中，我们经常使用一个Map加载一些(key，value)结构的数据，利用hash算法O(1)的时间复杂度来提高程序的处理效率。另外，你知道哈希算法的其他应用场景吗？
1. 什么是哈希算法？
在了解哈希算法的应用场景之前，我们先来看看散列（哈希）思想。哈希是通过哈希算法将任意长度的输入转换成固定长度的输出。输入称为key，输出为hash值，即hash值(Key)，哈希算法为hash()函数(散列与哈希是对hash的不同翻译)；实际上，这些哈希值存储在一个数组中，这个数组称为哈希表。哈希表利用数组支持按下标随机访问数据的特性，根据哈希函数将数据值和数组下标一一映射，实现O(1)的时间复杂度查询。
如何解决写爬虫IP受阻的问题？立即使用。
1.1 散列冲突
当前的哈希算法MD5、SHA、CRC等。无法实现一个hash函数，不同的hash值对应不同的键，即无法避免不同的键映射到同一个值的情况，即出现散列冲突。而且由于数组的存储空间有限，也会增加哈希冲突的概率。如何解决哈希冲突？有两种常用的哈希冲突解决方法：开放寻址和链接。
1.1.1 开放寻址法
通过线性检测找到哈希表中的空闲位置，写入哈希值：
如图所示，834313已经被哈希到哈希表中303432的位置。如果有冲突，将依次遍历哈希表，直到找到一个空闲位置，并写入834313。当哈希表中空闲槽不多时，哈希碰撞的概率会大大增加。一般情况下，我们会尽量保证哈希表中有一定比例的空闲槽。此时，我们用装载因子来表示空闲槽的数量。计算公式为：哈希表的加载因子=表中填充的元素数/哈希表的长度。负载因子越大，空闲空间越少，冲突越多，哈希表的性能会下降。
当数据比小，负载因子小时，适合采用开放式寻址方式，这也是java中ThreadLocalMap使用开放式寻址方式解决哈希冲突的原因。
1.1.2 链表法
链表方法是比较常用的哈希冲突解决方法，也比较简单。如图所示：
在哈希表中，每个桶/槽都会对应一个链表，所有哈希值相同的元素都会放入同一个槽对应的链表中；当哈希冲突较多时，链表的长度会变长，查询哈希值需要遍历链表，那么查询效率会从O(1)退化到O(n)。
这种解决哈希冲突的方法更适合对象大、数据量大的哈希表，支持更多的优化策略，比如用红黑树代替链表；Jdk1.8引入了红黑树来进一步优化HashMap。当链表的长度过长时(默认值超过8)，链表会被转换成红黑树。这时候可以利用红黑树的快速添加、删除和修正的特性来提高HashMap的性能。当红黑树的节点数小于8时，红黑树会被转换成链表，因为当数据比例较小时，红黑树需要保持平衡。与链表相比
2. 哈希算法的应用场景
2.1 安全加密
最常用的加密哈希算法是MD5(MD5消息摘要算法)和SHA(安全哈希算法)。利用哈希的特性，很难逆向推导出原始数据，从而达到加密的目的。
以MD5为例，哈希值是固定的128位二进制字符串，最多能代表2 ^ 128个数据。这个数据已经是天文数字了，哈希碰撞的概率不到1/2 128。如果想通过穷举法找到另一个和MD5相同的数据，需要天文数字的时间，所以哈希算法在有限的时间内还是很难被破解，从而达到加密的效果。
2.2 数据校验
利用散列函数对数据敏感的特性，它可以用来检查pro中的数据是否
2.3 散列函数
利用hash函数相对于均匀分布的特性，将hash值作为数据存储的位置值，使数据在容器中均匀分布。
2.4 负载均衡
通过哈希算法，计算客户端id地址或会话id的哈希值，将得到的哈希值与服务器列表的大小取模。最后一个值是应该路由到的服务器号。
2.5 数据分片
如果我们有一个1T的日志文件，记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，怎么办？数据量比较大，很难放在一台电脑的内存里。即使放在一台电脑上，处理时间也会很长。要解决这个问题，可以先把数据切片，然后用多台机器处理，提高处理速度。
具体思路是：为了提高处理速度，我们用N台机器并行处理。从搜索记录的日志文件中，依次留下每个搜索关键字，通过哈希函数计算哈希值，然后取模n，最后的值就是应该赋值的机器号；这样，哈希值相同的搜索关键词被分配到同一台机器上，每台机器会分别计算关键词出现的次数，最后合并出最终的结果。其实这里的处理也是MapReduce的基本设计思路。
2.6 分布式存储
对于海量数据需要缓存的情况，一台缓存机肯定是不够的，所以我们需要将数据分布在多台机器上。
这时候可以利用前面的分片思路，即通过哈希算法得到数据的哈希值，然后对机器数取模，从而得到应该存储的缓存机器数。
但是如果数据增加，原来的10台机器承受不了，需要扩容。此时，如果重新计算所有数据，然后再次移动到正确的机器上，就意味着所有缓存的数据会一下子失效，会经过缓存返回数据库，可能会造成雪崩效应，压垮数据库。为了在不移动所有数据的情况下添加缓存机器，一致性哈希算法是更好的选择。主要思路是：假设我们有一台kge机器，数据的哈希值范围是[0，Max]。我们把整个范围分成m个小区(m远大于k)，每台机器负责m/k个小区。当添加新机器时，我们将从
3. 写在最后
其实哈希算法还有很多其他的应用，比如git commit id等。很多应用来自于对算法的理解和扩展，也是基础数据结构，是算法价值的体现。需要我们在工作中慢慢去理解和体会。
推荐教程：《Java教程》以上是常用算法的hash算法的详细内容。更多请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。