С помощью этого класса решается модельная задача: на входе дается множество различных чисел, а затем множество запросов - целых чисел. Для каждого запроса определяется, лежит ли число из запроса в множестве.
#include <cstdio>
#include <vector>
#include <cstdlib>
using std::vector;
const long long g_BigPrimeNumber = 2147483647;
inline long long hashFunction(long long a_coefficient,
long long b_coefficient,
long long x) {
return (((a_coefficient * x + b_coefficient) % g_BigPrimeNumber) +
g_BigPrimeNumber) % g_BigPrimeNumber;
}
inline void generateHashFunctionCoefficients(long long *a, long long *b) {
*a = rand() % (g_BigPrimeNumber - 1) + 1;
*b = rand() % g_BigPrimeNumber;
}
class FixedSet {
private:
struct PrimaryHashTable {
long long a_coefficient_, b_coefficient_; // Hash function coefficients.
struct SecondaryHashTable {
long long a_coefficient_, b_coefficient_; // Hash function coefficients.
vector<int> numbers_to_store;
vector<int> numbers;
vector<int> numbers_empty; // numbers_empty[i] is true while numbers[i]
// is empty
SecondaryHashTable(): a_coefficient_(0), b_coefficient_(0) {}
};
vector<SecondaryHashTable> secondary_hash_tables_;
// Returns number of cell needed to keep hash table.
unsigned long long memoryToKeepNumbers() const {
unsigned long long result = 0;
for (vector<SecondaryHashTable>::const_iterator sht =
secondary_hash_tables_.begin(); sht != secondary_hash_tables_.end();
++sht) {
result += sht->numbers_to_store.size() * sht->numbers_to_store.size();
}
return result;
}
void cleanNumbersToStore() {
for (vector<SecondaryHashTable>::iterator sht =
secondary_hash_tables_.begin(); sht != secondary_hash_tables_.end();
++sht) {
sht->numbers_to_store.clear();
}
}
// Resizes each secondary hash table to numbers_of_numbers_^2 size and
// generates coefficients a and b for it.
void prepareSecondaryHashTables() {
for (vector<SecondaryHashTable>::iterator sht_iter
= secondary_hash_tables_.begin();
sht_iter != secondary_hash_tables_.end(); ++sht_iter) {
sht_iter->numbers.resize(sht_iter->numbers_to_store.size() *
sht_iter->numbers_to_store.size());
sht_iter->numbers_empty.resize(sht_iter->numbers_to_store.size() *
sht_iter->numbers_to_store.size(), true);
generateHashFunctionCoefficients(&(sht_iter->a_coefficient_),
&(sht_iter->b_coefficient_));
}
}
void fillHashTable() {
for (vector<SecondaryHashTable>::iterator sht_iter
= secondary_hash_tables_.begin();
sht_iter != secondary_hash_tables_.end(); ++sht_iter) {
bool success = false;
while (!success) {
generateHashFunctionCoefficients(&(sht_iter->a_coefficient_),
&(sht_iter->b_coefficient_));
// Clear stored numbers.
sht_iter->numbers_empty.assign(sht_iter->numbers_empty.size(), true);
// Try to refill secondary hash table.
success = true;
for (vector<int>::const_iterator number_iter =
sht_iter->numbers_to_store.begin();
number_iter != sht_iter->numbers_to_store.end(); ++number_iter) {
long long hash_in_sht = hashFunction(sht_iter->a_coefficient_,
sht_iter->b_coefficient_,
*number_iter) %
sht_iter->numbers_to_store.size();
if (sht_iter->numbers_empty[hash_in_sht]) {
sht_iter->numbers[hash_in_sht] = *number_iter;
sht_iter->numbers_empty[hash_in_sht] = false;
} else if (sht_iter->numbers[hash_in_sht] != *number_iter) {
// Fail. Collision again.
success = false;
break;
}
}
}
}
}
} primary_hash_table_;
int total_number_of_numbers_;
static const int k_MemoryLimitMultiplier = 4;
public:
void preparePrimaryHashTable(const vector<int> &numbers) {
primary_hash_table_.secondary_hash_tables_.resize(numbers.size());
do {
generateHashFunctionCoefficients(&(primary_hash_table_.a_coefficient_),
&(primary_hash_table_.b_coefficient_));
primary_hash_table_.cleanNumbersToStore();
for (vector<int>::const_iterator it = numbers.begin();
it != numbers.end(); ++it) {
primary_hash_table_.secondary_hash_tables_[hashFunction(
primary_hash_table_.a_coefficient_,
primary_hash_table_.b_coefficient_, *it) % numbers.size()].
numbers_to_store.push_back(*it);
}
} while (primary_hash_table_.memoryToKeepNumbers() >
k_MemoryLimitMultiplier * numbers.size());
}
void Initialize(const vector<int> &numbers) {
total_number_of_numbers_ = numbers.size();
preparePrimaryHashTable(numbers);
primary_hash_table_.prepareSecondaryHashTables();
primary_hash_table_.fillHashTable();
}
explicit FixedSet() {}
bool Contains(int number) const {
int number_of_sht = hashFunction(primary_hash_table_.a_coefficient_,
primary_hash_table_.b_coefficient_,
number) % total_number_of_numbers_;
if (primary_hash_table_.secondary_hash_tables_[number_of_sht].
numbers_to_store.size() == 0) {
return false;
}
int hash_in_sht = hashFunction(
primary_hash_table_.secondary_hash_tables_[number_of_sht].a_coefficient_,
primary_hash_table_.secondary_hash_tables_[number_of_sht].b_coefficient_,
number) % primary_hash_table_.secondary_hash_tables_[number_of_sht].
numbers_to_store.size();
return (!primary_hash_table_.secondary_hash_tables_[number_of_sht].
numbers_empty[hash_in_sht] &&
primary_hash_table_.secondary_hash_tables_[number_of_sht].
numbers[hash_in_sht] == number);
}
};
void readInputToVector(vector<int> *result_vector) {
int number_of_numbers, current_int;
scanf("%d", &number_of_numbers);
for (int i = 0; i < number_of_numbers; ++i) {
scanf("%d", ¤t_int);
result_vector->push_back(current_int);
}
}
void testNumbers(const FixedSet &fixed_set,
const vector<int> &numbers_to_test,
vector<bool> *result_of_test) {
for (vector<int>::const_iterator it = numbers_to_test.begin();
it != numbers_to_test.end(); ++it) {
result_of_test->push_back(fixed_set.Contains(*it));
}
}
void writeOutput(const vector<bool> &output_vector) {
for (vector<bool>::const_iterator it = output_vector.begin();
it != output_vector.end(); ++it) {
*it ? printf("Yes\n") : printf("No\n");
}
}
int main() {
srand(2010);
vector<int> numbers, numbers_to_test;
vector<bool> result_of_test;
readInputToVector(&numbers);
readInputToVector(&numbers_to_test);
FixedSet fixed_set;
fixed_set.Initialize(numbers);
testNumbers(fixed_set, numbers_to_test, &result_of_test);
writeOutput(result_of_test);
return 0;
}