smatskevich

HashTableOnChains

Apr 22nd, 2017
197
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <assert.h>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. using std::string;
  6.  
  7. // Хеш-функция, опирающаяся на первый символ строки.
  8. int Hash( const std::string& key, int tableSize )
  9. {
  10.     assert( tableSize > 0 );
  11.     if( key.empty() ) {
  12.         return 0;
  13.     }
  14.     return key[0] % tableSize;
  15. }
  16.  
  17. const int TableSize = 256;
  18.  
  19. class CHashTable {
  20. public:
  21.     CHashTable();
  22.     ~CHashTable();
  23.  
  24.     // Проверка наличия ключа в таблице.
  25.     bool Has( const string& key ) const;
  26.     // Добавление ключа в таблицу. Возвращает false, если такой ключ уже есть.
  27.     bool Add( const string& key );
  28.     // Удаление ключа из таблицы. Возвращает false, если такого ключа нет.
  29.     bool Remove( const string& key );
  30.  
  31. private:
  32.     // Элемент односвязного списка.
  33.     struct CHashTableNode {
  34.         string Key;
  35.         CHashTableNode* Next;
  36.  
  37.         explicit CHashTableNode( const string& key, CHashTableNode* next ) : Key( key ), Next( next ) {}
  38.     };
  39.     std::vector<CHashTableNode*> internalTable;
  40. };
  41.  
  42. CHashTable::CHashTable() :
  43.     internalTable( TableSize, nullptr )
  44. {
  45. }
  46.  
  47. CHashTable::~CHashTable()
  48. {
  49.     for( int i = 0; i < internalTable.size(); ++i ) {
  50.         for( CHashTableNode* node = internalTable[i]; node != nullptr; ) {
  51.             CHashTableNode* next = node->Next;
  52.             delete node;
  53.             node = next;
  54.         }
  55.     }
  56. }
  57.  
  58. bool CHashTable::Has( const string& key ) const
  59. {
  60.     const int hash = Hash( key, TableSize );
  61.     for( CHashTableNode* node = internalTable[hash]; node != nullptr; node = node->Next ) {
  62.         if( node->Key == key ) {
  63.             return true;
  64.         }
  65.     }
  66.     return false;
  67. }
  68.  
  69. bool CHashTable::Add( const string& key )
  70. {
  71.     const int hash = Hash( key, TableSize );
  72.     for( CHashTableNode* node = internalTable[hash]; node != nullptr; node = node->Next ) {
  73.         if( node->Key == key ) {
  74.             return false;
  75.         }
  76.     }
  77.     internalTable[hash] = new CHashTableNode( key, internalTable[hash] );
  78.     return true;
  79. }
  80.  
  81. bool CHashTable::Remove( const string& key )
  82. {
  83.     const int hash = Hash( key, TableSize );
  84.  
  85.     // Храним в node указатель на ту область памяти, которая хранит указатель на элемент списка.
  86.     // Если этот элемент списка надо удалить, то обновляем указатель
  87.     for( CHashTableNode** node = &internalTable[hash]; *node != nullptr; node = &( *node )->Next ) {
  88.         if( ( *node )->Key == key ) {
  89.             CHashTableNode* toDelete = *node;
  90.             *node = toDelete->Next;
  91.             delete toDelete;
  92.             return true;
  93.         }
  94.     }
  95.     return false;
  96. }
  97.  
  98. int main()
  99. {
  100.     CHashTable table;
  101.  
  102.     char command = 0;
  103.     std::string value;
  104.     while( std::cin >> command >> value ) {
  105.         bool commandSucceeded = false;
  106.         switch( command ) {
  107.             case '+':
  108.                 commandSucceeded = table.Add( value );
  109.                 break;
  110.             case '-':
  111.                 commandSucceeded = table.Remove( value );
  112.                 break;
  113.             case '?':
  114.                 commandSucceeded = table.Has( value );
  115.                 break;
  116.             default:
  117.                 assert( false );
  118.         }
  119.         std::cout << ( commandSucceeded ? "OK" : "FAIL" ) << std::endl;
  120.     }
  121.     return 0;
  122. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×