一致性Hash算法原理参考此博客，介绍的比较详细：https://www.cnblogs.com/lpfuture/p/5796398.html

预设场景：所有请求过来，会根据一致性hash算法，选择一个服务器转发出去，一致性hash算法获取到的是服务器的ip。

假定节点存储结构如下：

class Node{    String addr; //存放服务器的ip}

实现方案一（bitmap+HashMap）

借助数据结构

1. 2^32长度的bitmap，用于标记有节点的下表

2. HashMap，用于存储下标到对象的映射

数据查找伪码实现如下：

bitmap = [0,0,0,1,0,0,1,...0]; //2^32的bitmap，每个为1的值标识此位置包含nodeindexToAddr
     
       map; //存储bitmap中获取的位置下标到Node的映射n=hash(x); //x假设为请求中获取到的用户id，通过hash算法可以得到一个0-2^32-1之间的整数//开始计算while(bitmap[n] != 1){    n = (n+1)%2^32;}//n即为node在环中占的位置，从hash中取出此值Node node = map.get(n);return node.addr;
     

节点插入伪码实现如下：

Node toBeInsert = new Node(x); //插入值为x的节点int n = hash(x);bitmap[n] = 1; //置位为1map.put(n, toBeInsert);

 

这种方式完全是按照原理中介绍的来实现的，需要用到一个2^32的bitmap，如果不进行压缩，需要占用512M的空间。占用空间较大，但是能直接定位到值。

实现方案二（链表）

借助数据结构：链表

class LinkNode{     //定义链表数据结构    LinkNode next;    int index; //下标    Node value;}LinkNode head = []->[]->...->[]->head; //按照index排序的链表int n=hash(x);LinkNode front = null;LinkNode cur=head;while(cur.index

链表的方式每次都会从表头开始遍历一遍才能找到指定位置

链表方式的插入：直接创建一个节点插入进来就可以了，保证链表是有序的。