用c#實(shí)現(xiàn)一致性Hash算法(KetamaHash)

第 2 頁 相應(yīng)的.NET實(shí)現(xiàn)
下面是相應(yīng)的.NET實(shí)現(xiàn)（注釋參考JAVA版本）:   

public class KetamaNodeLocator
{
    //原文中的JAVA類TreeMap實(shí)現(xiàn)了Comparator方法，這里我圖省事，直接用了net下的SortedList，其中Comparer接口方法）
    private SortedList<long, string> ketamaNodes = new SortedList<long, string>();
    private HashAlgorithm hashAlg;
    private int numReps = 160;

    //此處參數(shù)與JAVA版中有區(qū)別，因?yàn)槭褂玫撵o態(tài)方法，所以不再傳遞HashAlgorithm alg參數(shù)
    public KetamaNodeLocator(List<string> nodes, int nodeCopies)
    {
        ketamaNodes = new SortedList<long, string>();

        numReps = nodeCopies;
        //對(duì)所有節(jié)點(diǎn)，生成nCopies個(gè)虛擬結(jié)點(diǎn)
        foreach (string node in nodes)
        {
            //每四個(gè)虛擬結(jié)點(diǎn)為一組
            for (int i = 0; i < numReps / 4; i++)
            {
                //getKeyForNode方法為這組虛擬結(jié)點(diǎn)得到惟一名稱
                byte[] digest = HashAlgorithm.computeMd5(node + i);
                /** Md5是一個(gè)16字節(jié)長度的數(shù)組，將16字節(jié)的數(shù)組每四個(gè)字節(jié)一組，分別對(duì)應(yīng)一個(gè)虛擬結(jié)點(diǎn)，這就是為什么上面把虛擬結(jié)點(diǎn)四個(gè)劃分一組的原因*/ 
                for (int h = 0; h < 4; h++)
                {
                    long m = HashAlgorithm.hash(digest, h);
                    ketamaNodes[m] = node;
                }
            }
        }
    }

    public string GetPrimary(string k)
    {
        byte[] digest = HashAlgorithm.computeMd5(k);
        string rv = GetNodeForKey(HashAlgorithm.hash(digest, 0));
        return rv;
    }

    string GetNodeForKey(long hash)
    {
        string rv;
        long key = hash;
        //如果找到這個(gè)節(jié)點(diǎn)，直接取節(jié)點(diǎn)，返回  
        if (!ketamaNodes.ContainsKey(key))
        {
            //得到大于當(dāng)前key的那個(gè)子Map，然后從中取出第一個(gè)key，就是大于且離它最近的那個(gè)key 說明詳見: http://www.javaeye.com/topic/684087
            var tailMap = from coll in ketamaNodes
                          where coll.Key > hash
                          select new { coll.Key };
            if (tailMap == null || tailMap.Count() == 0)
                key = ketamaNodes.FirstOrDefault().Key;
            else
                key = tailMap.FirstOrDefault().Key;
        }
        rv = ketamaNodes[key];
        return rv;
    }
}
    
   
      下面的代碼與JAVA中有所不同，它使用靜態(tài)方法實(shí)現(xiàn)：   

 
public class HashAlgorithm
{
    public static long hash(byte[] digest, int nTime)
    {
        long rv = ((long)(digest[3 + nTime * 4] & 0xFF) << 24)
                | ((long)(digest[2 + nTime * 4] & 0xFF) << 16)
                | ((long)(digest[1 + nTime * 4] & 0xFF) << 8)
                | ((long)digest[0 + nTime * 4] & 0xFF);

        return rv & 0xffffffffL; /* Truncate to 32-bits */
    }

    /**
     * Get the md5 of the given key.
     */
    public static byte[] computeMd5(string k)
    {
        MD5 md5 = new MD5CryptoServiceProvider();
      
        byte[] keyBytes = md5.ComputeHash(Encoding.UTF8.GetBytes(k));
        md5.Clear();
        //md5.update(keyBytes);
        //return md5.digest();
        return keyBytes;
    }
}