一致性 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 的值标识此位置包含 node
- indexToAddr<Integer, Node> 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; // 置位为 1
- map.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<n){
- front = cur;
- cur = cur.next;
- }
- if(front == null) front = head;
- return front.val.node;
链表的方式每次都会从表头开始遍历一遍才能找到指定位置
链表方式的插入: 直接创建一个节点插入进来就可以了, 保证链表是有序的.
来源: http://www.bubuko.com/infodetail-2931849.html