文章目录

一致性hash算法介绍图片教学原本数据结构图新增节点情况删除情况 实现一致性hash算法分析代码github 参考博客

一致性hash算法介绍

负载均衡算法：一般使用储存的数据%机器台数，但是一旦新增机器或者减少机器，就会影响所有原本导向的节点。 比如：目前储存数据：6，有4台机器，它会是6%4=2，会保存在2号机器。但是一旦新增一台机器，6%5=1， 变成储存在一号机器。原本所有的数据都不见了，这是个很大的问题。 一致性hash算法：就是即使机器经常变动，对原本数据的影响以及搬迁不大。使用就近节点储存数据的原则， 怎么理解呢？它是一个闭环的结构，当你数据落在节点则保存在节点上。如果数据不落在节点上，则按统一的一个方向， 就近储存数据。

图片教学

原本数据结构图

原本hash闭环图，Data数据就近赋值，比如:Data1，其实是不落在节点上的，就近原则落在Node1上。

新增节点情况

新增但无影响其他数据的情况

新增Node4节点，看到对原本数据是没有影响的。

新增有影响的情况

为了方便演示，把节点和数据移动了一下！ 可以看到，新增Node4节点，但是原本的Data1就近原则落在Node4节点上。（原本Data1已经不存在了， 按照一致性hash算法的话,它会在Node4去查这个Data1的数据，为空。这个时候重新put进去到Node4）

删除情况

这个删除情况当然是会影响原本数据的，用胸肌想一下就知道了。

实现一致性hash算法

这个是参考下面博客滴~

分析代码

变量

/** 按照 键 排序*/ TreeMap<Integer, Node> nodes = new TreeMap<>();

使用TreeMap来获取最近的节点

put方法

void put(Obj obj) { int objHashcode = obj.hashCode(); Node node = nodes.get(objHashcode); if (node != null) { node.putObj(obj); return; } // 找到比给定 key 大的集合 SortedMap<Integer, Node> tailMap = nodes.tailMap(objHashcode); // 找到最小的节点 int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey(); nodes.get(nodeHashcode).putObj(obj); }

根据nodes.tailMap方法找到比这个数据大的节点，如果有则说明数据落在最大节点Map里面的最小的节点上。 如果没有比它大的节点map，由于是闭环！！！把数据赋值给第一个最小节点。

get方法

Obj get(Obj obj) { Node node = nodes.get(obj.hashCode()); if (node != null) { return node.getObj(obj); } // 找到比给定 key 大的集合 SortedMap<Integer, Node> tailMap = nodes.tailMap(obj.hashCode()); // 找到最小的节点 int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey(); return nodes.get(nodeHashcode).getObj(obj); }

如果落在节点上。直接获取节点上的数据。如果不在节点上，就近找到节点获取数据。

github

一致性hash实现.

参考博客

自己实现一个一致性-Hash-算法.