Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using std::cin;
- using std::cout;
- using std::vector;
- class FixedSet {
- private:
- vector<int> numbers; //хранимый массив
- int** hash_table; //хэш-таблица
- int a_hash_index, b_hash_index; //индексы для хэш-функции первого уровня
- int** table_hash_index; //таблица с индексами для хэш-функций второго уровня
- vector<int>* temp_hash; // временный массив векторов. Позволяет определить идеальную хэш-функцию.
- int numbers_size; //число входных данных
- public:
- FixedSet(const vector<int>&);
- ~FixedSet();
- const bool Contains(int);
- };
- const unsigned int big_prime = 1000000007; //очень большое простое число
- void Enter(vector<int>&);//ввод
- int Random(int, int); //случайное число в указаном диапозоне.
- int Hash_function(int, int, int, int); //хэш-функция. a, b, x, n.
- bool Collizion(vector<int>&, int, int); //определяет есть ли коллизии для данных коэфициентов хэш-функции и данного набора данных
- int main() {
- vector<int> numbers;
- vector<int> numbers_for_find;
- Enter(numbers);
- Enter(numbers_for_find);
- FixedSet set(numbers);
- for(unsigned int index_number_for_find = 0; index_number_for_find < numbers_for_find.size(); ++index_number_for_find) {
- if (set.Contains(numbers_for_find[index_number_for_find]) == true) {
- cout << "Yes\n";
- }
- else {
- cout << "No\n";
- }
- }
- return 0;
- }
- void Enter(vector<int>& numbers) {
- int num_elements;
- int buffer;
- cin >> num_elements;
- for(int number_of_number = 0; number_of_number < num_elements; ++number_of_number) {
- cin >> buffer;
- numbers.push_back(buffer);
- }
- }
- FixedSet::FixedSet(const vector<int>& input) {
- numbers = input; //копирование
- numbers_size = numbers.size(); //установка кол-ва элементов
- hash_table = new int*[numbers.size()]; //создание хэш-таблицы
- table_hash_index = new int*[numbers.size()]; //создание таблицы с параметрами функций
- temp_hash = new vector<int>[numbers.size()]; //временная таблица
- for(unsigned int i = 0; i < numbers.size(); ++i) {
- hash_table[i] = NULL;
- table_hash_index[i] = NULL;
- }
- a_hash_index = Random(1, big_prime - 1);//Генерирование хэш-функции
- b_hash_index = Random(0, big_prime - 1);//первгого уровня
- for (int i = 0; i < numbers.size(); ++i) {
- int hash_value = Hash_function(a_hash_index, b_hash_index, numbers[i], numbers.size()); //"Расбрасывание" значений во временную таблицу
- temp_hash[hash_value].push_back(numbers[i]); // для вычисления идеальных хэш-функций
- }
- for (int index_first_hash = 0; index_first_hash < numbers.size(); ++index_first_hash) {
- int size = temp_hash[index_first_hash].size();
- if (size > 0) {
- hash_table[index_first_hash] = new int[size * size]; //создание в хэш-таблице квадратичного массива
- for(int j = 0; j < size * size; j++) {
- hash_table[index_first_hash][j]= -2147483648;
- }
- int temp_a = Random(1, big_prime - 1), temp_b = Random(1, big_prime); //генерирование случайных параметров хэш-функции
- while (Collizion(temp_hash[index_first_hash], temp_a, temp_b)) { //пока есть коллизии
- temp_a = Random(1, big_prime - 1);//Генерируем параметры функции
- temp_b = Random(1, big_prime); //
- }
- table_hash_index[index_first_hash] = new int[3]; //заполнение
- table_hash_index[index_first_hash][0] = temp_a; //таблицы
- table_hash_index[index_first_hash][1] = temp_b; //хэш-функций
- table_hash_index[index_first_hash][2] = size*size;//
- for(int runner = 0; runner < temp_hash[index_first_hash].size(); ++runner) { //пробегая по массиву
- int second_hash = Hash_function(temp_a, temp_b, temp_hash[index_first_hash][runner], size*size); //считаем хэш
- hash_table[index_first_hash][second_hash] = temp_hash[index_first_hash][runner]; //заносим по хэшам в ячейку
- }
- }
- }
- delete[] temp_hash; //удаляем временную таблицу
- }
- FixedSet::~FixedSet() {
- if (hash_table != NULL) {
- for (unsigned int runner = 0; runner < numbers.size(); ++runner) {
- if (hash_table[runner] != NULL) {
- delete[] hash_table[runner];
- }
- }
- delete[] hash_table;
- }
- if (table_hash_index != NULL)
- {
- for (unsigned int runner = 0; runner < numbers.size(); ++runner) {
- if (table_hash_index[runner] != NULL) {
- delete[] table_hash_index[runner];
- }
- }
- delete[] table_hash_index;
- }
- }
- const bool FixedSet::Contains(int num_for_search) {
- int first_hash = Hash_function(a_hash_index, b_hash_index, num_for_search, numbers_size); //считаем хэш-первого уровня
- if (hash_table[first_hash] == NULL) {
- return false;
- }
- int a = table_hash_index[first_hash][0]; // Определяем хэш-функцию
- int b = table_hash_index[first_hash][1]; // второго
- int size = table_hash_index[first_hash][2]; // уровня
- int second_hash = Hash_function(a, b, num_for_search, size); // считаем хэш второго уровня
- if (hash_table[first_hash][second_hash] == num_for_search) { //сравниваем
- return true;
- }
- return false;
- }
- int Random(int from, int till) {
- if (till > from) {
- return (from + (((rand() * rand()) % (till - from)) + 1));
- }
- return 0;
- }
- int Hash_function(int a, int b, int x, int n) {
- return ((a * x + b) % big_prime) % n;
- }
- bool Collizion(vector<int>& Array, int a, int b) {
- vector<int> hash_value;
- for(int i = 0; i < Array.size(); ++i) {
- int temp = Hash_function(a, b, Array[i], Array.size() * Array.size()); //считаем хэши
- for(int j = 0; j < hash_value.size(); ++j) {
- if (hash_value[j] == temp && Array[j] != Array[i]) {//если находим такой-же выходим
- return true;
- }
- }
- hash_value.push_back(temp); //иначе заносим хэш в базу
- }
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment