Реализуйте последовательный алгоритм хеширования самостоятельно

задняя часть алгоритм

предисловие

в предыдущемРаспределенная теория (8) — согласованный хэш (алгоритм согласованного хеширования)В разделе мы обсудили принцип согласованного алгоритма хеширования и сказали, что напишем простой алгоритм сами. Напишите сегодня.

Результат обычного хеширования

Давайте посмотрим, как это делают обычные хэши.

Во-первых, вам нужно кэшировать объекты узла, объекты хранения в кеше и коллекцию узлов кеша для хранения действительных узлов кеша.

  1. Фактический объект хранения, очень простой класс, просто должен получить свое хеш-значение:
  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 + '\'' +
          '}';
    }
  }
  1. Объекты узлов кеша, используемые для хранения реальных объектов:
  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();
    }
  }

Это также очень просто, карта используется внутри для сохранения узлов.

  1. Набор узлов кеша для хранения действительных узлов кеша:
 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);
    }
  }

Есть внутренний массив, при выборке данных узел кэша получается путем взятия количества оставшихся машин, а затем данные извлекаются из узла.

  1. Тест: при добавлении или удалении узлов вы все еще можете найти исходные данные:
 /**
   * 验证普通 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));
    }
  }

Шаги теста следующие:

  1. Добавьте 3 узла в коллекцию.
  2. В направлении集群Добавьте 5 объектов к узлу, и эти 5 объектов будут хешированы на разные узлы в соответствии со значением хеш-функции.
  3. Распечатать未增减前Данные.
  4. Распечатать增加 2 个节点После данных см. Если вы все еще можете получить доступ к данным.

результат:

Доступ ни к одному из них невозможен. В этом недостаток обычных остатков, а в случае машин сложения или вычитания такой результат неприемлем.

Давайте посмотрим, как решается непротиворечивый хэш.

Согласованные результаты хеширования

Вот ключевой момент.

Кэшированный объект узла и фактически сохраненный объект изменять не нужно.Что изменилось?

Что изменилось, так это способ сохранения объекта и способ извлечения объекта, то есть алгоритм, который берет остаток от машины, не используется.

Новые объекты 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);
}
}

Этот класс отличается от предыдущего тем, что:

  1. Внутренне массивы не используются, но используются отсортированные карты.
  2. В методе put, если объект не попадает на кеш-узел, он найдет узел меньше его и ближайший к нему. Здесь мы используем метод tailMap из TreeMap, конкретный API можно увидеть в документации.
  3. В методе get он аналогичен шагу put, иначе объект не может быть получен.

Конкретный способ найти узел выглядит следующим образом:

image.png

Тот же тестовый пример, результат выполнения следующий:

image.png

Найдите все узлы раньше. Решить проблему обычного хэша.

Суммировать

Код относительно прост, в основном с помощью TreeMap, поставляемого с JDK, для поиска соседних узлов. Конечно, мы тестировали здесь только дополнение, а модификацию не тестировали, но идея та же. Здесь это просто лозунг.

При этом виртуальную ноду мы не реализовали, и заинтересованные друзья могут попробовать.

удачи! ! ! !

Категории