Самостоятельная работа по теме : Хеш-таблицы и функции

Сопротивление до изображения
Это свойство означает, что в вычислительном отношении должно быть трудно перевернуть хеш-функцию.
Другими словами, если хеш-функция h создала хеш-значение z, то будет трудно найти любое входное значение x, которое хэширует к z.
Это свойство защищает от злоумышленника, который имеет только хэш-значение и пытается найти входные данные.
Сопротивление второго изображения
Это свойство означает, что заданы входные данные и их хэш, должно быть трудно найти другой входной файл с тем же хешем.
Другими словами, если хеш-функция h для входа x создает хеш-значение h (x), то должно быть трудно найти любое другое входное значение y такое, что h (y) = h (x).
Это свойство хэш-функции защищает от злоумышленника, у которого есть входное значение и его хэш, и он хочет заменить другое значение допустимым значением вместо исходного входного значения.
Сопротивление столкновению
Это свойство означает, что должно быть трудно найти два разных входа любой длины, которые приводят к одному и тому же хешу. Это свойство также называется хеш-функцией без столкновений.
Другими словами, для хеш-функции h трудно найти любые два различных входа x и y, для которых h (x) = h (y).
Поскольку хеш-функция является функцией сжатия с фиксированной длиной хеш-функции, невозможно, чтобы хеш-функция не имела коллизий. Это свойство отсутствия столкновений только подтверждает, что эти столкновения трудно найти.
Это свойство очень мешает злоумышленнику найти два входных значения с одинаковым хешем.
Кроме того, если хеш-функция устойчива к столкновениям, она является второй устойчивой к изображениям.
Методы борьбы с коллизиями
В идеальном случае, когда заранее известны все пары ключ-значение, достаточно легко реализовать идеальную хеш-таблицу, в которой время поиска будет постоянным (используется идеальная хеш-функция, которая определяет положения в таблице по целым значениям и без столкновений).
Но в большинстве случаев приходится бороться с коллизиями. Обычно применяются методы цепочек и открытой индексации.
Метод цепочек
Этот метод часто называют открытым хешированием. Его суть проста — элементы с одинаковым хешем попадают в одну ячейку в виде связного списка.
То есть, если ячейка с хешем уже занята, но новый ключ отличается от уже имеющегося, то новый элемент вставляется в список в виде пары ключ-значение.
Если выбран метод цепочек, то вставка нового элемента происходит за O(1), а время поиска зависит от длины списка и в худшем случае равно O(n). Если количество ключей n, а распределяем по m-ячейкам, то соотношение n/m будет коэффициентом заполнения.
В C++ метод цепочек реализуется так:
class LinkedHashEntry {
private:
int key;
int value;
LinkedHashEntry *next;
public:
LinkedHashEntry(int key, int value) {
this->key = key;
this->value = value;
this->next = NULL;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
void setValue(int value) {
this->value = value;
}
LinkedHashEntry *getNext() {
return next;
}
void setNext(LinkedHashEntry *next) {
this->next = next;
}
};