1 using System;
  2 using System.Collections.Generic;
  3 using System.Data.HashFunction;
  4 using System.Data.HashFunction.xxHash;
  5 using System.Linq;
  6 
  7 namespace HashTest
  8 {
  9     public class ConsistentHash1
 10     {
 11         /// <summary>
 12         /// 虚拟节点数
 13         /// </summary>
 14         private static readonly int VirturalNodeNum = 1000;
 15 
 16         /// <summary> 
 17         /// 服务器IP
 18         /// </summary>
 19         private static readonly string[] Nodes =
 20         {
 21             "192.168.1.0",
 22             "192.168.1.1",
 23             "192.168.1.2",
 24             "192.168.1.3",
 25             "192.168.1.4",
 26             "192.168.1.5",
 27             "192.168.1.6",
 28             "192.168.1.7",
 29             "192.168.1.8",
 30             "192.168.1.9"
 31         };
 32 
 33         /// <summary>
 34         /// 按照一致性Hash进行分组
 35         /// </summary>
 36         private static readonly IDictionary<uint, string> ConsistentHashNodes = new SortedDictionary<uint, string>();
 37 
 38         private static uint[] _nodeKeys = null;
 39         static void Main(string[] args)
 40         {
 41             ComputeNode();
 42             Print();
 43             Console.ReadLine();
 44         }
 45 
 46         private static void Print()
 47         {
 48             IDictionary<string, int> result = new SortedDictionary<string, int>();
 49             for (int i = 0; i < 50000; i++)
 50             {
 51                 var node = Get("ConsistentHashTest" + i);
 52                 if (result.TryGetValue(node, out var count))
 53                 {
 54                     result[node] = count + 1;
 55                 }
 56                 else
 57                 {
 58                     result[node] = 1;
 59                 }
 60                 if (i > 1200 && i < 1220)
 61                 {
 62                     Console.WriteLine($"ConsistentHashTest{i}:{node}");
 63                 }
 64             }
 65 
 66             foreach (var node in result)
 67             {
 68                 Console.WriteLine($"{node.Key}:{node.Value}");
 69             }
 70         }
 71 
 72         private static void ComputeNode()
 73         {
 74             foreach (var node in Nodes)
 75             {
 76                 AddNode(node);
 77             }
 78 
 79             _nodeKeys = ConsistentHashNodes.Keys.ToArray();
 80         }
 81 
 82         private static void AddNode(string node)
 83         {
 84             for (int i = 0; i < VirturalNodeNum; i++)
 85             {
 86                 var key = node + ":" + i;
 87                 var hashValue = ComputeHash(key);
 88                 if (!ConsistentHashNodes.ContainsKey(hashValue))
 89                 {
 90                     ConsistentHashNodes.Add(hashValue, node);
 91                 }
 92             }
 93         }
 94 
 95         private static uint ComputeHash(string virturalNode)
 96         {
 97             var hashFunction = xxHashFactory.Instance.Create();
 98             var hashValue = hashFunction.ComputeHash(virturalNode);
 99             return BitConverter.ToUInt32(hashValue.Hash, 0);
100         }
101 
102         private static string Get(string item)
103         {
104             var hashValue = ComputeHash(item);
105             var index = GetClockwiseNearestNode(hashValue);
106             return ConsistentHashNodes[_nodeKeys[index]];
107         }
108 
109         private static int GetClockwiseNearestNode(uint hash)
110         {
111             int begin = 0;
112             int end = _nodeKeys.Length - 1;
113 
114             if (_nodeKeys[end] < hash || _nodeKeys[0] > hash)
115             {
116                 return 0;
117             }
118 
119             while ((end - begin) > 1)
120             {
121                 var mid = (end + begin) / 2;
122                 if (_nodeKeys[mid] >= hash) end = mid;
123                 else begin = mid;
124             }
125 
126             return end;
127         }
128     }
129 }