背景
看过《为自己搭建一个分布式 IM(即时通讯) 系统》的朋友应该对其中的登录逻辑有所印象。
先给新来的朋友简单介绍下 cim 是干啥的：
其中有一个场景是在客户端登录成功后需要从可用的服务端列表中选择一台服务节点返回给客户端使用。
而这个选择的过程就是一个负载策略的过程；第一版本做的比较简单，默认只支持轮询的方式。
虽然够用，但不够优雅😏。
因此我的规划是内置多种路由策略供使用者根据自己的场景选择，同时提供简单的 API 供用户自定义自己的路由策略。
先来看看一致性 Hash 算法的一些特点：
- 构造一个
0 ~ 2^32-1大小的环。
- 服务节点经过 hash 之后将自身存放到环中的下标中。
- 客户端根据自身的某些数据 hash 之后也定位到这个环中。
- 通过顺时针找到离他最近的一个节点，也就是这次路由的服务节点。
- 考虑到服务节点的个数以及 hash 算法的问题导致环中的数据分布不均匀时引入了虚拟节点。
自定义有序 Map
根据这些客观条件我们很容易想到通过自定义一个有序数组来模拟这个环。
这样我们的流程如下：
- 初始化一个长度为 N 的数组。
- 将服务节点通过 hash 算法得到的正整数，同时将节点自身的数据（hashcode、ip、端口等）存放在这里。
- 完成节点存放后将整个数组进行排序（排序算法有多种）。
- 客户端获取路由节点时，将自身进行 hash 也得到一个正整数；
- 遍历这个数组直到找到一个数据大于等于当前客户端的 hash 值，就将当前节点作为该客户端所路由的节点。
- 如果没有发现比客户端大的数据就返回第一个节点（满足环的特性）。
先不考虑排序所消耗的时间，单看这个路由的时间复杂度：
- 最好是第一次就找到，时间复杂度为
O(1)。
- 最差为遍历完数组后才找到，时间复杂度为
O(N)。
理论讲完了来看看具体实践。
我自定义了一个类：SortArrayMap
他的使用方法及结果如下：
可见最终会按照 key 的大小进行排序，同时传入 hashcode = 101 时会按照顺时针找到 hashcode = 1000 这个节点进行返回。
下面来看看具体的实现。
成员变量和构造函数如下：
其中最核心的就是一个 Node 数组，用它来存放服务节点的 hashcode 以及 value 值。
其中的内部类 Node 结构如下：
写入数据的方法如下：
相信看过 ArrayList 的源码应该有印象，这里的写入逻辑和它很像。
- 写入之前判断是否需要扩容，如果需要则复制原来大小的 1.5 倍数组来存放数据。
- 之后就写入数组，同时数组大小 +1。
但是存放时是按照写入顺序存放的，遍历时自然不会有序；因此提供了一个 Sort 方法，可以把其中的数据按照 key 其实也就是 hashcode 进行排序。
排序也比较简单，使用了 Arrays 这个数组工具进行排序，它其实是使用了一个 TimSort 的排序算法，效率还是比较高的。
最后则需要按照一致性 Hash 的标准顺时针查找对应的节点：
代码还是比较简单清晰的；遍历数组如果找到比当前 key 大的就返回，没有查到就取第一个。
这样就基本实现了一致性 Hash 的要求。
ps:这里并不包含具体的 hash 方法以及虚拟节点等功能（具体实现请看下文），这个可以由使用者来定，SortArrayMap 可作为一个底层的数据结构，提供有序 Map 的能力，使用场景也不局限于一致性 Hash 算法中。
