smatskevich

Hash table on chains

Dec 2nd, 2017
196
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. unsigned int MyEffectiveHash( const string& key, int bound )
  8. {
  9.     return key.empty() ? 0 : ( static_cast<unsigned int>( key[0] ) % bound );
  10. }
  11.  
  12. class CHashTable {
  13. public:
  14.     explicit CHashTable( int initialTableSize );
  15.     ~CHashTable();
  16.  
  17.     // Проверка наличия ключа в хеш-таблице.
  18.     bool Has( const string& key ) const;
  19.     // Добавление ключа. Возвращает false, если ключ уже есть в хеш-таблице, повторно его не добавляет.
  20.     bool Add( const string& key );
  21.     // Удаление ключа. Возвращает false, если ключа нет в хеш-таблице.
  22.     bool Remove( const string& key );
  23.  
  24. private:
  25.     // Узел односвязного списка.
  26.     struct CHashTableNode {
  27.         string Key;
  28.         CHashTableNode* Next;
  29.         explicit CHashTableNode( const string& key ) : Key( key ), Next( nullptr ) {}
  30.     };
  31.     std::vector<CHashTableNode*> table;
  32. };
  33.  
  34. CHashTable::CHashTable( int initialTableSize ) :
  35.     table( initialTableSize, nullptr )
  36. {
  37. }
  38.  
  39. CHashTable::~CHashTable()
  40. {
  41.     // Удаляем все цепочки.
  42.     for( int i = 0; i < static_cast<int>( table.size() ); ++i ) {
  43.         CHashTableNode* current = table[i];
  44.         while( current != nullptr ) {
  45.             CHashTableNode* next = current->Next;
  46.             delete current;
  47.             current = next;
  48.         }
  49.     }
  50. }
  51.  
  52. bool CHashTable::Has( const string& key ) const
  53. {
  54.     const int hash = MyEffectiveHash( key, table.size() );
  55.  
  56.     for( CHashTableNode* node = table[hash]; node != nullptr; node = node->Next ) {
  57.         if( node->Key == key ) {
  58.             return true;
  59.         }
  60.     }
  61.     return false;
  62. }
  63.  
  64. bool CHashTable::Add( const string& key )
  65. {
  66.     const int hash = MyEffectiveHash( key, table.size() );
  67.     for( CHashTableNode* node = table[hash]; node != nullptr; node = node->Next ) {
  68.         if( node->Key == key ) {
  69.             return false;
  70.         }
  71.     }
  72.     CHashTableNode* newNode = new CHashTableNode( key );
  73.     newNode->Next = table[hash];
  74.     table[hash] = newNode;
  75.     return true;
  76. }
  77.  
  78. bool CHashTable::Remove( const string& key )
  79. {
  80.     const int hash = MyEffectiveHash( key, table.size() );
  81.  
  82.     // Если пустой список.
  83.     if( table[hash] == nullptr ) {
  84.         return false;
  85.     }
  86.     // Если удаляемый ключ - первый.
  87.     if( table[hash]->Key == key ) {
  88.         CHashTableNode* toDelete = table[hash];
  89.         table[hash] = toDelete->Next;
  90.         delete toDelete;
  91.         return true;
  92.     }
  93.  
  94.     for( CHashTableNode* prev = table[hash]; prev->Next != nullptr; prev = prev->Next ) {
  95.         // Если удаляемый ключ - следующий.
  96.         if( prev->Next->Key == key ) {
  97.             CHashTableNode* toDelete = prev->Next;
  98.             prev->Next = toDelete->Next;
  99.             delete toDelete;
  100.             return true;
  101.         }
  102.     }
  103.  
  104.     // Предыдущий код можно заменить на следующий:
  105.     //for( CHashTableNode** node = &table[hash]; *node != nullptr; node = &( ( *node )->Next ) ) {
  106.     //  if( ( *node )->Key == key ) {
  107.     //      CHashTableNode* toDelete = *node;
  108.     //      *node = toDelete->Next;
  109.     //      delete toDelete;
  110.     //      return true;
  111.     //  }
  112.     //}
  113.     return false;
  114. }
  115.  
  116. int main()
  117. {
  118.     CHashTable hashTable( 800 );
  119.     char command = 0;
  120.     string key;
  121.     while( std::cin >> command >> key ) {
  122.         switch( command ) {
  123.             case '?':
  124.                 std::cout << ( hashTable.Has( key ) ? "OK" : "FAIL" ) << std::endl;
  125.                 break;
  126.             case '+':
  127.                 std::cout << ( hashTable.Add( key ) ? "OK" : "FAIL" ) << std::endl;
  128.                 break;
  129.             case '-':
  130.                 std::cout << ( hashTable.Remove( key ) ? "OK" : "FAIL" ) << std::endl;
  131.                 break;
  132.         }
  133.     }
  134.     return 0;
  135. }
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.

×