一个SymbolTable类(哈希表的应用)

andalousie

直接上代码吧。
main.cpp

1. #include "List.h"
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <cassert>
   
5. 
   
6. class StringBuffer
   
7. {
   
8. public:
   
9.         explicit StringBuffer (int size)
   
10.                 : _curOffset (0), _bufSize (size)
    
11.         {
    
12.                 _buf = new char [size];
    
13.         }
    
14.         ~StringBuffer ()
    
15.         {
    
16.                 delete []_buf;
    
17.         }
    
18.         bool WillFit (int len) const
    
19.         {
    
20.                 return _curOffset + len + 1 < _bufSize;
    
21.         }
    
22.         void Add (char const * str)
    
23.         {
    
24.                 strcpy (&_buf [_curOffset], str);
    
25.                 _curOffset += strlen (str) + 1;
    
26.         }
    
27.         int GetOffset () const
    
28.         {
    
29.                 return _curOffset;
    
30.         }
    
31.         bool IsEqual (int offStr, char const * str) const
    
32.         {
    
33.                 char const * strStored = &_buf [offStr];
    
34.                 return strcmp (str, strStored) == 0;
    
35.         }
    
36.         char const * GetString (int offStr) const
    
37.         {
    
38.                 return &_buf [offStr];
    
39.         }
    
40. private:
    
41.         int                _bufSize;
    
42.         char  * _buf;
    
43.         int     _curOffset;
    
44. };
    
45. 
    
46. class HTable
    
47. {
    
48. public:
    
49.         explicit HTable (int size): _size (size)
    
50.         {
    
51.                 _aList = new List [size];
    
52.         }
    
53.         ~HTable ()
    
54.         {
    
55.                 delete []_aList;
    
56.         }
    
57.         // return a short list of candidates
    
58.         List & find (char const * str) const;
    
59.         // add another string->id mapping
    
60.         void insert (char const * str, int id);
    
61. private:
    
62.         // the hashing function
    
63.         int hash (char const * str) const;
    
64. 
    
65.         List  * _aList; // an array of (short) lists
    
66.         int         _size;
    
67. };
    
68. 
    
69. // Find the list in the hash table that may contain
    
70. // the id of the string we are looking for
    
71. 
    
72. List & HTable::find (char const * str) const
    
73. {
    
74.         int i = hash (str);
    
75.         return _aList [i];
    
76. }
    
77. 
    
78. void HTable::insert (char const * str, int id)
    
79. {
    
80.         int i = hash (str);
    
81.         _aList [i].insert (id);
    
82. }
    
83. 
    
84. int HTable::hash (char const * str) const
    
85. {
    
86.         // no empty strings, please
    
87.         assert (str != 0 && str [0] != 0);
    
88.         unsigned h = str [0];
    
89.         for (int i = 1; str [i] != 0; ++i)
    
90.         {
    
91.                 h = (h << 4) + str [i];
    
92.                 unsigned long g = h & 0xf0000000L;
    
93.                 if (g) h ^= g >> 24;
    
94.                 h &= -g;
    
95.         }
    
96.         return h % _size; // remainder
    
97. }
    
98. 
    
99. const int idNotFound = -1;
    
100. 
     
101. // String table maps strings to ints
     
102. // and ints to strings
     
103. 
     
104. class SymbolTable
     
105. {
     
106. public:
     
107.         explicit SymbolTable (int size);
     
108.         ~SymbolTable ();
     
109.         int ForceAdd (char const * str, int len);
     
110.         int Find (char const * str) const;
     
111.         char const * GetString (int id) const;
     
112. private:
     
113.         HTable                        _htab;         // string -> ids
     
114.         int                                _maxId;
     
115.         int                          * _offStr; // id -> offset
     
116.         int                                _curId;
     
117.         StringBuffer        _strBuf; // offset -> string
     
118. };
     
119. 
     
120. SymbolTable::SymbolTable (int size)
     
121.         : _curId (0),
     
122.           _maxId (size),
     
123.           _htab (size + 1),
     
124.           _strBuf (size * 10)
     
125. {
     
126.         _offStr = new int [size];
     
127. }
     
128. 
     
129. SymbolTable::~SymbolTable ()
     
130. {
     
131.         delete []_offStr;
     
132. }
     
133. 
     
134. int SymbolTable::ForceAdd (char const * str, int len)
     
135. {
     
136.         // is there enough space?
     
137.         if (_curId == _maxId || !_strBuf.WillFit (len))
     
138.         {
     
139.                 return idNotFound;
     
140.         }
     
141.         // point to the place where the string will be stored
     
142.         _offStr [_curId] = _strBuf.GetOffset ();
     
143.         _strBuf.Add (str);
     
144.         // add mapping to hash table
     
145.         _htab.insert (str, _curId);
     
146.         ++_curId;
     
147.         return _curId - 1;
     
148. }
     
149. 
     
150. int SymbolTable::Find (char const * str) const
     
151. {
     
152.         // Get a short list from hash table
     
153.         List & list = _htab.find (str);
     
154.         // Iterate over this list
     
155.         for (List::iterator it = list.begin();
     
156.                  it != list.end();
     
157.                  ++it)
     
158.         {
     
159.                 int id = *it;
     
160.                 int offStr = _offStr [id];
     
161.                 if (_strBuf.IsEqual (offStr, str))
     
162.                 return id;
     
163.         }
     
164.         return idNotFound;
     
165. }
     
166. 
     
167. // map integer into string. Must be valid id
     
168. 
     
169. char const * SymbolTable::GetString (int id) const
     
170. {
     
171.         assert (id >= 0);
     
172.         assert (id < _curId);
     
173.         int offStr = _offStr [id];
     
174.         return _strBuf.GetString (offStr);
     
175. }
     
176. 
     
177. int main()
     
178. {
     
179.         SymbolTable strTable(100);
     
180.         strTable.ForceAdd ("One", 3);
     
181.         strTable.ForceAdd ("Two", 3);
     
182.         strTable.ForceAdd ("Three", 5);
     
183. 
     
184.         int id = strTable.Find ("One");
     
185.         std::cout << "One at " << id << std::endl;
     
186.         id = strTable.Find ("Two");
     
187.         std::cout << "Two at " << id << std::endl;
     
188.         id = strTable.Find ("Three");
     
189.         std::cout << "Three at " << id << std::endl;
     
190.         id = strTable.Find ("Minus one");
     
191.         std::cout << "Minus one at " << id << std::endl;
     
192. 
     
193.         std::cout << "String 0 is "
     
194.                         << strTable.GetString (0) << std::endl;
     
195.         std::cout << "String 1 is "
     
196.                         << strTable.GetString (1) << std::endl;
     
197.         std::cout << "String 2 is "
     
198.                         << strTable.GetString (2) << std::endl;
     
199.         return 0;
     
200. }

复制代码

List.h可以参考http://bbs.fishc.com/thread-44344-1-1.html
整体来说，大家可以看出，这个SymbolTable很好的处理了Hash值的collision，那就是使用多个短链表存储同一位置的字符~
三个类放在一起，也许会看起来比较乱。但是，其实它们是相关的。数据真正存储的地方其实是StringBuffer的_buf字符指针里面。就这样吧。今天我们英语配音比赛得了第一名，好开心啊。

网络学习

谢谢分享资源  祝你马上有财