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

andalousie

直接上代码吧。
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 [size];
        }
        ~StringBuffer ()
        {
                delete []_buf;
        }
        bool WillFit (int len) const
        {
                return _curOffset + len + 1 < _bufSize;
        }
        void Add (char const * str)
        {
                strcpy (&_buf [_curOffset], str);
                _curOffset += strlen (str) + 1;
        }
        int GetOffset () const
        {
                return _curOffset;
        }
        bool IsEqual (int offStr, char const * str) const
        {
                char const * strStored = &_buf [offStr];
                return strcmp (str, strStored) == 0;
        }
        char const * GetString (int offStr) const
        {
                return &_buf [offStr];
        }
private:
        int                _bufSize;
        char  * _buf;
        int     _curOffset;
};

class HTable
{
public:
        explicit HTable (int size): _size (size)
        {
                _aList = new List [size];
        }
        ~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 [i];
}

void HTable::insert (char const * str, int id)
{
        int i = hash (str);
        _aList [i].insert (id);
}

int HTable::hash (char const * str) const
{
        // no empty strings, please
        assert (str != 0 && str [0] != 0);
        unsigned h = str [0];
        for (int i = 1; str [i] != 0; ++i)
        {
                h = (h << 4) + str [i];
                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 [size];
}

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 [_curId] = _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 [id];
                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 [id];
        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字符指针里面。就这样吧。今天我们英语配音比赛得了第一名，好开心啊。

网络学习

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