欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c#哈希算法的实现方法及思路

程序员文章站 2024-02-22 19:39:58
有想过hash["a1"] = datetime.now;这句是怎么实现的吗?我们来重温下学校时代就学过的哈希算法吧。 我们要写个class,实现如下主程序调用: 复制...

有想过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;
        }
    }

运行效果图:

c#哈希算法的实现方法及思路