Реализация прямой адресной таблицы

Question

я был дан в качестве домашнего задания Introduction to Algorithms упражнения 11.1-3, который идет следующим образом:

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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