Лабораторная работа №1 Хэш-таблица Вариант 9 Работу Студент 2 курса Группы №2125 Назарьев Сергей Санкт-Петербург



Скачать 52.98 Kb.
Дата13.02.2017
Размер52.98 Kb.
Просмотров191
Скачиваний0
ТипЛабораторная работа

Университет ИТМО
Кафедра ИПМ
Алгоритмы и структуры данных

Лабораторная работа № 1


Хэш-таблица


Вариант 9

Работу выполнил:

Студент 2 курса

Группы № 2125

Назарьев Сергей

Санкт-Петербург

2015 г.

Цель работы:

Требуется разработать программу, реализующую комбинированный способ организации таблицы идентификаторов. Для организации таблицы используется простейшая хэш-функция, указанная в варианте задания, а при возникновении коллизий используется дополнительный метод размещения идентификаторов в памяти. Если в качестве этого метода используется дерево или список, то они должны быть связаны с элементом главной хэш-таблицы. В каждом варианте требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.


Вариант 9.

Хэш-функция: сумма кодов первой и последней букв



Способ разрешения коллизий: упорядоченный список с логарифмическим поиском

c:\users\zar\downloads\неназванная диаграмма.png
Алгоритм поиска в хэш-таблице:


  1. Находим hash от элемента и назовём его hashstr.

  2. Выберем из массива указателей указатель, находящийся по индексу hashstr. Это указатель на дерево (выступает в роли корзины), в котором может лежать наш элемент.

  3. Обходим бинарное дерево поиска, сравниваем каждый узел с нашим элементом.

Вывод:
Хэш-таблица позволяет реализовать некоторые очень часто используемые в жизни структуры данных: ассоциативные массивы и математические множества реализованы именно с помощью хэш-таблиц. На опыте данной лабораторной работы можно легко заметить, как сильно зависит скорость работы от размеров корзины. Для того, чтобы хэш-таблица хорошо работала (=высокая скорость доступа), её “корзины” должны быть минимального размера, то есть хэш-функция, которую использует хэш-таблица, должна уметь раскидывать данные максимально равномерно. В случае данной лабораторной работы, результаты работы хэш-функции слишком часто совпадали, из-за чего корзины заполнялись неравномерно и вся прелесть хэш-таблицы “улетучивалась”.

Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал