所以，总的时间复杂度就是O(N)。其实算法还能更改进一些：给一个位置变量X，如果新的差值比原差值小，X替换为新的位置，否则X不变。这样遍历就减少了一轮，不过经过改进后的算法时间复杂度仍为O(N)。
总而言之，这个解决方案和解决方案一相比，总体来看，似乎更好了一些。
3、解决方案三：二叉查找树
抛开List这种数据结构，另一种数据结构则是使用二叉查找树。对于树不是很清楚的朋友可以简单看一下这篇文章树形结构。
当然我们不能简单地使用二叉查找树，因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等，这里使用红黑树，选用红黑树的原因有两点：
1、红黑树主要的作用是用于存储有序的数据，这其实和第一种解决方案的思路又不谋而合了，但是它的效率非常高
2、JDK里面提供了红黑树的代码实现TreeMap和TreeSet
另外，以TreeMap为例，TreeMap本身提供了一个tailMap(K fromKey)方法，支持从红黑树中查找比fromKey大的值的集合，但并不需要遍历整个数据结构。
使用红黑树，可以使得查找的时间复杂度降低为O(logN)，比上面两种解决方案，效率大大提升。
为了验证这个说法，我做了一次测试，从大量数据中查找第一个大于其中间值的那个数据，比如10000数据就找第一个大于5000的数据（模拟平均的情况）。看一下O(N)时间复杂度和O(logN)时间复杂度运行效率的对比：
50000 100000 500000 1000000 4000000ArrayList 1ms 1ms 4ms 4ms 5ms
LinkedList 4ms 7ms 11ms 13ms 17ms
TreeMap 0ms 0ms 0ms 0ms 0ms
因为再大就内存溢出了，所以只测试到4000000数据。可以看到，数据查找的效率，TreeMap是完胜的，其实再增大数据测试也是一样的，红黑树的数据结构决定了任何一个大于N的最小数据，它都只需要几次至几十次查找就可以查到。
当然，明确一点，有利必有弊，根据我另外一次测试得到的结论是，为了维护红黑树，数据插入效率TreeMap在三种数据结构里面是最差的，且插入要慢上5~10倍。
Hash值重新计算
服务器节点我们肯定用字符串来表示，比如"192.168.1.1"、"192.168.1.2"，根据字符串得到其Hash值，那么另外一个重要的问题就是Hash值要重新计算，这个问题是我在测试String的hashCode()方法的时候发现的，不妨来看一下为什么要重新计算Hash值：
/** * String的hashCode()方法运算结果查看 * @author 五月的仓颉 * */ public class StringHashCodeTest { public static void main(String[] args) { System.out.println("192.168.0.0:111的哈希值：" + "192.168.0.0:1111".hashCode()); System.out.println("192.168.0.1:111的哈希值：" + "192.168.0.1:1111".hashCode()); System.out.println("192.168.0.2:111的哈希值：" + "192.168.0.2:1111".hashCode()); System.out.println("192.168.0.3:111的哈希值：" + "192.168.0.3:1111".hashCode()); System.out.println("192.168.0.4:111的哈希值：" + "192.168.0.4:1111".hashCode()); } }
我们在做集群的时候，集群点的IP以这种连续的形式存在是很正常的。看一下运行结果为：