Hash算法 一致性Hash算法在Memcached中的应用

//保存所有虚拟节点信息, key : 虚拟节点的hash key, value: 虚拟节点对应的真实server
        private Dictionary<uint, string> hostDictionary = new Dictionary<uint, string>();
        //保存所有虚拟节点的hash key, 已按升序排序
        private uint[] ketamaHashKeys = new uint[] { };
        //保存真实server主机地址
        private string[] realHostArr = new string[] { };
        //每台真实server对应虚拟节点个数
        private int VirtualNodeNum = 250;

        public KetamaVirtualNodeInit(string[] hostArr)
        {
            this.realHostArr = hostArr;
            this.InitVirtualNodes();
        }

        /// <summary>
        /// 初始化虚拟节点
        /// </summary>
        private void InitVirtualNodes()
        {
            hostDictionary = new Dictionary<uint, string>();
            List<uint> hostKeys = new List<uint>();
            if (realHostArr == null || realHostArr.Length == 0)
            {
                throw new Exception("不能传入空的Server集合");
            }

            for (int i = 0; i < realHostArr.Length; i++)
            {
                for (int j = 0; j < VirtualNodeNum; j++)
                {
                    byte[] nameBytes = Encoding.UTF8.GetBytes(string.Format("{0}-node{1}", realHostArr[i], j));
                    //调用Ketama hash算法获取hash key
                    uint hashKey = BitConverter.ToUInt32(new KetamaHash().ComputeHash(nameBytes), 0);
                    hostKeys.Add(hashKey);
                    if (hostDictionary.ContainsKey(hashKey))
                    {
                        throw new Exception("创建虚拟节点时发现相同hash key,请检查是否传入了相同Server");
                    }
                    hostDictionary.Add(hashKey, realHostArr[i]);
                }
            }

            hostKeys.Sort();
            ketamaHashKeys = hostKeys.ToArray();
        }

     /// <summary>
        /// 根据hash key 获取对应的真实Server
        /// </summary>
        /// <param name="hash"></param>
        /// <returns></returns>
        public string GetHostByHashKey(string key)
        {
            byte[] bytes = Encoding.UTF8.GetBytes(key);
            uint hash = BitConverter.ToUInt32(new KetamaHash().ComputeHash(bytes), 0);

            //寻找与当前hash值相等的Server. 
            int i = Array.BinarySearch(ketamaHashKeys, hash);

            //如果i小于零则表示没有hash值相等的虚拟节点
            if (i < 0)
            {
                //将i继续按位求补,得到数组中第一个大于当前hash值的虚拟节点
                i = ~i;

                //如果按位求补后的i大于等于数组的大小,则表示数组中没有大于当前hash值的虚拟节点
                //此时直接取第一个server
                if (i >= ketamaHashKeys.Length)
                {
                    i = 0;
                }
            }

            //根据虚拟节点的hash key 返回对应的真实server host地址
            return hostDictionary[ketamaHashKeys[i]];
        }

    /// <summary>
    ///  Ketama hash加密算法
    ///  关于HashAlgorithm参见MSDN链接
    ///  http://msdn.microsoft.com/zh-cn/library/system.security.cryptography.hashalgorithm%28v=vs.110%29.aspx
    /// </summary>
    public class KetamaHash : HashAlgorithm
    {

        private static readonly uint FNV_prime = 16777619;
        private static readonly uint offset_basis = 2166136261;

        protected uint hash;

        public KetamaHash()
        {
            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);
        }
    }