Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstdlib> // для функций rand() и srand()
- #include <list>
- #include <iterator>
- using namespace std;
- const int c = 3; // O(n) ~ 3n
- const int p = 2000000033;
- int rand_int(int min, int max)
- {
- static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
- return static_cast<int>(rand() * fraction * (max - min + 1) + min);
- }
- int uni_hash(int a, int b, int m, int key)
- {
- return ((a * key + b) % p) % m);
- }
- struct Node
- {
- int a;
- int b;
- vector<int>* second_table = NULL;
- vector<int> keys;
- int count_keys = 0;
- };
- class FixedSet
- {
- vector<struct Node> nodes; //вектор ячеек первой хэш табл
- vector<vector<int>> second_tables;
- int count_numbers;
- int table_size;
- // vector<vector<int>> vec(2, vector<int>(10));
- public:
- FixedSet();
- void Initialize(const vector<int>& numbers);
- bool Contains(int number) const;
- void print();
- };
- FixedSet::FixedSet()
- {
- this->count_numbers = 0;
- this->nodes;
- this->table_size = 0;
- }
- void FixedSet::Initialize(const vector<int>& numbers)
- {
- this->count_numbers = numbers.size();
- this->table_size = c * count_numbers;
- //Задаём размеры таблиц
- this->nodes.resize(table_size);
- this->second_tables.resize(table_size); //внутренние размера 0
- int m1 = c * count_numbers; //Размер 1 уровня
- int hash, key;
- bool flag = false; //Тру если простроили корректно
- while (!flag) //!!!!!!!!!!!!!!!!!! Написать чистку вектора мб работать с копией но тогда как
- //!указывать на нее
- {
- a = rand_int(1, p - 1);
- b = rand_int(0, p - 1); //Глобальная ХФ
- //Закинули все ключи в таблицу
- for (int i = 0; i < this->count_numbers; ++i)
- {
- key = numbers[i];
- hash = uni_hash(a, b, table_size, key);
- nodes[hash].keys.push_back(key);
- nodes[hash].count_keys += 1;
- }
- //Теперь считаю коллизии
- int S = 0;
- for (int i = 0; i < this->table_size; ++i)
- {
- S += (nodes[i].count_keys) * (nodes[i].count_keys);
- }
- if (S <= this->table_size)
- {
- flag = true;
- }
- else //Чистка
- {
- this->nodes.clear();
- nodes.resize(this->table_size);
- }
- }
- //Вышли из вайл - значит успешно построили первый уровень, теперь второй:
- int b_i;
- for (int i = 0; i < this->table_size; ++i)
- {
- flag = false;
- while (!flag) //Повторяю попытки пока не получится без коллизий (добавить проврку на пустоту)
- {
- b_i = nodes[i].count_keys;
- second_table_size = b_i * b_i * c;
- this->second_tables[i].resize(
- second_table_size); //создать таблицу второго уровня для данного ключ
- a = rand_int(1, p - 1);
- b = rand_int(0, p - 1); // i-ая ХФ для второго слоя
- //Для каждого ключа в ячейке генерю хэш и отправляю в соот табл
- for (int j = 0; j < b_i; ++j)
- {
- key = nodes[i].keys[j];
- hash = uni_hash(a, b, second_table_size, key);
- this->second_tables[i][hash] = key;
- }
- //Теперь проверяю на коллизции
- int z = 0;
- for (int k = 0; k < second_table_size; ++k)
- {
- //тут надо как то понять что уже такое встречалось
- if ()
- z++;
- break;
- }
- if (z == 0)
- flag = true;
- }
- }
- }
- void FixedSet::print()
- {
- cout << "\n print: \n";
- for (int i = 0; i < nodes.size(); ++i)
- {
- cout << "i= " << i << " : ";
- for (int j = 0; j < nodes[i].keys.size(); ++j)
- cout << nodes[i].keys[j] << endl;
- }
- cout << endl;
- }
- int main()
- {
- cout << "Hello World";
- FixedSet f;
- vector<int> numbers = { 1, 2, 3 };
- f.Initialize(numbers);
- // f.print();
- return 0;
- }
Add Comment
Please, Sign In to add comment