SimpleStringHashTable

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

// Размер хеш-таблицы.
const int HashTableSize = 1001;

// Простая хеш-функция, использующая только первый символ строки для вычисления хеша.
// Возвращает значения в диапазоне [0, range - 1].
int SimpleStringHash( const string& key, int range )
{
    if( key.empty() ) {
        return 0;
    }
    return key[0] % range;
}

// Хеш-таблица, реализованная методом цепочек.
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 Key;
        CHashTableNode* Next;

        explicit CHashTableNode( const string& key ) : Key( key ), Next( nullptr ) {}
    };
    // Собственно таблица.
    std::vector<CHashTableNode*> table;
};

CHashTable::CHashTable() :
    table( HashTableSize, nullptr )
{
}

CHashTable::~CHashTable()
{
    for( int i = 0; i < static_cast<int>( table.size() ); ++i ) {
        for( CHashTableNode* node = table[i]; node != nullptr; ) {
            CHashTableNode* next = node->Next;
            delete node;
            node = next;
        }
    }
}

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

bool CHashTable::Add( const string& key )
{
    int hash = SimpleStringHash( key, table.size() );
    for( CHashTableNode* node = table[hash]; node != nullptr; node = node->Next ) {
        if( node->Key == key ) {
            return false;
        }
    }
    // Проверили, что key в таблице нет. Добавим его в начало цепочки.
    CHashTableNode* newNode = new CHashTableNode( key );
    newNode->Next = table[hash];
    table[hash] = newNode;
    return true;
}

bool CHashTable::Remove( const string& key )
{
    int hash = SimpleStringHash( key, table.size() );
    if( table[hash] == nullptr ) {
        return false;
    }
    CHashTableNode* node = table[hash];
    if( node->Key == key ) {
        // Если требуется удалить первый элемент.
        table[hash] = node->Next;
        delete node;
        return true;
    }
    for( CHashTableNode* nodeNext = node->Next; nodeNext != nullptr; node = nodeNext, nodeNext = nodeNext->Next ) {
        if( nodeNext->Key == key ) {
            node->Next = nodeNext->Next;
            delete nodeNext;
            return true;
        }
    }
    return false;
}

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