smatskevich

SimpleStringHashTable

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

×