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