Хэширование

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

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

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

Существует два способа разрешения коллизии:

· Способ открытой адресации. Когда появляется коллизия во время добавления записей ищется свободный участок памяти, куда помещается новая запись. При поиске записи поступают аналогично, т.е. сначала производят поиск по адресу, а затем если запись с искомыми ключами не найдена, последовательно просматриваются остальные участки памяти.

· Способ цепочек. Каждая запись имеет ссылку на область переполнения, в которую записываются цепочки коллизий.

Назначение и основные компоненты операционных систем. Управление памятью. Управление внешними устройствами. Защита данных. Интерфейс прикладного программирования. Пользовательский интерфейс.

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

Общими словами, операционная система — это первый и основной набор программ, загружающийся в компьютер. Помимо вышеуказанных функций ОС может осуществлять и другие, например предоставление пользовательского интерфейса, сетевое взаимодействие и т. п.

С 1990-х наиболее распространенными операционными системами являются ОС семейства Microsoft Windows и UNIX-подобные системы.

Функции:

Интерфейсные функции:

1. Управление аппаратными средствами, устройствами ввода/вывода
2. Файловая система
3. Поддержка многозадачности (разделение использования памяти, времени выполнения)
4. Ограничение доступа, многопользовательский режим работы
5. Сеть

Внутренние функции:

1. Обработка прерываний
2. Виртуальная память
3. Планировщик задач
4. Буферы ввода-вывода
5. Обслуживание драйверов устройств

Операционная система состоит из следующих компонентов:

1. Ядро занимается планировкой задач и обеспечивает доступ к оборудованию.

2. Системные библиотеки предоставляют приложениям интерфейс к функциям ядра на более абстрактном уровне.

3. Оболочка представляет пользовательский интерфейс — интерфейс командной строки или графический пользовательский интерфейс.

4. Низкоуровневые системные утилиты для управления ядром и оборудованием (форматирование дисков, включение/выключение и т.д.)

В некоторых операционных системах (напр. UNIX) ядро и оболочка совершенно независимы и могут независимо заменяться.

Свойства ОС