常用算法帖(C#): 字典

.Net(4.0)为我们提供了如下类型的字典结构：Dictionary, SortedDictionary, Lookup。这些类型都支持范型，它们的工作原理基本一致，都是提供如下功能：接收健返回值。它们之间的不同处为：

SortedDictionar：有序字典，插入字典的元素都按升序进行了排列。

Lookup：一键可以对应多值。

在字典的数据结构中，真实充当键的不是当前对象的值。而是对象的hash值，这个值是通过object.GetHashCode()方法返回的。按照不同的对象应该具有不同的hash值原则,我们完全可以通过重载object.GetHashCode方法来设置我们自己的特殊键，我们来看个小例子吧。（根据测试代码的执行结果，我们也能推测出.NET CLR是通过匹配不同对象的Hash值来确定它们是否相等。）

 class Person : IEquatable<Person>,IComparer<Person>    {        public string firstName, lastName;        public int age;        public Person() { }        public Person(string firstName, string lastName, int age)        {            this.firstName = firstName;            this.lastName = lastName;            this.age = age;        }        public bool Equals(Person other)        {            return other.GetHashCode() == this.GetHashCode();        }        public override int GetHashCode()        {            if (age != null)            {                return age << 5 * 30;            }            else            {                return base.GetHashCode();            }        }        public int Compare(Person x, Person y)        {            if (x.age>y.age)            {                return 1;            }            else if (x.age == y.age)            {                return 0;            }            else            {                return -1;            }        }    }

public static void TestDictionaryKey()        {            Person Jeff = new Person("Jeff", "Xiong", 26);            Person Jeff2 = Jeff;            Console.WriteLine("Jeff's hash code:{0}", Jeff.GetHashCode());            Console.WriteLine("Jeff2's hash code:{0}", Jeff2.GetHashCode());            if (Jeff.Equals(Jeff2))            {                Console.WriteLine("Jeff equal Jeff2");            }            else            {                Console.WriteLine("Jeff not equal Jeff2");            }            Person Bob = new Person("Bob", "Li", 26);            Console.WriteLine("Bob's hash code:{0}", Bob.GetHashCode());            if (Jeff.Equals(Bob))            {                Console.WriteLine("Jeff equal Bob");            }            else            {                Console.WriteLine("Jeff not equal Bob");            }            string A = "Jeff";            string B = "Jeff";            Console.WriteLine("A's hash code:{0}", A.GetHashCode());            Console.WriteLine("B's hash code:{0}", B.GetHashCode());            double AA = 1.23;            double BB = 1.23;            Console.WriteLine("AA's hash code:{0}", AA.GetHashCode());            Console.WriteLine("BB's hash code:{0}", BB.GetHashCode());            /*OUT PUT                Jeff's hash code:109051904                Jeff2's hash code:109051904                Jeff equal Jeff2                Bob's hash code:109051904                Jeff equal Bob                A's hash code:808924690                B's hash code:808924690                AA's hash code:1158867386                BB's hash code:1158867386             */        }

接下来我们来看看几个字典类型的小DEMO吧：

Dictionary

        public static void TestDictionary()        {            Dictionary<string, string> programBook = new Dictionary<string, string>();            programBook.Add("chapter1", "base programming skill");            programBook.Add("chapter2", "the amateurism programming skill");            programBook.Add("chapter3", "the professional programming skill");            programBook.Add("chapter4", "the god programming skill");            Random rand = new Random();            string[] content = programBook.Keys.ToArray<string>();            Console.WriteLine(programBook[content[rand.Next(0, 4)]]);            /*OUT PUT             the professional programming skill             */        }

SortedDictionary

public static void TestSortDictionary()        {            SortedDictionary<string, string> book = new SortedDictionary<string, string>();            book.Add("chapter1", "this is chapter 1");            book.Add("chapter6", "this is chapter 6");            book.Add("chapter3", "this is chapter 3");            book.Add("chapter2", "this is chapter 2");            book.Add("chapter9", "this is chapter 9");            book.Add("chapter4", "this is chapter 4");            book.Add("chapter7", "this is chapter 7");            book.Add("chapter5", "this is chapter 5");            book.Add("chapter8", "this is chapter 8");            foreach (string key in book.Keys)            {                Console.WriteLine(key + ":" + book[key]);            }            /*OUT PUT                chapter1:this is chapter 1                chapter2:this is chapter 2                chapter3:this is chapter 3                chapter4:this is chapter 4                chapter5:this is chapter 5                chapter6:this is chapter 6                chapter7:this is chapter 7                chapter8:this is chapter 8                chapter9:this is chapter 9             */        }

Lookup

 public static void TestLookup()        {            Person[] persons = new Person[]{                new Person{firstName="Li",lastName="Ming",age=21},                new Person{firstName="Li",lastName="XinLiang",age=22},                new Person{firstName="Wang",lastName="Kai",age=23},                new Person{firstName="Li",lastName="SiMing",age=24}    };            var personsContent = persons.ToLookup(person => person.firstName);            ILookup<string, Person> ok = persons.ToLookup<Person, string>(a => a.firstName);            foreach (Person tmp in personsContent["Li"])            {                Console.WriteLine(tmp.firstName + tmp.lastName);            }            Console.WriteLine("*");            foreach (Person tmp in ok["Li"])            {                Console.WriteLine(tmp.firstName + tmp.lastName);            }            /*OUT PUT                LiMing                LiXinLiang                LiSiMing                *                LiMing                LiXinLiang                LiSiMing             */        }