TreeMap 实现
SortArrayMap 虽说是实现了一致性 hash 的功能，但效率还不够高，主要体现在 sort 排序处。
下图是目前主流排序算法的时间复杂度：
最好的也就是 O(N) 了。
这里完全可以换一个思路，不用对数据进行排序；而是在写入的时候就排好顺序，只是这样会降低写入的效率。
比如二叉查找树，这样的数据结构 jdk 里有现成的实现；比如 TreeMap 就是使用红黑树来实现的，默认情况下它会对 key 进行自然排序。
来看看使用 TreeMap 如何来达到同样的效果。
运行结果：
127.0.0.1000
效果和上文使用 SortArrayMap 是一致的。
只使用了 TreeMap 的一些 API：
- 写入数据候，
TreeMap可以保证 key 的自然排序。
tailMap可以获取比当前 key 大的部分数据。
- 当这个方法有数据返回时取第一个就是顺时针中的第一个节点了。
- 如果没有返回那就直接取整个
Map的第一个节点，同样也实现了环形结构。
ps:这里同样也没有 hash 方法以及虚拟节点（具体实现请看下文），因为 TreeMap 和 SortArrayMap 一样都是作为基础数据结构来使用的。
性能对比
为了方便大家选择哪一个数据结构，我用 TreeMap 和 SortArrayMap 分别写入了一百万条数据来对比。
先是 SortArrayMap：
耗时 2237 毫秒。
TreeMap：
耗时 1316毫秒。
结果是快了将近一倍，所以还是推荐使用 TreeMap 来进行实现，毕竟它不需要额外的排序损耗。
cim 中的实际应用
下面来看看在 cim 这个应用中是如何具体使用的，其中也包括上文提到的虚拟节点以及 hash 算法。
模板方法
在应用的时候考虑到就算是一致性 hash 算法都有多种实现，为了方便其使用者扩展自己的一致性 hash 算法因此我定义了一个抽象类；其中定义了一些模板方法，这样大家只需要在子类中进行不同的实现即可完成自己的算法。
AbstractConsistentHash，这个抽象类的主要方法如下：
add方法自然是写入数据的。
sort方法用于排序，但子类也不一定需要重写，比如TreeMap这样自带排序的容器就不用。
getFirstNodeValue获取节点。
process则是面向客户端的，最终只需要调用这个方法即可返回一个节点。
下面我们来看看利用 SortArrayMap 以及 AbstractConsistentHash 是如何实现的。
就是实现了几个抽象方法，逻辑和上文是一样的，只是抽取到了不同的方法中。
只是在 add 方法中新增了几个虚拟节点，相信大家也看得明白。
把虚拟节点的控制放到子类而没有放到抽象类中也是为了灵活性考虑，可能不同的实现对虚拟节点的数量要求也不一样，所以不如自定义的好。
但是 hash 方法确是放到了抽象类中，子类不用重写；因为这是一个基本功能，只需要有一个公共算法可以保证他散列地足够均匀即可。
因此在 AbstractConsistentHash 中定义了 hash 方法。
这里的算法摘抄自 xxl_job，网上也有其他不同的实现，比如
FNV1_32_HASH等；实现不同但是目的都一样。
这样对于使用者来说就非常简单了：
他只需要构建一个服务列表，然后把当前的客户端信息传入 process 方法中即可获得一个一致性 hash 算法的返回。
同样的对于想通过 TreeMap 来实现也是一样的套路：
他这里不需要重写 sort 方法，因为自身写入时已经排好序了。
而在使用时对于客户端来说只需求修改一个实现类，其他的啥都不用改就可以了。
运行的效果也是一样的。
这样大家想自定义自己的算法时只需要继承 AbstractConsistentHash 重写相关方法即可，客户端代码无须改动。
路由算法扩展性
但其实对于 cim 来说真正的扩展性是对路由算法来说的，比如它需要支持轮询、hash、一致性hash、随机、LRU等。
只是一致性 hash 也有多种实现，他们的关系就如下图：
应用还需要满足对这一类路由策略的灵活支持，比如我也想自定义一个随机的策略。
因此定义了一个接口：RouteHandle
public interface RouteHandle { /** * 再一批服务器里进行路由 * @param values * @param key * @return */ String routeServer(List<String> values,String key) ; }
其中只有一个方法，也就是路由方法；入参分别是服务列表以及客户端信息即可。
而对于一致性 hash 算法来说也是只需要实现这个接口，同时在这个接口中选择使用 SortArrayMapConsistentHash 还是 TreeMapConsistentHash 即可。
这里还有一个 setHash 的方法，入参是 AbstractConsistentHash；这就是用于客户端指定需要使用具体的那种数据结构。
而对于之前就存在的轮询策略来说也是同样的实现 RouteHandle 接口。
这里我只是把之前的代码搬过来了而已。
接下来看看客户端到底是如何使用以及如何选择使用哪种算法。
为了使客户端代码几乎不动，我将这个选择的过程放入了配置文件。
- 如果想使用原有的轮询策略，就配置实现了
RouteHandle接口的轮询策略的全限定名。
- 如果想使用一致性 hash 的策略，也只需要配置实现了
RouteHandle接口的一致性 hash 算法的全限定名。
- 当然目前的一致性 hash 也有多种实现，所以一旦配置为一致性 hash 后就需要再加一个配置用于决定使用
SortArrayMapConsistentHash还是TreeMapConsistentHash或是自定义的其他方案。
- 同样的也是需要配置继承了
AbstractConsistentHash的全限定名。
不管这里的策略如何改变，在使用处依然保持不变。
只需要注入 RouteHandle，调用它的 routeServer 方法。
@Autowired private RouteHandle routeHandle ; String server = routeHandle.routeServer(serverCache.getAll(),String.valueOf(loginReqVO.getUserId()));
既然使用了注入，那其实这个策略切换的过程就在创建 RouteHandle bean 的时候完成的。
也比较简单，需要读取之前的配置文件来动态生成具体的实现类，主要是利用反射完成的。
这样处理之后就比较灵活了，比如想新建一个随机的路由策略也是同样的套路；到时候只需要修改配置即可。
感兴趣的朋友也可提交 PR 来新增更多的路由策略。
总结
希望看到这里的朋友能对这个算法有所理解，同时对一些设计模式在实际的使用也能有所帮助。
以上所有源码：
