Помощью построения хеш-таблиц

Понятия хеш-функции и хеш-таблицы. Методы хеширования: метод деления, метод середины квадратов, метод свертывания

Коллизии. Методы разрешения коллизий: метод открытой адресации и метод цепочек

Задачи, решаемые с помощью построения хеш-таблиц

Литература: [8, с. 567-597]

Вопросы для самоконтроля

1 Каков принцип построения хеш-таблиц?

2 Существуют ли универсальные методы построения хеш-таблиц? Ответ обоснуйте.

3 Почему возможно возникновение коллизий?

4 Каковы методы устранения коллизий? Охарактеризуйте их эффективность в различных ситуациях.

5 Назовите преимущества открытого и закрытого хеширования.

6 В каком случае поиск в хеш-таблицах становится неэффективен?

7 Как выбирается метод изменения адреса при повторном хешировании?

8 В чем заключается суть каждого метода для разрешения коллизии?

Список используемых источников

1 Кнут, Д. Искусство программирования. Т.1 / Д. Кнут. – М.: Вильямс, 2001. - 976 с.

2 Кнут, Д. Искусство программирования. Т.2 / Д. Кнут. – М.: Вильям, 2001. - 988 с.

3 Кормен, Т Алгоритмы: построение и анализ / пер. с англ. под ред. А. Шейя. – М.:МЦНМО, 2002. – 960 с.

4 Красиков, И. В. Алгоритмы. Просто, как дважды два / И. В. Красиков, И. Е. Красикова. – М.:Эксмо, 2007. – 256 с.

5 Липский, В. Комбинаторика для программистов / В. Липский. – М: Мир, 1988. – 200 с.

6 Макконнелл, Дж. Основы современных алгоритмов. / Дж. Макконнелл. – М: Техносфера, 2004. – 368 с.

7 Окулов, С. М. Программирование в алгоритмах / С. М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2002. – 341 с.

8 Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/ Сортировка/Поиск / пер. с англ. / Роберт Седжвик. – К: Издательство «ДиаСофт», 2001. – 688 с.

9 Хусаинов, Б. С. Структуры и алгоритмы обработки данных. Примеры на языке Си: учеб. пособие / Б. С. Хусаинов. – М.:Финансы и статистика, 2004. – 464 с.

Задания на домашнюю контрольную работу по учебной

Дисциплине «Структуры и алгоритмы обработки данных»