Ограничения: время – 250ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Реализовать хеш-таблицу с открытой адресацией (без удаления)
Операции
создать пустой набор // HTable<int> t(1009);
количество элементов // int kol=t.size();
добавить k // t.insert(5);
проверить наличие k // bool b=t.contains(5);
В качестве хеш-функции использовать
`h(k, i) = (h_1(k) + i*h_2(k)) mod m`
где `k` вычислять как ``std::hash<T>{}(key)``, `i` -- номер исследования,
`h_1(k) = k mod m`, `h_2(k) = 1 + (k mod (m-1))`.
```c++
template <typename T>
class HTable {
int n=0, m;
vector<bool> F; // ячейка заполнена
vector<T> H; // значения
int find(T key) const {...}
public:
HTable(int m):m(m),F(m,0),H(m){}
int size() const { return n; }
bool contains(T key) const { ... }
void insert(T key) { ... }
};
```
Пример использования:
```c++
int main()
{ HTable<int> t(1009);
t.insert(10); // {10}
t.insert(20); // {10,20}
t.insert(15); // {10,15,20}
cout<<t.size()<<"\n"; // 3
cout<<t.contains(10)<<"\n"; // 1
cout<<t.contains(25)<<"\n"; // 0
}
```
В качестве решения отправлять завершенное определение класса
Начало
Рабочее место участника
Учебные задачи: АиСД. Деревья. Множества, отображения, хеш-таблицы