Что: Лекция
Когда: Суббота, 20 октября 2018, 14:30–16:05
Где: НГУ, ауд. 2128
Слайды: algorithms_1_lecture_201018.pdf

Описание

Хеш-функции. Коллизии. Разрешение коллизий методом цепочек, методом последовательных проб и методом двойного хеширования. Гипотеза простого равномерного хеширования, оценка средней длины цепочки. Универсальные семейства хеш-функций, оценка средней длины цепочки. Построение универсального семейства для целочисленных ключей. Совершенные хеш-функции. Построение совершенной хеш-функции с помощью универсального семейства (размер m = O(n^2)). Двухуровневая хеш-таблица (размер m = O(n)).

Видео