Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- struct cell {
- cell(const std::string &_key) : key(_key), Del(false) {}
- std::string key;
- bool Del;
- };
- class CHashTable {
- public:
- CHashTable() : table(8, NULL), _size(0) {}
- bool insert(const std::string &key);
- bool remove(const std::string &key);
- bool found(const std::string &key) const;
- void ReHash();
- private:
- std::vector<cell*> table;
- int _size;
- };
- int Hash1(const std::string& key, int m) {
- int hash = 0;
- int a = 11;
- for (int i = 0; i < static_cast<int>(key.size()); i++) {
- hash = (hash * a + key[i]) % m;
- }
- return hash;
- }
- int HashFunction(int h1, int i, int m) {
- if (m != 0) {
- return(h1 + i) % m;
- }
- else {
- return 0;
- }
- }
- bool CHashTable::insert(const std::string &key) {
- if (static_cast<double>(_size) / static_cast<double>(static_cast<int>(table.size())) >= 0.75) {
- ReHash();
- }
- int h1 = Hash1(key, static_cast<int>(table.size()));
- int h = HashFunction(h1, 0, static_cast<int>(table.size()));
- for (int i = 0; i < static_cast<int>(table.size()) && table[h] != NULL; i++) {
- if (table[h]->key == key && table[h]->Del == false) {
- return false;
- }
- /*
- if (table[h]->Del == true) {
- table[h]->key = key;
- table[h]->Del = false;
- _size++;
- return true;
- }
- */
- h = HashFunction(h1, i + 1, static_cast<int>(table.size()));
- }
- table[h] = new cell(key);
- _size++;
- return true;
- }
- bool CHashTable::remove(const std::string &key) {
- int h1 = Hash1(key, static_cast<int>(table.size()));
- int j = HashFunction(h1, 0, static_cast<int>(table.size()));
- for (int i = 0; i < static_cast<int>(table.size()); i++) {
- if (table[j] != NULL) {
- if (table[j]->key == key && table[j]->Del == false) {
- table[j]->Del = true;
- return true;
- }
- }
- else {
- return false;
- }
- j = HashFunction(h1, i + 1, static_cast<int>(table.size()));
- }
- }
- bool CHashTable::found(const std::string &key) const {
- int i = 0;
- int h1 = Hash1(key, static_cast<int>(table.size()));
- int h = h1;
- while (table[h] != NULL && i < static_cast<int>(table.size())) {
- if (table[h]->key == key && table[h]->Del == false) {
- return true;
- }
- h = HashFunction(h1, i + 1, static_cast<int>(table.size()));
- i++;
- }
- return false;
- }
- void CHashTable::ReHash() {
- int newBufferSize = static_cast<int>(table.size()) * 2;
- std::vector<cell*> newBuffer(newBufferSize, NULL);
- for (int i = 0; i < static_cast<int>(table.size()); i++) {
- if (table[i] != NULL && table[i]->Del == false) {
- int j = 0;
- int h1 = Hash1(table[i]->key, newBufferSize);
- int h = HashFunction(h1, j, newBufferSize);
- while (j < newBufferSize) {
- if (newBuffer[h] == NULL) {
- break;
- }
- j++;
- h = HashFunction(h1, j, newBufferSize);
- }
- newBuffer[h] = table[i];
- }
- }
- table = newBuffer;
- }
- int main()
- {
- CHashTable table;
- while (std::cin) {
- char a = 0;
- std::string b;
- std::cin >> a >> b;
- if (std::cin.fail())
- {
- break;
- }
- if (a == '+') {
- std::cout << (table.insert(b) ? "OK" : "FAIL") << std::endl;
- }
- if (a=='-'){
- std::cout << (table.remove(b) ? "OK" : "FAIL") << std::endl;
- }
- else {
- std::cout << (table.found(b) ? "OK" : "FAIL") << std::endl;
- }
- }
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement