分布式集群架构场景化解决方案学习笔记：Hash算法的介绍及应用场景
Hash 算法的使用
在安全加密领域MD5、SHA等加密算法，在数据存储和查找方面有Hash表等都应用到了Hash算法
问题： 为什么需要使用 Hash 算法？
Hash算法较多的应用在数据存储和查找领域，最经典的就是Hash表，它的查询效率非常高，如果哈希算法设计的好，那么Hash表的数据查询时间复杂度可以接近于O(1)
Hash 算法使用示例
需求:
提供一组数据1，5，7，6，3，4，8，对这组数据进行存储，然后随便给定一个数n，请你判断n是否存在于刚才的数据集中？
-
顺序查找法：
这种方式就是通过循环来完成，比较原始，效率也不高 -
二分查找法：
排序之后折半查找，相对于顺序查找法会提高一些效率，但是效率也并不是特别好 -
直接寻址法：
直接把数据和数组的下标绑定到一起，查找的时候，直接array[n]就取出了数据
优点： 速度快，一次查找得到结果
缺点：浪费空间（数据：1，3，7，12306），单个索引上存储内容有限（数据：1，1，2，12，12，1，1） -
除留取余法
根据求模余数确定存储位置的下标 -
开放寻址法
如果数据是 1，6，7，8 采用除留取余法则会造成hash冲突，此时可以采用开放寻址法，比如：1放进去了，6再来的时候，向前或者向后找空闲位置存放
缺点： 如果数组长度定义好了，比如10，由于数组长度不能扩展，来了11个数据，不管Hash冲突不冲突，肯定存不下这么多数据 -
拉链法
数据长度定义好了，怎么存储更多内容呢，算好Hash值，在数组元素存储位置放了一个链表
总结： Hash表的查询效率高不高取决于Hash算法，Hash算法能够让数据平均分布，既能够节省空间又能提高查询效率
Hash 算法在分布式集群架构中的应用场景
Hash算法在很多分布式集群产品中都有应用，比如：分布式集群架构Redis、Hadoop、ElasticSearch，Mysql分库分表，Nginx负载均衡等
请求的负载均衡
-
nginx的ip_hash策略
Nginx的ip_hash策略可以在客户端ip不变的情况下，将其发出的请求始终路由到同一个目标服务器上，实现会话粘滞，避免处理session共享问题
问题： 如果没有ip_hash策略，那么如何实现回话沾滞？答：可以维护一张映射表，存储客户端IP或者sessionid与具体目标服务器的映射关系，但是存在缺点
缺点：
- 在客户端很多的情况下，映射表非常大，浪费内存空间
- 客户端上下线，目标服务器上下线，都会导致重新维护映射表，映射表维护成本很大
解决方案： 如果使用哈希算法，事情就简单很多，我们可以对ip地址或者sessionId进行计算哈希值，哈希值与服务器数量进行取模运算，得到的值就是当前请求应该被路由到的服务器编号，如此，同一个客户端ip发送过来的请求就可以路由到同一个目标服务器，实现会话粘滞。
分布式存储
问题：以分布式内存数据库Redis为例，集群中有redis1，redis2，redis3三台Redis服务器，那么，在进行数据存储时，<key1,value1> 数据存储到哪个服务器当中呢?答：针对key进行hash处理 hash(key)%3=index，使用余数index锁定存储的具体服务器节点