「架构师训练营」作业：第 5 周 一致性 hash 算法

class Program
{        
    private static readonly SortedDictionary<ulong, string> _circle = new SortedDictionary<ulong, string>();
    public static string[] services = new string[]
    {
        "192.168.1.1",
        "192.168.1.2",
        "192.168.1.3",
        "192.168.1.4",
        "192.168.1.5",
        "192.168.1.6",
        "192.168.1.7",
        "192.168.1.8",
        "192.168.1.9",
        "192.168.1.10"
    };
    static void Main(string[] args)
    {
        int Replicas = 100;
        foreach(string ip in services)
        {
            AddNode(ip, Replicas);
        }
         List<string> nodes = new List<string>();
         for (int i = 0; i < 1000000; i++)
         {
             nodes.Add(GetTargetNode(i + "test" + (char)i));
         }
         var counts = nodes.GroupBy(n => n, n => n.Count()).ToList();
         counts.ForEach(index => Console.WriteLine(index.Key + " --- " + index.Count()));
         var stdDeviation = CaculateStandardDeviation(counts.Select(i => i.Count()).ToArray());
         Console.WriteLine();
         Console.WriteLine("标准差：{0}",stdDeviation.ToString());
         Console.ReadLine();
     }
     public static void AddNode(string node, int repeat)
     {
         for (int i = 0; i < repeat; i++)
         {
              string identifier = node.GetHashCode().ToString() + "-" + i;
              ulong hashCode = Md5Hash(identifier);
              _circle.Add(hashCode, node);
          }
      }
     public static ulong Md5Hash(string key)
     {
         using (var hash = System.Security.Cryptography.MD5.Create())
         {
             byte[] data = hash.ComputeHash(Encoding.UTF8.GetBytes(key));
             var a = BitConverter.ToUInt64(data, 0);
             var b = BitConverter.ToUInt64(data, 8);
             ulong hashCode = a ^ b;
             return hashCode;
         }
     }
  
     public static string GetTargetNode(string key)
     {
         ulong hash = Md5Hash(key);
         ulong firstNode = ModifiedBinarySearch(_circle.Keys.ToArray(), hash);
         return _circle[firstNode];
     }
     /// <summary>
     /// 计算key的数值，得出空间归属。
     /// </summary>
     /// <param name="sortedArray"></param>
     /// <param name="val"></param>
     /// <returns></returns>
     public static ulong ModifiedBinarySearch(ulong[] sortedArray, ulong val)
     {
         int min = 0;
         int max = sortedArray.Length - 1;
         if (val < sortedArray[min] || val > sortedArray[max])
             return sortedArray[0];
          while (max - min > 1)
          {
              int mid = (max + min) / 2;
              if (sortedArray[mid] >= val)
              {
                  max = mid;
              }
              else
              {
                  min = mid;
              }
          }
          return sortedArray[max];
      }
      public static double CaculateStandardDeviation(int[] arry)
      {
          double stdDeviation = 0;
          int min = arry.Min();
          int max = arry.Max();
          var avg = Math.Round((decimal)arry.Average(p => p), 5);
          if (arry.Length > 1)
          {
              double sumOfSquare = 0;
              foreach(var item in arry)
              {
                  sumOfSquare += Math.Pow((double)item - (double)avg, 2);
              }
              stdDeviation = Math.Sqrt(sumOfSquare / (arry.Length - 1));
              stdDeviation = Math.Round(stdDeviation, 5);
          }
        return stdDeviation;
    }
}