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

Описание

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