20 март - 25 март

Хеш таблици

• Хеш таблици vs. Масиви, Списъци и Дървета. Приложения на хеш-таблиците

Амортизирано константен достъп, вмъкване, изтриване. Големи масиви от данни, емпирична информация за ключовете.

• Хеш функции и колизии. Пригодност на хеш-функциите

Класически хеш-функции: остатък (прости размери), мултипликативно хеширане, извличане на цифри, сгъване, повдигане на средата на квадрат.

Хеширане на низове: адитивно хеширане.

• Управление на колизии

Отворено хеширане. Терминологична уговорка - това, което в [1] се нарича отворено хеширане, в [2], [3], [4] и др. се нарича затворено и обратно

линейно пробване, квадратично пробване, двойно хеширане.

Затворено хеширане

допълнетелна памет, списък на препълванията.

• Операции

Вмъкване, тъсене, изтриване, управление на редици от елементи, увеличаване на капацитета.

• Литература

1. Наков, П., Добриков, П., Програмиране = ++Алгоритми, стр. 165-179
2. Амерал, Л., Алгоритми и структури от данни в C++, стр 161-174
3. wikipedia.org
4. Шишков, П., колектив, Структури от данни, “Интеграл” Добрич, 1005, стр 314-329

Сортиране

• Сортиране vs. Търсене. Устойчивост и неустойчивост на сортиранията
• Сортиране чрез пермутации. Дърво на сравненията. Теорема за ускорението
• Мехурче. Оптимизации. Клатене
• Пряка селекция
• Сортиране чрез вмъкване (алгоритъм на картоиграча)
• Алгоритъм на Шел

Теми на упражненията

• Кеш за текстов файл със записи:
• Да се реализира като хеш таблица с фиксирана големина
• Да поддържа търсене по ключ (първата дума от реда)
• Справяне с колизиите става като се изхвърля стария запис от таблицата.
• При заявка която липсва в кеша се претърсва файла.
• Ако има време:
• Добавяне на стратегия за справяне с колизии
• Изхвърляне на least recentrly used при превишаване на капацитета (т.е. този който е достъпен най-късно за последен път). (става с двусвързан списък който минава през всички записи).