Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100). учебное пособие
| Вид материала | Учебное пособие |
| 0.8.2 Непосредственный доступ Простой непосредственный доступ Непосредственный доступ с использованием хеш-адресации Линейное рехеширование. |
- Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной, 1650.9kb.
- Рабочая программа для специальности: 220400 Программное обеспечение вычислительной, 133.96kb.
- Государственный Технический Университет. Факультет: Автоматики и Вычислительной Техники., 32.46kb.
- Образования Республики Молдова Колледж Микроэлектроники и Вычислительной Техники Кафедра, 113.64kb.
- Постоянное развитие и углубление профессиональных навыков в области информационных, 54.56kb.
- «Программное обеспечение вычислительной техники и автоматизированных систем», 1790.14kb.
- Задачи дисциплины: -изучение основ вычислительной техники; -изучение принципов построения, 37.44kb.
- Лекция №2 «История развития вычислительной техники», 78.1kb.
- Система контроля и анализа технических свойств интегральных элементов и устройств вычислительной, 582.84kb.
- Московский государственный инженерно-физический институт (технический университет), 947.05kb.
0.8.2 Непосредственный доступ
При необходимости непосредственного доступа (random access) устанавливается связь между адресом запоминания и ключом, по которому ищется запись.
Простой непосредственный доступ
В простейшем случае ключ поиска - просто номер записи. Чаще ключ - некоторая совокупность данных из записи. По значению ключа либо непосредственно вычисляется адрес записи (например, адрес расположения физического блока фиксированной длины на диске вычисляется по его номеру), либо ключ используется для доступа к справочнику, в котором отыскивается адрес (например, адрес начала расположения i-го файла задается i-й записью в директории). Метод очень быстрый - мы немедленно получаем доступ к записи. Но он может быть очень расточительным по использованию памяти, когда из полного возможного набора в N ключей, по которым вырабатываются адреса в диапазоне от 0 до N-1, фактически будет иметься только K << N ключей, т.е. из всего диапазона адресов 0-(N-1) будет использоваться только K адресов, раскиданных по всему объему от 0 до N-1.
Непосредственный доступ с использованием хеш-адресации
В таких случаях значение ключа используется для вычисления функции расстановки (hash code), определяющей адрес расположения данных. Причем функция расстановки подбирается такой, чтобы для K ключей из полного допустимого набора в N ключей, генерируемое количество адресов L было возможно более близко к K. Этот подход обычно используется при поиске информации об объекте по его имени, например, для поиска информации об объекте по его наименованию, для поиска информации в базе данных о сотруднике по его фамилии, для работы с таблицей идентификаторов в трансляторах и т.д. В этом случае функция расстановки вычисляется из символов ключа. Идеальная функция расстановки должна вычислять уникальный адрес для каждого из фактических ключей. Реальные же функции расстановки могут для разных ключей давать один и тот же адрес. Рассмотрим частный пример (табл. 9.1) занесения информации в таблицу из 10 элементов (L равно 10). В качестве ключа используем наименование объекта. Для вычисления хеш-адреса Hn в диапазоне 0-9 суммируем коды символов ключа, из которых предварительно вычитаем 65. В качестве хеш-адреса берем остаток от деления полученной суммы на 10. (На самом деле число 10 не годится, а выбрано для наглядности).
| Пример вычисления хеш-адреса. | Таблица 9.1 | |||||||
| Ключ | Коды символов ключа | Хеш-адрес | ||||||
| GALLERY | 71 | 65 | 76 | 76 | 69 | 82 | 89 | 3 |
| HOUSE | 72 | 79 | 85 | 83 | 69 | | | 3 |
| MIRROR | 77 | 73 | 82 | 82 | 79 | 82 | | 5 |
| RING | 82 | 73 | 78 | 71 | | | | 4 |
| SCENE | 83 | 67 | 69 | 78 | 69 | | | 1 |
Из табл. 9.1. видно, что для двух разных ключей GALLERY и HOUSE вычислен одинаковый хеш-адрес, равный 3. Предложен ряд способов разрешения таких коллизий. Рассмотрим один из них, называемый рехешированием.
Перед занесением очередной строки в таблицу проверяем занят ли элемент. Если элемент таблицы свободен, то выполняем занесение. Если же элемент таблицы уже занят, то сравниваем ключи So уже занесенного и Sn заносимого элементов. Если они совпали, то выполняем какую-либо процедуру реагирования на одинаковые ключи и завершаем занесение. Например, для базы данных по кадрам выдаем диагностику о том что информация о данном сотруднике уже есть, для таблицы идентификаторов формируем сообщение о повторном описании и т.п. Если же ключи So и Sn не совпали, то вычисляется новый адрес в таблице по формуле:
| (0.1.1) |
где Hn - исходный хеш-адрес, Pi - некоторое число, L - длина таблицы.
Если этот элемент также оказался занятым, то задается новое значение Pi и по формуле (0.4.26) вычисляется следующий адрес т.д., пока не будет найден некоторый элемент, который либо пуст, либо содержит ключ Sn, либо не будет получен исходный хеш-адрес. В последнем случае работа прекращается из-за переполнения таблицы. Используются несколько основных способов рехеширования [12,]:
Линейное рехеширование. В этом, наиболее распространенном и простом случае P1 равно 1, P2 равно 2 и т.д.
Число сравнений E (1 - V/2)(1-V), где V - коэффициент заполненности таблицы.
10% - E = 1.06 сравнений,
50% - E = 1.50 сравнений,
90% - E = 5.50 сравнений.
Случайное рехеширование. При этом способе Pj - псевдослучайное число.
Способ хорош при L = 2m где m - целое.
Число сравнений E - (1/V)log(1-V).
10% - E = 1.05 сравнений,
50% - E = 1.39 сравнений,
90% - E = 2.56 сравнений.
Рехеширование сложением с выбором. При этом способе Pi = i ×Hn (i = 1L-1),.
Способ хорош когда L - простое число.
Квадратичное рехеширование. При этом способе Pi = A×(i2) + B×i + C.
Здесь A, B, C - произвольные числа, выбор которых определяется эффективностью вычисления формулы на конкретной машине.
Время вычислений хеш-адреса меньше чем при случайном рехешировании.
Если L - простое число, то E L/2.
Третья форма организации данных - списки, когда логическая и физическая организация данных разделены и для доступа к данным используются указатели на данные.
Далее будем рассматривать структуры данных с использованием списков указателей.