Реализация таблицы прямых адресов
В качестве домашней работы мне дали упражнение " Введение в алгоритмы " 11.1-3 что выглядит следующим образом:
Предложите, как реализовать таблицу прямого доступа, в которой ключи хранимых элементов не должны различаться, а элементы могут иметь спутниковые данные. Все три словарные операции (вставка, удаление и поиск) должны выполняться за O(1) раз. Не забывайте, что Delete принимает в качестве аргумента указатель на удаляемый объект, а не ключ.
Что ж, вставить не проблема, так как это просто означает создание связанного списка в соответствующем месте в таблице (если он еще не существует) и добавление элемента к нему. Поиск, которому дан ключ, может вернуть любой из элементов, которые соответствуют ключу, так что это просто означает, что нам нужно вернуть заголовок списка соответствия в таблице.
Моя проблема с операцией удаления. Если я изменю объект, добавив к нему указатель на его узел в связанном списке, я могу удалить его в O(1), но я не уверен, что мне разрешено изменять объект. Есть ли способ сделать это без изменения данного объекта?
5 ответов
Это вопрос из книги Кормена? Насколько я понимаю, после прочтения предыдущих абзацев в этой книге объект, который вы храните в таблице прямого доступа, является "вашим" объектом. Таким образом, вы можете, как вы предлагаете, хранить указатели на двусвязные списки в таблице, где каждый элемент списка имеет указатель на объект пользователя. Затем словарная операция SEARCH возвращает элемент списка, и пользователь должен использовать дополнительный шаг, чтобы добраться до своего объекта. Аналогично операция DELETE получает указатель на элемент списка.
Имеет ли это смысл? Я не хочу портить твою домашнюю работу!
Мы можем использовать двойной связанный список для каждого индекса таблицы прямых адресов. Слот j будет содержать указатель на заголовок списка, который содержит все элементы со значением ключа j, и, если таких элементов нет, слот j содержит NIL. INSERT-вставка x в начало списка займет всего O(1) времени. ПОИСК - он может вернуть любой элемент, который соответствует данному ключу, и, таким образом, возвращение заголовка списка займет всего O(1) времени. УДАЛЕНИЕ - Поскольку мы использовали двойной связанный список, мы можем удалить элемент за O(1) времени, используя указатель на предыдущий и следующий узлы.
Я думаю, что вы можете использовать спутниковые данные для отображения в качестве вторичного ключа. Тогда это своего рода двухуровневая хеш-таблица. Что касается операции DELETE, сначала мы используем первичный ключ. И когда есть дублированные первичные ключи, мы используем вторичные ключи, чтобы получить объект. Следовательно, общее время по-прежнему равно O(1).
Хеш-таблицы будут работать для вас до определенного момента. Как только у вас начнутся коллизии, оно станет O(1+k/n), где k - количество ключей, а n - размер таблицы. Если вы сделаете запланированное изменение размера и повторного хэширования, то вы можете избежать этого. Не знаю, повлияет ли это на ваш рейтинг эффективности, поскольку это не происходит во время вставки, удаления или поиска.
Удаление, не изменяя объект, может быть достигнуто простым установкой указателя ссылки на хэш-значение на ноль. Прямых изменений в объекте не производится, но вносятся изменения в контейнер объектов.
Я думаю, что для большинства ограничений, которые вы даете, хеш-таблица может быть реализована определенным образом, чтобы обойти их. На http://en.wikipedia.org/wiki/Hash_table есть дополнительная информация о том, как реализовать хеш-таблицу.
Самая важная часть.."реализовать таблицу прямого доступа, в которой ключи хранимых элементов не должны быть различимы" и "словарная операция за время O(1).
Вставка также невозможна за время O(1), если элементы равны (как говорит Q, элементы не должны быть различимыми).
Для удаления части вы должны взять ключи, а также объекты, чтобы добраться до определенного объекта, и принять ключ от спутниковых данных, чтобы добраться до определенного объекта.
Я думаю, что только 2 идеи имеют смысл для O(1) времени.