半小時在白闆上寫代碼實作一緻性哈希Hash算法

說明

半小時白闆代碼實作一緻性哈希Hash算法，這是Intel一次面試題。面試官丢下這個問題和白闆，面試官就工作去了。

講師：李智慧

什麼是一緻性哈希Hash

一緻性哈希是解決分布式緩存中，當擴容的時候，資料不一緻的問題。

一緻性哈希如何實作？

1. 首先建立一個2的32次方環，0~2的32次方-1，首尾相連，建構一個一緻性哈希環；
2. 把伺服器若幹個虛拟節點的哈希值，放到這個環上；
3. 要計算的哈希值的Key值，也放到環上；
4. 從這個Key值，順時針查找，離它最近的虛拟節點的伺服器。

Java實作

package hash;

import java.util.SortedMap;
import java.util.TreeMap;

class Node {
  String ipAddress;

  public Node(String ipAddress) {
    this.ipAddress = ipAddress;
  }
}

public class ConsistentHashElegent {

  private SortedMap<Integer, Node> hashCircle = new TreeMap<>();

  public ConsistentHashElegent(Node[] nodes, int virtualNums) {
    // init consistent hash
    for (Node node: nodes) {
      for (int i = 0; i < virtualNums; i++) {
        hashCircle.put(getHash(node.toString() + i), node);
      }
    }
  }

  // get consistent node
  public Node getConsistentNode(String key) {
    int hash = getHash(key);
    // validate whether hash is equal to the virtual node hash
    if (hashCircle.containsKey(hash)) {
      // the right tree of key hash
      SortedMap<Integer, Node> tailMap = hashCircle.tailMap(hash);
      hash = tailMap.isEmpty()? hashCircle.firstKey() : tailMap.firstKey();
    }

    return hashCircle.get(hash);
  }


  /**
   * gain hash code from string
   * @param str input
   * @return
   */
  public int getHash(String str) {
    final int p = 16777619;
    int hash = (int) 2166136261L;
    for (int i = 0; i < str.length(); i++)
      hash = (hash ^ str.charAt(i)) * p;
    hash += hash << 13;
    hash ^= hash >> 7;
    hash += hash << 3;
    hash ^= hash >> 17;
    hash += hash << 5;
    return hash;
  }

}


           

更多請參考：

極客大學架構師訓練營 系統架構 分布式緩存 一緻性哈希 Hash 第9課 聽課總結

參考

https://blog.csdn.net/zgpeace/article/details/107092057