Таблицы прямого доступа
Здравствуйте. Мне нужна информация по теме, желательно подробная. Можно с примером реализации. Я не могу понять даже разницы между таблицами прямого доступа и хешированными таблицами. Всё, что удалось нарыть:
------------
3.9.1. Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально
быстрый поиск, вляется таблица прямого доступа. В такой таблице
ключ является адресом записи в таблице или может быть преобразо-
ван в адрес, причем таким образом, что никакие два разных ключа
не преобразуются в один и тот же адрес. При создании таблицы вы-
деляется память для хранения всей таблицы и заполняется пустыми
записями. Затем записи вносятся в таблицу - каждая на свое место,
определяемое ее ключом. При поиске ключ используется как адрес и
по этому адресу выбирается запись, если выбранная запись пустая,
то записи с таким ключом вообще нет в таблице.
Таблицы прямого доступа очень эффективны в использовании,
но, к сожалению, область их применения весьма ограничена. Назовем
пространством ключей множество всех теоретически возможных значе-
ний ключей записи. Назовем пространством записей множество тех
слотов в памяти, которые мы выделяем для хранения таблицы. Табли-
цы прямого доступа применимы только для таких задач, в которых
размер пространства записей может быть равен размеру пространства
ключей. В большинстве реальных задач, однако, размер пространства
записей много меньше, чем пространства ключей. Так, если в ка-
честве ключа используется фамилия, то даже ограничив длину ключа
10 символами мы получаем 33^10 возможных значений ключей. Ни в
какой вычислительной системе не может быть выделено пространство
записей такого размера. Даже если ресурсы вычислительной системы
и позволят это, то значительная часть этого пространства будет
заполнена пустыми записями, так как в каждом конкретном заполне-
нии таблицы фактическое множество ключей не будет полностью пок-
рывать пространство ключей.
------------------
Естественно, картину эта статейка прояснила слабенько. Прошу помощи у вас.
------------
3.9.1. Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально
быстрый поиск, вляется таблица прямого доступа. В такой таблице
ключ является адресом записи в таблице или может быть преобразо-
ван в адрес, причем таким образом, что никакие два разных ключа
не преобразуются в один и тот же адрес. При создании таблицы вы-
деляется память для хранения всей таблицы и заполняется пустыми
записями. Затем записи вносятся в таблицу - каждая на свое место,
определяемое ее ключом. При поиске ключ используется как адрес и
по этому адресу выбирается запись, если выбранная запись пустая,
то записи с таким ключом вообще нет в таблице.
Таблицы прямого доступа очень эффективны в использовании,
но, к сожалению, область их применения весьма ограничена. Назовем
пространством ключей множество всех теоретически возможных значе-
ний ключей записи. Назовем пространством записей множество тех
слотов в памяти, которые мы выделяем для хранения таблицы. Табли-
цы прямого доступа применимы только для таких задач, в которых
размер пространства записей может быть равен размеру пространства
ключей. В большинстве реальных задач, однако, размер пространства
записей много меньше, чем пространства ключей. Так, если в ка-
честве ключа используется фамилия, то даже ограничив длину ключа
10 символами мы получаем 33^10 возможных значений ключей. Ни в
какой вычислительной системе не может быть выделено пространство
записей такого размера. Даже если ресурсы вычислительной системы
и позволят это, то значительная часть этого пространства будет
заполнена пустыми записями, так как в каждом конкретном заполне-
нии таблицы фактическое множество ключей не будет полностью пок-
рывать пространство ключей.
------------------
Естественно, картину эта статейка прояснила слабенько. Прошу помощи у вас.
Цитата: Shalfey
Здравствуйте. Мне нужна информация по теме, желательно подробная. Можно с примером реализации. Я не могу понять даже разницы между таблицами прямого доступа и хешированными таблицами.
Принципиальной разницы никакой. Можно даже сказать что таблицы прямого доступа - это частный случай хэширования.
Разница состоит в размере в пространстве ключей. При хешировании пространство ключей меньше пространства записей и, соответственно, возможны (и они случаются) коллизии, чего нет в таблиах прямого доступа.
При хешировании мы используем некую функцию от ключа, которая возвращает нам адрес (числовое значение) в таблице. В таблицах прямого доступа у нас сам ключ интерпретируется как число. Пример с фамилией это демонстрирует: строка длиной в 10 символов интерпретируется как 10-байтовое число.