Внедрение таблицы прямого адреса

Мне было дано домашнее задание Введение в алгоритмы 11.1-3, которое выглядит следующим образом:

Предложите, как реализовать таблицу прямого доступа, в которой ключи сохраненных элементов не обязательно должны быть различны, а элементы могут иметь спутниковые данные. Все три словарных операции (Insert, Delete и Search) должны выполняться в O (1) раз. Не забывайте, что Delete принимает в качестве аргумента указатель на объект, который нужно удалить, а не ключ.

Ну, вставка не проблема, поскольку это просто означает создание связанного списка в соответствующем месте в таблице (если оно еще не существует) и добавление к нему элемента. Поиск, которому дается ключ, может возвращать любой из элементов, соответствующих ключу, поэтому просто означает, что нам нужно вернуть головку списка соответствия в таблице.

Моя проблема заключается в операции Delete. Если я модифицирую объект, чтобы добавить к нему указатель на его node в связанном списке, тогда я могу удалить его в O (1), но я не уверен, что мне разрешено изменять объект. Есть ли способ сделать это без изменения данного объекта?

Ответ 1

Это вопрос из книги Кормена? Насколько я понимаю, из чтения предыдущих абзацев в этой книге объект, который вы храните в таблице прямого доступа, является "вашим" объектом. Таким образом, вы можете, как вы полагаете, хранить указатели на двусвязные списки в таблице, причем каждый элемент списка имеет указатель на объект пользователя. Затем операция поиска по словарю возвращает элемент списка, и пользователь должен использовать следующий шаг для доступа к своему объекту. Аналогично, операция DELETE принимает указатель на элемент списка.

Это имеет смысл? Я не хочу испортить домашнюю работу!

Ответ 2

Я думаю, вы можете использовать спутниковые данные для отображения в качестве вторичного ключа. Тогда это своего рода двухуровневая хеш-таблица. Обеспокоенный операцией DELETE, сначала мы используем первичный ключ. И когда есть повторяющиеся первичные ключи, мы используем вторичные ключи для получения объекта. Поэтому общее время все еще равно O (1).

Ответ 3

Мы можем использовать двойной связанный список в каждом индексе таблицы прямого адреса. Слот j будет содержать указатель на заголовок списка, который содержит все элементы с ключом j, и если такой элементный слот j содержит NIL. INSERT-inserting x во главе списка займет только время O (1). SEARCH- Он может возвращать любой элемент, который соответствует указанному ключу, и, таким образом, возврат главы списка просто займет время O (1). DELETE- Поскольку мы использовали двойной связанный список, мы можем удалить элемент в O (1) раз, указав указатель на предыдущий и следующий узлы.

Ответ 4

Хэш-таблицы будут работать для вас до определенной точки. После того, как вы начинаете иметь collsions, тогда он становится O (1 + k/n), где k - количество ключей, а n - ваш размер таблицы. Если вы измените размер хэша и измените его, вы можете уйти с этим. Не знаю, повлияет ли это на рейтинг эффективности, поскольку это не происходит при вставке, удалении или поиске.

Удаление, не изменяя объект, может быть достигнуто просто установкой указателя ссылки хеша на нуль. Прямое изменение объекта не производится, но сделаны изменения в контейнере объектов.

Я думаю, что для большинства ограничений, которые вы даете, хеш-таблица может быть реализована определенными способами, чтобы обойти их. Дополнительная информация приведена в http://en.wikipedia.org/wiki/Hash_table#Performance_analysis о том, как реализовать хеш-таблицу.

Ответ 5

Самая важная часть.. "реализует таблицу прямого доступа, в которой ключи сохраненных элементов не обязательно должны быть разными" и "операция словаря в течение O (1).

Вставка также невозможна в O (1) раз, если элементы равны (поскольку Q говорит, что элементы не обязательно должны быть разными).

Для удаления части вам нужно взять ключи, а также объекты, чтобы добраться до определенного объекта, а также взять ключ из спутниковых данных, чтобы достичь определенного объекта.

Я думаю, что только за 2 идеи имеют смысл для O (1) времени.