Новость

Харламов Вадим Сергеевич (БПИ225) A2

Для сравнения квадратического и кубического пробирования напишем программу, которая будет выполнять заполнение хэш-таблицы используя квадратичное и кубическое пробирование.

Тесты будут проводиться для с таблицами размера 2^m, где m ∈ [5, 12], а в качестве хэш функции будет использоваться остаток от деления на 2^m.

Создадим вектор случайных ключей от 1 до 5000, в количестве 2^m / 2:

После чего выполним вставку всех значений используя квадратичное пробирование, во время вставки будем считать кол-во коллизий и проб

Аналогично сделаем с кубическим пробированием

Теперь, имея 2 хэш-таблицы определим количество кластеров и их длины

Метод вернет нам вектор, где индексом будет длина кластера, а значением – их количество.

Теперь выведем все кластеры и сравним полученные результаты, ориентируясь на количество коллизий, проб, кол-во кластеров и их размеры.

Для M = 32:

Для M = 512

Для M = 4096:

Заметим, что при M = 32 и 512 количество коллизий и размерности/количество кластеров были примерно на одном уровне, но при увеличении M, количество коллизий для кубического пробирования уменьшается, а также заметно уменьшается максимальный размер кластеров (52 у квадратичного и 26 у кубического), таким образом, можно сделать вывод, что кубическое пробирование действительно может немного улучшить работу со вставками при больших M, уменьшая размерности кластеров.