HASH GAME - Online Skill Game GET 300

　　三、一致性hash算法的优缺点一致性hash算法的优点有很多，其中最主要的优点有以下几点：1.可以实现负载均衡，可以有效的减少服务器的负载；2.能够实现数据的分布式存储，可以提高系统的可用性；3.算法的实现比较简单，易于理解和实施；4.可以轻松的添加或删除节点，而不会影响系统的整体性能；虽然一致性hash算法有很多优点，但它也有一些缺点，其中最主要的缺点有以下几点：1.一致性hash算法只适用于有限的节点数，当节点数增加时，算法的效率会急剧下降；2.当节点数量发生变化时，会导致数据的重新分布，这可能会导致系统的性能下降；3.当数据量增加时，数据分布的时间会随之增加，从而降低系统的效率。

　　ａ ｌ ｐｐ ｙｍｅ ｔ ｏ ｏ ｉｔ ｎ ｈ ｓ ｉ ｌ ｏ ｉｈｍ ｉ ｈｅ ｄ ｓ ｒ ｂ ｅ ｙｓ ｅ ｉ ｅ ａｌ ａ ｄ ｓ ｎ ｆ ｃ ｎｓｓ ｅ ｔ ａ ｈ ｎｇ ａ ｇ ｒ ｔ ｎ ｔ ｉ ｔ ｉ ｕｔ ｄ ｓ ｔ ｍ ｎ ｄ ｔ ｉ ｎ ｕｍｓ ｐ ｔ ｄ ａ ａ ｏ ｕ ｈｅ ａ ｖ ｎｔ ｇｅ ｆ ｃ ｎｓｓ ｅ ｔｈａ ｈ ｎ ｌ ｒｔ ｍ ． ｏ ｉｔ ｎ ｓ ｉ ｇ ａｇｏ ｉｈ

　　1.3 初步优化 因为耗时最⼤的是server连接machine的时候，所以决定在server端缓存machine的连接，经过测试如果通过使⽤的连接缓存进⾏查询，那么耗时将控制在1秒以内，满⾜了⽤户的要求，不过还有⼀个问题因此产⽣，那就是根据现有负载均衡算法，假如server1已经缓存了到machine1的连接，但是再次查询时，请求就会发送到下⼀个server，如server2，这就导致了两个问题，⼀是，重新建⽴了连接耗时较长，⼆是，两个server同时缓存着到machine1的连接，造成了连接浪费。

　　但是因为server端是集群，机器有可能动态的增加或减少，假如根据hash计算，指定的 machine会被指定的server连接，如下图： 然后⼜增加了⼀个server，那么根据当前的hash算法，server和machine的连接就会变成如下： 可以发现，四个machine和server的连接关系发⽣变化了，这将导致4次连接的初始化，以及四个连接的浪费，虽然server集群变动的⼏率很⼩，但是每变动⼀次将有⼀半的连接作废掉，这还是不能接受的，当时想的最理想的结果是：当新增机器的时候，原有的连接分⼀部分给新机器，但是除去分出的连接以外保持不变当减少机器的时候，将减少机器的连接分给剩下的机器，但剩下机器的原有连接不变 简单来说，就是变动不可避免，但是让变动最⼩化。

　　哈希算法相关解析1、散列法（哈希算法）--原理：一种高效的存储方式，是利用空间换取时间的快速查找算法通过哈希函数将关键码映射到不同的位置，已达到快速查找的功能假如关键码有40个，哈希表的位置有50个，通过哈希函数将这40个数以一定的规律映射到表中，在你查找的时候直接调用函数就可以找到，但是，因为这个哈希函数是自己定义的，就可能会存在将两个关键码映射到同一块地址上，就会出现哈希冲突，要是关键码的个数大于哈希表的值，不仅会存在冲突问题吗，还会存在溢出问题，则必须对位置取余操作。

　　--冲突原因：1、处理冲突的方法是否恰当2、哈希函数分配不够均匀3、a负载因子太小（关键码-哈希表长度）a越大，则哈希表的剩余空间越小，冲突概率越高--解决冲突的方法：一、开放定址法1、线性探测：（步数为一步）j = (j+1)%num当插入关键码时，如果发生冲突，可依次向后探测（每次走一步），直到找到一个空的位置然后插入当进行查找操作时，如果定位的地址没有值，则不存在，如果定位的位置有值，则依次往后探测，直到遇到要查找的关键码，如果遇到了空地址还没有找到，则不存在--缺点：--1、堆聚现象：如果插入时，探测的次数比较多，那就带来一定的效率问题，而且假如每次插入都需要探测，则冲突的可能性大大增强，产生堆聚现象（存在关键码全部连成--2、删除出错：删除时，本来我们只需要找到这个位置，然后清零操作，但是，由于可能会存在冲突，影响后续的操作（这个位置后面还有与它相同的属性探测，当置0时，后面就找不到了），所以我们只能将此位置设置为已删除的标记--3：浪费空间当为了减少冲突时，就会要求负载因子较小，则肯定会浪费空间2、线性补偿探测（步数为n步）j =(j+n)%num（也可以理解为二次探测）当冲突时，再利用一个哈希函数探测一个位置当插入关键码时，如果发生冲突，可依次向后探测（每次走n步）或者再利用一个函数，直到找到一个空的位置然后插入当进行查找操作时，如果定位的地址没有值，则不存在，如果定位的位置有值，则依次往后探测，直到遇到要查找的关键码，如果遇到了空地址还没有找到，则不存在--缺点：有效的解决了堆聚问题，但删除操作并不会有所改善--高效的映射：1、有一个合适的哈希函数，比如说质数 value% (一个质数)--当数据量小。

　　ｅ ｎ ｔ ｈ ａ ｓ ｈ ｉ ｎ ｇ — ｂ ａ ｓ ｅ ｄ ｄ ｉ ｓ ｔ ｉ ｒ ｂ ｕ ｔ ｉ ｎ ｇ ｐ ｒ ｏ ｃ ｅ ｓ ｓ （ Ｃ Ｈ — Ｄ Ｐ ） ｌ ａ ｇ ｏ ｉ ｒ ｔ ｈ ｍ．Ｆ ｉ ｒ ｓ ｌ ｔ ｙ ， ｂ ｏ ｔ ｈ ｔ ｈ ｅ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｏ ｒ ｓ ａ ｎ ｄ ｔ ｈ ｅ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｅ ｓ ａ ｒ ｅ ｍａ ｐ ｐ ｅ ｄ ｔ ｏ ｔ ｈ ｅ ｃ ｌ ｏ ｓ ｅ

　　摘要 ： 多 处理 机 系统 中进 程 分 配 策 略 是 影 响 多 处 理机 性 能 的重 要 因素 。本 文设 计 一 种 基 于 一 致 性 哈 希 算 法 的 多 处 理 机 系统进 程 分 配 Ｃ Ｈ— Ｄ Ｐ （ Ｃ ｏ ｎ ｓ ｉ ｓ ｔ ｅ ｎ ｔ Ｈ ａ ｓ ｈ ｉ ｎ ｇ — ｂ ａ ｓ ｅ ｄ Ｄ ｉ ｓ ｔ ｉ ｒ ｂ ｕ ｔ ｉ ｎ ｇ Ｐ ｒ ｏ ｃ ｅ ｓ ｓ ） 策略， 首先将 处理 机和进 程都 映射 到 闭合 地址 空 间