Consistent Hashing C#, 一致性HASH

ConsistentHashing.cs

    /// <summary>
    /// 一致性 Hash 算法
    /// </summary>
    class ConsistentHashing
    {
        List<KeyValuePair<uint, string>> _serList = new List<KeyValuePair<uint, string>>();

        public ConsistentHashing(string[] serList)
        {
            if (serList == null || serList.Length == 0)
                return;

            foreach (var ser in serList)
            {
                _serList.Add(new KeyValuePair<uint, string>(Hash(ser), ser));
            }
            _serList.Sort((x, y) => x.Key > y.Key ? 1 : (x.Key == y.Key ? 0 : -1));
        }
        /// <summary>
        /// Hash 具体的节点
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public KeyValuePair<uint, string> Locate(string key)
        {
            if (string.IsNullOrEmpty(key))
                return _serList[0];

            var hash = Hash(key);
            var index = _serList.BinarySearch(new KeyValuePair<uint, string>(hash, null), new KeyValuePairComparer());
            if (index >= 0)
                return _serList[index];
            else
            {
                var nIndex = ~index;
                if (nIndex >= _serList.Count)
                    return _serList[0];
                else
                    return _serList[nIndex];
            }
        }
        /// <summary>
        /// 得到字符串的HASH
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private static uint Hash(string key)
        {
            return BitConverter.ToUInt32(new ModifiedFNV1_32().ComputeHash(Encoding.UTF8.GetBytes(key)), 0);
        }

        /// <summary>
        /// KeyValuePair 比较器实现
        /// 只比对 Key 部分大小
        /// </summary>
        class KeyValuePairComparer
            : IComparer<KeyValuePair<uint, string>>
        {

            #region IComparer<KeyValuePair<uint,string>> 成员
            public int Compare(KeyValuePair<uint, string> x, KeyValuePair<uint, string> y)
            {
                return x.Key > y.Key ? 1 : (x.Key == y.Key ? 0 : -1);
            }
            #endregion
        }
        
        #region HASH函数相关
        /// <summary>
        /// 修改版FNV1_32 哈希函数
        /// </summary>
        /// <remarks>
        /// FNV1_32 哈希函数
        /// Fowler-Noll-Vo hash, variant 1, 32-bit version.
        /// http://www.isthe.com/chongo/tech/comp/fnv/
        /// 修改版FNV1_32 哈希函数
        /// Modified Fowler-Noll-Vo hash, 32-bit version.
        /// http://home.comcast.net/~bretm/hash/6.html
        /// </remarks>
        class ModifiedFNV1_32 : HashAlgorithm
        {
            private static readonly uint FNV_prime = 16777619;
            private static readonly uint offset_basis = 2166136261;

            protected uint hash;

            public ModifiedFNV1_32()
            {
                HashSizeValue = 32;
            }

            public override void Initialize()
            {
                hash = offset_basis;
            }

            protected override void HashCore(byte[] array, int ibStart, int cbSize)
            {
                int length = ibStart + cbSize;
                for (int i = ibStart; i < length; i++)
                {
                    hash = (hash * FNV_prime) ^ array[i];
                }
            }

            protected override byte[] HashFinal()
            {
                hash += hash << 13;
                hash ^= hash >> 7;
                hash += hash << 3;
                hash ^= hash >> 17;
                hash += hash << 5;
                return BitConverter.GetBytes(hash);
            }
        }
        #endregion
    }

TestProgram.cs

    static class Program
    {
        /// <summary>
        /// 应用程序的主入口点。
        /// </summary>
        [STAThread]
        static void Main()
        {
            ConsistentHashing ch = new ConsistentHashing(new string[]{
                            "192.168.1.192:9001甲",
                            "192.168.1.192:9002乙",
                            "192.168.1.192:9003丙",
                            "192.168.1.192:9004丁",
                            "192.168.1.192:9005子",
                            "192.168.1.192:9006丑",
                            "192.168.1.192:9007吟",
                            "192.168.1.193:9001毛",
                            "192.168.1.193:9002",
                            "192.168.1.193:9003",
                            "192.168.1.193:9004",
                            "192.168.1.193:9005",
                            "192.168.1.193:9006",
                            "192.168.1.193:9007",
                            "192.168.1.194:9001",
                            "192.168.1.194:9002",
                            "192.168.1.194:9003",
                            "192.168.1.194:9004",
                            "192.168.1.194:9005",
                            "192.168.1.194:9006",
                            "192.168.1.194:9007"});

            Console.WriteLine("{0}-{1}", "HelloWorld", ch.Locate("HelloWorld"));
            Console.WriteLine("{0}-{1}", "Hello1", ch.Locate("Hello1"));
            Console.WriteLine("{0}-{1}", "Hello2", ch.Locate("Hello2"));
            Console.WriteLine("{0}-{1}", "Hello3", ch.Locate("Hello3"));
            Console.WriteLine("{0}-{1}", "Hello4", ch.Locate("Hello4"));

            Console.WriteLine("{0}-{1}", "Hello4小白", ch.Locate("Hello4小白"));
            Console.WriteLine("{0}-{1}", "Hello4小强", ch.Locate("Hello4小强"));

            Console.WriteLine("{0}-{1}", "HelloWorld1", ch.Locate("HelloWorld"));
            Console.WriteLine("{0}-{1}", "HelloWorld2", ch.Locate("HelloWorld2"));
            Console.WriteLine("{0}-{1}", "HelloWorld3", ch.Locate("HelloWorld3"));
            Console.WriteLine("{0}-{1}", "HelloWorld4", ch.Locate("HelloWorld4"));
            Console.WriteLine("{0}-{1}", "HelloWorld5", ch.Locate("HelloWorld5"));
            Console.WriteLine("{0}-{1}", "HelloWorld6", ch.Locate("HelloWorld6"));

            Console.WriteLine("{0}-{1}", "中国One", ch.Locate("中国One"));
            Console.WriteLine("{0}-{1}", "美国Two", ch.Locate("美国Two"));
            Console.WriteLine("{0}-{1}", "日本three", ch.Locate("日本three"));
            Console.WriteLine("{0}-{1}", "韩国four", ch.Locate("韩国four"));
            Console.WriteLine("{0}-{1}", "越南five", ch.Locate("越南five"));

            Console.Read();
        }
    }
}