HashTableOnChains

#include <assert.h>
#include <iostream>
#include <string>
#include <vector>
using std::string;

// Хеш-функция, опирающаяся на первый символ строки.
int Hash( const std::string& key, int tableSize )
{
    assert( tableSize > 0 );
    if( key.empty() ) {
        return 0;
    }
    return key[0] % tableSize;
}

const int TableSize = 256;

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, CHashTableNode* next ) : Key( key ), Next( next ) {}
    };
    std::vector<CHashTableNode*> internalTable;
};

CHashTable::CHashTable() :
    internalTable( TableSize, nullptr )
{
}

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

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

bool CHashTable::Add( const string& key )
{
    const int hash = Hash( key, TableSize );
    for( CHashTableNode* node = internalTable[hash]; node != nullptr; node = node->Next ) {
        if( node->Key == key ) {
            return false;
        }
    }
    internalTable[hash] = new CHashTableNode( key, internalTable[hash] );
    return true;
}

bool CHashTable::Remove( const string& key )
{
    const int hash = Hash( key, TableSize );

    // Храним в node указатель на ту область памяти, которая хранит указатель на элемент списка.
    // Если этот элемент списка надо удалить, то обновляем указатель
    for( CHashTableNode** node = &internalTable[hash]; *node != nullptr; node = &( *node )->Next ) {
        if( ( *node )->Key == key ) {
            CHashTableNode* toDelete = *node;
            *node = toDelete->Next;
            delete toDelete;
            return true;
        }
    }
    return false;
}

int main()
{
    CHashTable table;

    char command = 0;
    std::string value;
    while( std::cin >> command >> value ) {
        bool commandSucceeded = false;
        switch( command ) {
            case '+':
                commandSucceeded = table.Add( value );
                break;
            case '-':
                commandSucceeded = table.Remove( value );
                break;
            case '?':
                commandSucceeded = table.Has( value );
                break;
            default:
                assert( false );
        }
        std::cout << ( commandSucceeded ? "OK" : "FAIL" ) << std::endl;
    }
    return 0;
}