StringHashTable

#include <iostream>
#include <string>
#include <vector>
using std::string;
using std::vector;

// Начальный размер хеш-таблицы.
const int InitialTableSize = 1001;

// Простая хеш-функция строки. Использует только первый символ.
int StringHash( const string& source, int m )
{
    if( source.empty() ) {
        return 0;
    }
    return source[0] % m;
}

class CHashTable {
public:
    CHashTable();
    ~CHashTable();

    // Проверка наличия ключа в таблице.
    bool Has( const string& key ) const;
    // Добавление ключа в таблицу. Если ключ уже есть, возвращает false.
    bool Add( const string& key );
    // Удаление ключа из таблицы. Если ключа не было, возвращает false.
    bool Remove( const string& key );

private:
    struct CHashTableNode {
        string Data;
        CHashTableNode* Next;

        explicit CHashTableNode( const string& data ) : Data( data ), Next( 0 ) {}
    };
    vector<CHashTableNode*> table;
};

CHashTable::CHashTable()
{
    table.resize( InitialTableSize, 0 );
}

CHashTable::~CHashTable()
{
    // Чистка всех цепочек.
    for( int i = 0; i < static_cast<int>( table.size() ); ++i ) {
        for( CHashTableNode* node = table[i]; node != 0; ) {
            CHashTableNode* nextNode = node->Next;
            delete node;
            node = nextNode;
        }
    }
}

bool CHashTable::Has( const string& key ) const
{
    int hash = StringHash( key, table.size() );
    for( CHashTableNode* node = table[hash]; node != 0; node = node->Next ) {
        if( node->Data == key ) {
            return true;
        }
    }
    return false;
}

bool CHashTable::Add( const string& key )
{
    int hash = StringHash( key, table.size() );
    for( CHashTableNode* node = table[hash]; node != 0; node = node->Next ) {
        if( node->Data == key ) {
            return false;
        }
    }
    // Добавим новый ключ в начало цепочки.
    CHashTableNode* newNode = new CHashTableNode( key );
    newNode->Next = table[hash];
    table[hash] = newNode;
    return true;
}

bool CHashTable::Remove( const string& key )
{
    int hash = StringHash( key, table.size() );
    if( table[hash] == 0 ) {
        // Ключей в цепочке нет.
        return false;
    }
    CHashTableNode* node = table[hash];
    if( node->Data == key ) {
        // Если искомый ключ - первый в списке.
        table[hash] = node->Next;
        delete node;
        return true;
    }

    for( CHashTableNode* nextNode = node->Next; nextNode != 0; node = nextNode, nextNode = nextNode->Next ) {
        if( nextNode->Data == key ) {
            node->Next = nextNode->Next;
            delete nextNode;
            return true;
        }
    }
    return false;
}

int main()
{
    CHashTable stringsTable;

    while( true ) {
        char command = 0;
        string value;
        std::cin >> command >> value;
        if( std::cin.fail() ) {
            break;
        }
        switch( command ) {
        case '?':
            std::cout << ( stringsTable.Has( value ) ? "OK" : "FAIL" ) << std::endl;
            break;
        case '+':
            std::cout << ( stringsTable.Add( value ) ? "OK" : "FAIL" ) << std::endl;
            break;
        case '-':
            std::cout << ( stringsTable.Remove( value ) ? "OK" : "FAIL" ) << std::endl;
            break;
        }
    }
    return 0;
}