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

## 前言

在前文分布式理论(八)—— Consistent Hash（一致性哈希算法）中，我们讨论了一致性 hash 算法的原理，并说了，我们会自己写一个简单的算法。今天就来写一个。

普通 hash 的结果

先看看普通 hash 怎么做。

首先，需要缓存节点对象，缓存中的存储对象，还有一个缓存节点集合，用于保存有效的缓存节点。

实际存储对象，很简单的一个类，只需要获取他的 hash 值就好：

static class Obj {
  String key;
  Obj(String key) {
    this.key = key;
  }
  @Override
  public int hashCode() {
    return key.hashCode();
  }
  @Override
  public String toString() {
    return "Obj{" +
        "key='" + key + '\'' +
        '}';
  }
}

缓存节点对象，用于存储实际对象：

static class Node {

  Map<Integer, Obj> node = new HashMap<>();
  String name;

  Node(String name) {
    this.name = name;
  }

  public void putObj(Obj obj) {
    node.put(obj.hashCode(), obj);
  }

  Obj getObj(Obj obj) {
    return node.get(obj.hashCode());
  }

  @Override
  public int hashCode() {
    return name.hashCode();
  }
}

也很简单，内部使用了一个 map 保存节点。

缓存节点集合，用于保存有效的缓存节点：

static class NodeArray {

   Node[] nodes = new Node[1024];
   int size = 0;

   public void addNode(Node node) {
     nodes[size++] = node;
   }

   Obj get(Obj obj) {
     int index = obj.hashCode() % size;
     return nodes[index].getObj(obj);
   }

   void put(Obj obj) {
     int index = obj.hashCode() % size;
     nodes[index].putObj(obj);
   }
 }

内部一个数组，取数据时，通过取余机器数量获取缓存节点，再从节点中取出数据。

测试：当增减节点时，还能不能找到原有数据：

/**
  * 验证普通 hash 对于增减节点，原有会不会出现移动。
  */
 public static void main(String[] args) {

   NodeArray nodeArray = new NodeArray();

   Node[] nodes = {
       new Node("Node--> 1"),
       new Node("Node--> 2"),
       new Node("Node--> 3")
   };

   for (Node node : nodes) {
     nodeArray.addNode(node);
   }

   Obj[] objs = {
       new Obj("1"),
       new Obj("2"),
       new Obj("3"),
       new Obj("4"),
       new Obj("5")
   };

   for (Obj obj : objs) {
     nodeArray.put(obj);
   }

   validate(nodeArray, objs);
 }

private static void validate(NodeArray nodeArray, Obj[] objs) {
  for (Obj obj : objs) {
    System.out.println(nodeArray.get(obj));
  }

  nodeArray.addNode(new Node("anything1"));
  nodeArray.addNode(new Node("anything2"));

  System.out.println("========== after  =============");

  for (Obj obj : objs) {
    System.out.println(nodeArray.get(obj));
  }
}

测试步骤如下：

向集合中添加 3 个节点。
向 集群 中添加 5 个对象，这 5 个对象会根据 hash 值散列到不同的节点中。
打印 未增减前 的数据。
打印 增加 2 个节点 后数据，看看还能不能访问到数据。

结果：

一个都访问不到了。这就是普通的取余的缺点，在增减机器的情况下，这种结果无法接收。

再看看一致性 hash 如何解决。

一致性 Hash 的结果

关键的地方来了。

缓存节点对象和实际保存对象不用更改，改的是什么？

改的是保存对象的方式和取出对象的方式，也就是不使用对机器进行取余的算法。

新的 NodeArray 对象如下：

static class NodeArray {

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

void addNode(Node node) {
  nodes.put(node.hashCode(), node);
}

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);

}

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);
}
}