Week 05- 作业一：一致性 hash 算法

 public class ConsistentDemo
    {
        private HashSet<string> _server = new HashSet<string>()
        {
            "server-0",
            "server-1","server-2","server-3","server-4",
            "server-5","server-6","server-7","server-8",
            "server-9"
        };
        /// <summary>
        /// 虚拟多少倍
        /// </summary>
        const int Multiples = 200;
        /// <summary>
        /// 测试样本数据量
        /// </summary>
        private const int TestItemCount = 400000;//1_000_000;
        private const int FNV32_prime = 16777619;//0x01000193;
        private const long FNV32_basis = 2166136261;//0x811C9DC5;
        //一个哈希值对应N的VALUE.        
        private Dictionary<long, string> _vServers = new Dictionary<long, string>();
        private long GetServerHash(string serverName)
        {
            long hash = FNV32_basis;
            for (int i = 0; i < serverName.Length; i++)
            {
                hash = (hash ^ serverName[i]) * FNV32_prime;
            }
            hash += hash << 40;
            hash ^= hash >> 8;
            hash += hash << 7;
            hash ^= hash >> 5;
            hash ^= hash >> 4;
            hash += hash << 1;
            return hash;
        }
        public ConsistentDemo()
        {
            foreach (var item in _server)
            {
                AddServer(item);
            }
        }
        /// <summary>
        /// 新增服务器
        /// </summary>
        /// <param name="name"></param>
        public void AddServer(string name)
        {
            for (int index = 0; index < Multiples; index++)
            {
                long hash = GetServerHash($"{name}:Virtual Server{index}");
                _vServers.TryAdd(hash, name);
            }
        }
        /// <summary>
        /// 移除服务器
        /// </summary>
        /// <param name="name"></param>
        public void RemoveServer(string name)
        {
            for (int index = 0; index < Multiples; index++)
            {
                long hash = GetServerHash($"{name}:Virtual Server{index}");
                _vServers.Remove(hash);
            }
        }
        /// <summary>
        /// 获取Key-value 对应服务服务器
        /// </summary>
        /// <param name="theValue"></param>
        /// <returns></returns>
        public string GetServer(string theValue)
        {
            if (_server.Count == 0)
            {
                return string.Empty;
            }
            long hash = GetServerHash(theValue);
            var target = _vServers.Keys.OrderBy(item => item).FirstOrDefault(item => item >= hash);
            if (_vServers.ContainsKey(target))
            {
                return _vServers[target];
            }
            else
            {
                return _vServers.FirstOrDefault().Value;
            }
        }
        public void Print()
        {
            Dictionary<string, int> data = new Dictionary<string, int>();
            for (int i = 0; i < TestItemCount; i++)
            {
                string svrName = GetServer($"我是{i}号数据");
                if (data.ContainsKey(svrName))
                {
                    data[svrName] += 1;
                }
                else
                {
                    data[svrName] = 1;
                }
            }
            Console.WriteLine($"数据量：{TestItemCount},数据被分布在:{data.Count}台服务器上   虚拟倍数{Multiples}   总虚拟服务器个数为:{_vServers.Count}");
            foreach (var item in data)
            {
                Console.WriteLine($"我是<{item.Key}>   我承载了{((float)item.Value / (float)TestItemCount) * 100}%数据");
            }
            Console.WriteLine($"标准差为:{CalculateStdDev(data.Values.ToArray())}");
        }
        private double CalculateStdDev(IEnumerable<int> values)
        {
            double ret = 0;
            if (values.Count() > 0)
            {
                //  计算平均数   
                double avg = values.Average();
                //  计算各数值与平均数的差值的平方，然后求和 
                double sum = values.Sum(d => Math.Pow(d - avg, 2));
                //  除以数量，然后开方
                ret = Math.Sqrt(sum / values.Count());
            }
            return ret;
        }
    }

static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            var xx = new ConsistentDemo();
            sw.Restart();
            Console.WriteLine("初始化服务器");
            xx.Print();
            Console.WriteLine($"总耗时:{sw.ElapsedMilliseconds}ms");
            Console.WriteLine("");
            sw.Restart();
            Console.WriteLine("新增一个临时的");
            xx.AddServer("临时服务器1");
            xx.Print();
            Console.WriteLine($"总耗时:{sw.ElapsedMilliseconds}ms");
            Console.WriteLine("");
            sw.Restart();
            Console.WriteLine("删除一个");
            xx.RemoveServer("server-1");
            xx.Print();
            Console.WriteLine($"总耗时:{sw.ElapsedMilliseconds}ms");
            Console.ReadLine();
        }