VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > c#编程 >
  • C#教程之c#哈希算法的实现方法及思路

有想过hash["A1"] = DateTime.Now;这句是怎么实现的吗?我们来重温下学校时代就学过的哈希算法吧。

我们要写个class,实现如下主程序调用:

 

复制代码 代码如下:

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
    {
        public object this[string key]
        {
            get
            {
            }
            set
            {
            }
        }
    }

 

程序中要保存的对象,最终是要保存在一个数组中的,而且需要通过一个转换函数来进行string key与数组Index的Map,如下:

 

复制代码 代码如下:

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;
        }

 

这个函数是遍历string key的每个char,累加,最终取模(同数组的长度),这样得出的一个value肯定就在数组范围内。

如果2个key转换出来的index相同呢?会导致冲突,一个最简单的解决办法是把数组中的每个元素变成List, 也就是说,如果string key转换后出现了相同的Index,没关系,只要把那2个元素都放在那个Index所标识的数组位置中即可,本文中用的是List<Tuple<string, object>>。

下面是整个程序的代码:

 

复制代码 代码如下:

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}相应的Index为:{1}", key, hashIndex));

            return hashIndex;
        }
    }

 

运行效果图:


相关教程