C#数据结构与算法学习笔记 基于哈希表实现集合、映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    class HashST1Set<Key> : ISet<Key>
    {
        private HashST1<Key> hashST1;

        public int Count { get { return hashST1.Count; } }

        public bool IsEmpty { get { return hashST1.IsEmpty; } }

        public HashST1Set(int M)
        {
            hashST1 = new HashST1<Key>(M);
        }

        public HashST1Set()
        {
            hashST1 = new HashST1<Key>();
        }

        public void Add(Key key)
        {
            hashST1.Add(key);
        }

        public void Remove(Key key)
        {
            hashST1.Remove(key);
        }

        public bool Contains(Key key)
        {
            return hashST1.Contains(key);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
    class Program
    {
        private static long TestSet(ISet<string> set, List<string> words)
        {
            Stopwatch t = new Stopwatch();
            t.Start();
            foreach (string word in words)
                set.Add(word);
            t.Stop();
            return t.ElapsedMilliseconds;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("双城记");

            List<string> words = TestHelper.ReadFile("测试文件1/双城记.txt");
            Console.WriteLine("词汇量总数：" + words.Count);

            Console.WriteLine();

            Console.WriteLine("（基于红黑树实现）集合");
            RBT1Set<string> rbt1Set = new RBT1Set<string>();
            long t1 = TestSet(rbt1Set, words);
            Console.WriteLine("不同单词的总数：" + rbt1Set.Count);
            Console.WriteLine("运行时间：" + t1 + "ms");

            Console.WriteLine();

            Console.WriteLine("（基于哈希表实现）集合");
            HashST1Set<string> hashST1Set = new HashST1Set<string>();
            long t2 = TestSet(hashST1Set, words);
            Console.WriteLine("不同单词的总数：" + hashST1Set.Count);
            Console.WriteLine("运行时间：" + t2 + "ms");

            Console.WriteLine();

            Console.Read();
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
    class HashST2<Key, Value>
    {
        private LinkedList3<Key, Value>[] hashtable;   //每个位置都指向一条链表，将冲突的元素都存在链表中
        private int M;
        private int N;

        public HashST2(int M)
        {
            this.M = M;
            N = 0;
            hashtable = new LinkedList3<Key, Value>[M];
            for (int i = 0; i < M; i++)
                hashtable[i] = new LinkedList3<Key, Value>();
        }

        public HashST2() : this(97) { }

        public int Count { get { return N; } }

        public bool IsEmpty { get { return N == 0; } }

        //将键转化为数组的索引
        private int Hash(Key key)
        {
            return (key.GetHashCode() & 0x7fffffff) % M;
        }

        public void Add(Key key, Value value)
        {
            LinkedList3<Key, Value> list = hashtable[Hash(key)];
            if (list.Contains(key))
                list.Set(key, value);
            else
            {
                list.Add(key, value);
                N++;
            }
        }

        public void Remove(Key key)
        {
            LinkedList3<Key, Value> list = hashtable[Hash(key)];
            if (list.Contains(key))
            {
                list.Remove(key);
                N--;
            }
        }

        public bool Contains(Key key)
        {
            LinkedList3<Key, Value> list = hashtable[Hash(key)];
            return list.Contains(key);
        }

        public Value Get(Key key)
        {
            LinkedList3<Key, Value> list = hashtable[Hash(key)];
            return list.Get(key);
        }

        public void Set(Key key, Value newValue)
        {
            LinkedList3<Key, Value> list = hashtable[Hash(key)];
            list.Set(key, newValue);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
    class HashST2Dictionary<Key,Value> :IDictionary<Key,Value>
    {
        private HashST2<Key, Value> hashST2;

        public int Count { get { return hashST2.Count; } }

        public bool IsEmpty { get { return hashST2.IsEmpty; } }

        public HashST2Dictionary(int M)
        {
            hashST2 = new HashST2<Key, Value>(M);
        }

        public HashST2Dictionary()
        {
            hashST2 = new HashST2<Key, Value>();
        }

        public void Add(Key key, Value value)
        {
            hashST2.Add(key, value);
        }

        public void Remove(Key key)
        {
            hashST2.Remove(key);
        }

        public bool ContainsKey(Key key)
        {
            return hashST2.Contains(key);
        }

        public Value Get(Key key)
        {
            return hashST2.Get(key);
        }

        public void Set(Key key, Value newValue)
        {
            hashST2.Set(key, newValue);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
    class Program
    {
        private static long TestDictionary(IDictionary<string,int> dic, List<string> words)
        {
            Stopwatch t = new Stopwatch();
            t.Start();
            foreach (var word in words)
            {
                if (!dic.ContainsKey(word))
                    dic.Add(word, 1);
                else
                    dic.Set(word, dic.Get(word) + 1);
            }
            t.Stop();
            return t.ElapsedMilliseconds;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("双城记");

            List<string> words = TestHelper.ReadFile("测试文件1/双城记.txt");
            Console.WriteLine("词汇量总数：" + words.Count);

            Console.WriteLine();

            Console.WriteLine("（基于红黑树实现）字典");
            RBT2Dictionary<string, int> dic1 = new RBT2Dictionary<string, int>();
            long t1 = TestDictionary(dic1, words);
            Console.WriteLine("不同单词的总数：" + dic1.Count);
            Console.WriteLine("city出现的频次："+dic1.Get("city"));
            Console.WriteLine("运行时间：" + t1 + "ms");

            Console.WriteLine();

            Console.WriteLine("（基于哈希表实现）字典");
            //统计只有一万个数据左右，传入997可以保证平均每条链表的长度为10左右，提升性能
            HashST2Dictionary<string, int> dic2 = new HashST2Dictionary<string, int>(997);  
            long t2 = TestDictionary(dic2, words);
            Console.WriteLine("不同单词的总数：" + dic2.Count);
            Console.WriteLine("city出现的频次："+dic2.Get("city"));
            Console.WriteLine("运行时间：" + t2 + "ms");

            Console.WriteLine();

            Console.Read();
        }
    }