一个SymbolTable类(哈希表的应用)
直接上代码吧。main.cpp
#include "List.h"
#include <iostream>
#include <cstring>
#include <cassert>
class StringBuffer
{
public:
explicit StringBuffer (int size)
: _curOffset (0), _bufSize (size)
{
_buf = new char ;
}
~StringBuffer ()
{
delete []_buf;
}
bool WillFit (int len) const
{
return _curOffset + len + 1 < _bufSize;
}
void Add (char const * str)
{
strcpy (&_buf , str);
_curOffset += strlen (str) + 1;
}
int GetOffset () const
{
return _curOffset;
}
bool IsEqual (int offStr, char const * str) const
{
char const * strStored = &_buf ;
return strcmp (str, strStored) == 0;
}
char const * GetString (int offStr) const
{
return &_buf ;
}
private:
int _bufSize;
char* _buf;
int _curOffset;
};
class HTable
{
public:
explicit HTable (int size): _size (size)
{
_aList = new List ;
}
~HTable ()
{
delete []_aList;
}
// return a short list of candidates
List & find (char const * str) const;
// add another string->id mapping
void insert (char const * str, int id);
private:
// the hashing function
int hash (char const * str) const;
List* _aList; // an array of (short) lists
int _size;
};
// Find the list in the hash table that may contain
// the id of the string we are looking for
List & HTable::find (char const * str) const
{
int i = hash (str);
return _aList ;
}
void HTable::insert (char const * str, int id)
{
int i = hash (str);
_aList .insert (id);
}
int HTable::hash (char const * str) const
{
// no empty strings, please
assert (str != 0 && str != 0);
unsigned h = str ;
for (int i = 1; str != 0; ++i)
{
h = (h << 4) + str ;
unsigned long g = h & 0xf0000000L;
if (g) h ^= g >> 24;
h &= -g;
}
return h % _size; // remainder
}
const int idNotFound = -1;
// String table maps strings to ints
// and ints to strings
class SymbolTable
{
public:
explicit SymbolTable (int size);
~SymbolTable ();
int ForceAdd (char const * str, int len);
int Find (char const * str) const;
char const * GetString (int id) const;
private:
HTable _htab; // string -> ids
int _maxId;
int * _offStr; // id -> offset
int _curId;
StringBuffer _strBuf; // offset -> string
};
SymbolTable::SymbolTable (int size)
: _curId (0),
_maxId (size),
_htab (size + 1),
_strBuf (size * 10)
{
_offStr = new int ;
}
SymbolTable::~SymbolTable ()
{
delete []_offStr;
}
int SymbolTable::ForceAdd (char const * str, int len)
{
// is there enough space?
if (_curId == _maxId || !_strBuf.WillFit (len))
{
return idNotFound;
}
// point to the place where the string will be stored
_offStr = _strBuf.GetOffset ();
_strBuf.Add (str);
// add mapping to hash table
_htab.insert (str, _curId);
++_curId;
return _curId - 1;
}
int SymbolTable::Find (char const * str) const
{
// Get a short list from hash table
List & list = _htab.find (str);
// Iterate over this list
for (List::iterator it = list.begin();
it != list.end();
++it)
{
int id = *it;
int offStr = _offStr ;
if (_strBuf.IsEqual (offStr, str))
return id;
}
return idNotFound;
}
// map integer into string. Must be valid id
char const * SymbolTable::GetString (int id) const
{
assert (id >= 0);
assert (id < _curId);
int offStr = _offStr ;
return _strBuf.GetString (offStr);
}
int main()
{
SymbolTable strTable(100);
strTable.ForceAdd ("One", 3);
strTable.ForceAdd ("Two", 3);
strTable.ForceAdd ("Three", 5);
int id = strTable.Find ("One");
std::cout << "One at " << id << std::endl;
id = strTable.Find ("Two");
std::cout << "Two at " << id << std::endl;
id = strTable.Find ("Three");
std::cout << "Three at " << id << std::endl;
id = strTable.Find ("Minus one");
std::cout << "Minus one at " << id << std::endl;
std::cout << "String 0 is "
<< strTable.GetString (0) << std::endl;
std::cout << "String 1 is "
<< strTable.GetString (1) << std::endl;
std::cout << "String 2 is "
<< strTable.GetString (2) << std::endl;
return 0;
}List.h可以参考http://bbs.fishc.com/thread-44344-1-1.html
整体来说，大家可以看出，这个SymbolTable很好的处理了Hash值的collision，那就是使用多个短链表存储同一位置的字符~
三个类放在一起，也许会看起来比较乱。但是，其实它们是相关的。数据真正存储的地方其实是StringBuffer的_buf字符指针里面。就这样吧。今天我们英语配音比赛得了第一名，好开心啊。
谢谢分享资源祝你马上有财
页:
[1]