快捷導(dǎo)航

c#哈希算法的實(shí)現(xiàn)方法及思路

更新時(shí)間：2013年12月04日 17:26:25 作者：

這篇文章主要介紹了c#哈希算法的實(shí)現(xiàn)方法及思路，有需要的朋友可以參考一下

有想過(guò)hash["A1"] = DateTime.Now;這句是怎么實(shí)現(xiàn)的嗎？我們來(lái)重溫下學(xué)校時(shí)代就學(xué)過(guò)的哈希算法吧。

我們要寫個(gè)class，實(shí)現(xiàn)如下主程序調(diào)用：

static void Main(string[] args)
        {
            MyHash hash = new MyHash();
            hash["A1"] = DateTime.Now;
            hash["A2"] = 1;
            Console.WriteLine(Convert.ToString(hash["A1"]));
            Console.WriteLine(Convert.ToString(hash["A2"]));
        }

一看，也確實(shí)挺簡(jiǎn)單的，就是一個(gè)所引器，如下：

復(fù)制代碼代碼如下:

class MyHash
    {
        public object this[string key]
        {
            get
            {
            }
            set
            {
            }
        }
    }

程序中要保存的對(duì)象，最終是要保存在一個(gè)數(shù)組中的，而且需要通過(guò)一個(gè)轉(zhuǎn)換函數(shù)來(lái)進(jìn)行string key與數(shù)組Index的Map，如下：

復(fù)制代碼代碼如下:

private List<List<Tuple<string, object>>> lstArray = new List<List<Tuple<string, object>>>(defaultSize);

private int MapString2Int(string key)
        {
            int hashIndex=0;
            char[] keyAry = key.ToCharArray();
            foreach (var c in keyAry)
                hashIndex += (int)c;

            hashIndex = hashIndex % lstArray.Capacity;
            return hashIndex;
        }

這個(gè)函數(shù)是遍歷string key的每個(gè)char，累加，最終取模（同數(shù)組的長(zhǎng)度），這樣得出的一個(gè)value肯定就在數(shù)組范圍內(nèi)。

如果2個(gè)key轉(zhuǎn)換出來(lái)的index相同呢？會(huì)導(dǎo)致沖突，一個(gè)最簡(jiǎn)單的解決辦法是把數(shù)組中的每個(gè)元素變成List, 也就是說(shuō)，如果string key轉(zhuǎn)換后出現(xiàn)了相同的Index，沒(méi)關(guān)系，只要把那2個(gè)元素都放在那個(gè)Index所標(biāo)識(shí)的數(shù)組位置中即可，本文中用的是List<Tuple<string, object>>。

下面是整個(gè)程序的代碼：

復(fù)制代碼代碼如下:

class Program
    {
        static void Main(string[] args)
        {
            MyHash hash = new MyHash();
            hash["A1"] = DateTime.Now;
            hash["A2"] = 1;
            Console.WriteLine(Convert.ToString(hash["A1"]));
            Console.WriteLine(Convert.ToString(hash["A2"]));
        }
    }

    class MyHash
    {
        private const int defaultSize = 99999;
        private List<List<Tuple<string, object>>> lstArray = new List<List<Tuple<string, object>>>(defaultSize);

        public MyHash()
        {
            int i = lstArray.Capacity;
            while(i>=0)
            {
                lstArray.Add(new List<Tuple<string,object>>());
                i--;
            }
        }

        public object this[string key]
        {
            get
            {
                EnsureNotNull(key);

                List<Tuple<string, object>> lst;
                Tuple<string, object> obj = FindByKey(key, out lst);
                if (obj == null)
                    throw new Exception("Key不存在");

                return obj.Item2;
            }
            set
            {
                EnsureNotNull(key);

                List<Tuple<string, object>> lst;
                Tuple<string, object> obj = FindByKey(key, out lst);
                if (obj!=null)
                    lst.Remove(obj);

                lst.Add(new Tuple<string, object>(key, value));
            }
        }

        private Tuple<string, object> FindByKey(string key, out List<Tuple<string, object>> lst)
        {
            int hashIndex = MapString2Int(key);
            lst = lstArray[hashIndex];
            Tuple<string, object> obj = null;
            for (var i = 0; i < lst.Count; i++)
            {
                if (lst[i].Item1 == key)
                {
                    obj = lst[i];
                    break;
                }
            }

return obj;
}

        private static void EnsureNotNull(string key)
        {
            if (key == null || key.Trim().Length == 0)
                throw new Exception("Key不能為空");
        }

        private int MapString2Int(string key)
        {
            int hashIndex=0;
            char[] keyAry = key.ToCharArray();
            foreach (var c in keyAry)
                hashIndex += (int)c;

hashIndex = hashIndex % lstArray.Capacity;

Console.WriteLine(string.Format("{0}相應(yīng)的Index為：{1}", key, hashIndex));

            return hashIndex;
        }
    }

運(yùn)行效果圖：