http://alexslav99.pythonanywhere.com/
Целью данной работы является сравнение различных методов борьбы с коллизиями:
- Метод цепочек;
- Метод открытой адресации (см. Кормен, 3-е издание, 11.4 Открытая адреация);
- Метод кукушки (см. https://en.wikipedia.org/wiki/Cuckoo_hashing).
- Для интереса, предлагается также сделать сравнения со стандартными средствами языка c++: std::map, std::hash_map. Вдруг получится их обогнать. Замечание: В качестве хеш-функций используйте только функции из универсальных семейств, про них рассказывалось на семинарах. Список универсальных хеш-функций можно найти здесь https://en.wikipedia.org/wiki/Universal_hashing. Что измеряется?
- Время вставки;
- Время удаления;
- Время поиска. Более конкретно об измерении: Нужно выбрать какое-то стартовое значение N, скажем 100, выбрать шаг step, скажем пусть step = 100, и выбрать максимальное значение, скажем 100 000. После чего нужно для каждого N с шагом step от минимального значения до максимального построить таблицу размера N (из случайных элементов, или сделать выборку из заранее подготовленной базы) и произвести одну или несколько операций (если несколько, скажем 10, то нужно усреднить). Измеряем именно время одной операции. Некоторые допускают ошибку и делают N вставок с замером времени, но не понятно, что в итоге Вы измерили. Входные данные: a) Случайные натуральные числа. б) Случайные вектора или строки. с) Очень бы хотелось увидеть как поведут себя таблицы на real life данных, например на словарях или словах какого нибудь литературного произведения. Ваш вывод должен содержать:
- График зависимости скорости вставки от количества элементов в таблице;
- График зависимости скорости удаления от количества элементов в таблице;
- График зависимости скорости поиска от количества элементов в таблице; На каждом графике должно быть несколько кривых, по одной или больше для каждого подхода. Заметим также, что таблицы из подходов 1) и 2) имеют дополнительный параметр m – ёмкость таблицы. Хорошо бы построить на графиках кривые для разных значений m, например m = 2n, m = n, m = ½ n. Но это не обязательно.