Задание 4. По учебной практике УП.01. ИССЛЕДОВАНИЕ ЛОГИКИ РАБОТЫ ПРОГРАММЫ, ПОСТРОЕННОЙ НА ВЗАИМОДЕЙСТВИИ ОБЪЕКТОВ И КЛАССОВ. Динамические структуры и классы в С# (на основе коллекций). Хэш-таблицы и словари. Хеш-таблицы. Применений хэш-таблиц. Простое пр

Задание 4

По учебной практике УП.01

ИССЛЕДОВАНИЕ ЛОГИКИ РАБОТЫ ПРОГРАММЫ, ПОСТРОЕННОЙ НА ВЗАИМОДЕЙСТВИИ ОБЪЕКТОВ И КЛАССОВ

Динамические структуры и классы в С# (на основе коллекций)

Хэш-таблицы и словари

Хеш-таблицы

Хеш-таблица (hash table) — это специальная структура данных для хранения пар ключей и их значений. По сути это ассоциативный массив, в котором ключ представлен в виде хеш-функции.

Пожалуй, главное свойство hash-таблиц — все три операции: вставка, поиск и удаление — в среднем выполняются за время O(1), среднее время поиска по ней также равно O(1) и O(n) в худшем случае.

Применений хэш-таблиц

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

Простое представление хеш-таблиц

Чтобы разобраться, что такое хеш-таблицы, представьте, что вас попросили создать библиотеку и заполнить ее книгами. Но вы не хотите заполнять шкафы в произвольном порядке.

Первое, что приходит в голову — разместить все книги в алфавитном порядке и записать все в некий справочник. В этом случае не придется искать нужную книгу по всей библиотеке, а только по справочнику.

А можно сделать еще удобнее. Если изначально отталкиваться от названия книги или имени автора, то лучше использовать некий алгоритм хеширования, который обрабатывает входящее значение и выдает номер шкафа и полки для нужной книги.

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

Учтите, что хеш-функция должна иметь следующие свойства:

· Всегда возвращать один и тот же адрес для одного и того же ключа;

· Не обязательно возвращает разные адреса для разных ключей;

· Использует все адресное пространство с одинаковой вероятностью;

· Быстро вычислять адрес.

12 3 4 Следующая ⇒