1 #include <iostream>
2
3 template <typename _Type>
4 class HashTable
5 {
6 public:
7 HashTable(int Length)
8 {
9 Element = new _Type[Length];
10 for(int i=0;i<Length;i++)
11 Element[i] = -1;
12 this->Length = Length;
13 Count = 0;
14 }
15
16 ~HashTable()
17 {
18 delete[] Element;
19 }
20
21 // Hash函数
22 virtual int Hash(_Type Data)
23 {
24 return Data % Length;
25 }
26
27 // 再散列法
28 virtual int ReHash(int Index,int Count)
29 {
30 return (Index + Count) % Length;
31 }
32
33 // 查找某个元素是否在表中
34 virtual bool SerachHash(_Type Data,int& Index)
35 {
36 Index = Hash(Data);
37 int Count = 0;
38 while(Element[Index] != -1 && Element[Index] != Data)
39 Index = ReHash(Index,++Count);
40 return Data == Element[Index] ? true : false;
41 }
42
43 virtual int SerachHash(_Type Data)
44 {
45 int Index = 0;
46 if(SerachHash(Data,Index)) return Index;
47 else return -1;
48 }
49
50 // 插入元素
51 bool InsertHash(_Type Data)
52 {
53 int Index = 0;
54 if(Count < Length && !SerachHash(Data,Index))
55 {
56 Element[Index] = Data;
57 Count++;
58 return true;
59 }
60 return false;
61 }
62
63 // 设置Hash表长度
64 void SetLength(int Length)
65 {
66 delete[] Element;
67 Element = new _Type[Length];
68 for(int i=0;i<Length;i++)
69 Element[i] = -1;
70 this->Length = Length;
71 }
72
73 // 删除某个元素
74 void Remove(_Type Data)
75 {
76 int Index = SerachHash(Data);
77 if(Index != -1)
78 {
79 Element[Index] = -1;
80 Count--;
81 }
82 }
83
84 // 删除所有元素
85 void RemoveAll()
86 {
87 for(int i=0;i<Length;i++)
88 Element[i] = -1;
89 Count = 0;
90 }
91
92 void Print()
93 {
94 for(int i=0;i<Length;i++)
95 printf("%d ",Element[i]);
96 printf("\n");
97 }
98 protected:
99 _Type* Element; // Hash表
100 int Length; // Hash表大小
101 int Count; // Hash表当前大小
102 };
103
104 void main()
105 {
106 HashTable<int> H(10);
107 printf("Hash Length(10) Test:\n");
108 int Array[6] = {49,38,65,97,13,49};
109 for(int i=0;i<6;i++)
110 printf("%d\n",H.InsertHash(Array[i]));
111 H.Print();
112 printf("Find(97):%d\n",H.SerachHash(97));
113 printf("Find(49):%d\n",H.SerachHash(49));
114 H.RemoveAll();
115 H.SetLength(30);
116 printf("Hash Length(30) Test:\n");
117 for(int i=0;i<6;i++)
118 printf("%d\n",H.InsertHash(Array[i]));
119 H.Print();
120 printf("Find(97):%d\n",H.SerachHash(97));
121 printf("Find(49):%d\n",H.SerachHash(49));
122 system("pause");
123 }
运行结果:
由上图可知给定的Hash表长度越长越不容易产生冲突,性能也就越高.
posted on 2010-08-10 23:37
lwch 阅读(534)
评论(1) 编辑 收藏 引用 所属分类:
数据结构