Hashtable с двусвязными списками?

Question

Введение в алгоритмы (CLRS) утверждает, что хэш-таблица, использующая двусвязные списки, способна удалять элементы быстрее, чем таблица со односвязными списками. Кто-нибудь может сказать мне, в чем преимущество использования двусвязных списков вместо единственного связанного списка для удаления в реализации Hashtable?

Answer 1

Путаница здесь связана с обозначениями в CLRS. Чтобы соответствовать истинному вопросу, я использую нотацию CLRS в этом ответе.

Мы используем хеш-таблицу для хранения пар ключ-значение. Часть значения не упоминается в псевдокоде CLRS, а ключевая часть определяется как k.

В моей копии CLR (здесь я работаю над первым выпуском) подпрограммы, перечисленные для хэшей с цепочкой, включают вставку, поиск и удаление (с более подробными именами в книге). Процедуры вставки и удаления принимают аргумент x, , который является элементом связанного списка, связанным с ключом key[x]. Процедура поиска принимает аргумент k, который является ключевой частью пары ключ-значение. Я полагаю, что путаница заключается в том, что вы интерпретировали процедуру удаления как получение ключа, а не элемента связанного списка.

Поскольку x является элементом связанного списка, одного его достаточно для удаления O (1) из связанного списка в слоте h(key[x]) хеш-таблицы, , если это дважды связанный список . Однако, если это односвязный список, наличие x недостаточно. В этом случае вам нужно начать с заголовка связанного списка в слоте h(key[x]) таблицы и обходить список, пока, наконец, вы не нажмете x, чтобы получить его предшественника. Только когда у вас есть предшественник x, удаление может быть выполнено, поэтому в книге говорится, что случай с одиночной связью приводит к одинаковому времени выполнения для поиска и удаления.

Дополнительное обсуждение

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

Процедуры псевдокода находятся на более низком уровне, чем если бы вы представляли пользователю интерфейс хэш-таблицы. Например, процедура удаления, которая принимает ключ k в качестве аргумента, отсутствует. Если это удаление предоставляется пользователю, вы, вероятно, просто придерживаетесь односвязных списков и имеете специальную версию поиска, чтобы сразу найти x, связанный с k и его предшественником.

Answer 2

К сожалению, моя копия CLRS сейчас находится в другой стране, поэтому я не могу использовать ее как справочную. Однако вот что я думаю:

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

x.left.right = x.right;
x.right.left = x.left;

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

pred.next = x.next

Итак, когда вы удаляете элемент из хеш-таблицы, вы ищите его (O (1) из-за свойств хеш-таблиц), а затем удаляете его в O (1), так как у вас теперь есть адрес.

Если бы это был односвязный список, вам нужно было бы найти предшественника объекта, который вы хотите удалить, что заняло бы O (n).

---

Тем не менее:

Меня также немного смущает это утверждение в случае цепочек хеш-таблиц из-за того, как работает поиск. В цепочечной хэш-таблице, если есть столкновение, вам уже нужно пройтись по связанному списку значений, чтобы найти нужный элемент, и, следовательно, также необходимо будет найти его предшественника.

Но то, как формулируется выражение, дает пояснение: «Если хеш-таблица поддерживает удаление, то ее связанные списки должны быть дважды связаны, чтобы мы могли быстро удалить элемент. Если списки были связаны только по одному, то удалить элемент x, нам сначала нужно найти x в списке T [h (x.key)], чтобы мы могли обновить следующий атрибут предшественника x. "

Это говорит о том, что у вас уже есть элемент x, что означает, что вы можете удалить его описанным выше способом. Если бы вы использовали односвязный список, даже если у вас уже был элемент x, вам все равно придется найти его предшественника, чтобы удалить его.

Answer 3

Если элементы в вашей хеш-таблице хранятся в «навязчивых» списках, они могут знать о связанном списке, членом которого они являются.Таким образом, если навязчивый список также является двусвязным, элементы могут быть быстро удалены из таблицы.

(Тем не менее, обратите внимание, что «навязчивость» может рассматриваться как нарушение принципов абстракции ...)

Пример: в объектно-ориентированном контексте навязчивый список может потребовать, чтобы все элементы были получены из базового класса.

class BaseListItem {
  BaseListItem *prev, *next;

  ...

public: // list operations
  insertAfter(BaseListItem*);
  insertBefore(BaseListItem*);
  removeFromList();
};

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

Answer 4

Давайте спроектируем структуры данных для кеширующего прокси.Нам нужна карта от URL до контента;давайте использовать хеш-таблицу.Нам также нужен способ найти страницы для выселения;давайте будем использовать очередь FIFO для отслеживания порядка последнего обращения к URL, чтобы мы могли реализовать исключение LRU.В C структура данных может выглядеть примерно так:

struct node {
    struct node *queueprev, *queuenext;
    struct node **hashbucketprev, *hashbucketnext;
    const char *url;
    const void *content;
    size_t contentlength;
};
struct node *queuehead;  /* circular doubly-linked list */
struct node **hashbucket;

Одна тонкость: чтобы избежать особого случая и тратить место в хэш-базах, x->hashbucketprev указывает на указатель, указывающий на x.Если x первый в корзине, он указывает на hashbucket;в противном случае он указывает на другой узел.Мы можем удалить x из его корзины с помощью

x->hashbucketnext->hashbucketprev = x->hashbucketprev;
*(x->hashbucketprev) = x->hashbucketnext;

. При исключении мы выполняем итерации по наименее недавно доступным узлам через указатель queuehead.Без hashbucketprev нам пришлось бы хэшировать каждый узел и находить его предшественника с линейным поиском, поскольку мы не достигли его через hashbucketnext.(Является ли это на самом деле плохо спорно, учитывая, что хэш должен быть дешевым и цепь должна быть короткой. Я подозреваю, что комментарий вы спрашиваете о был в основном холостым.)

Answer 5

Hashtable часто реализуется как вектор списков.Где индекс в векторе - это ключ (хеш).
Если у вас не более одного значения на ключ и вас не интересует логика в отношении этих значений, достаточно одного связанного списка.Более сложный / специфический дизайн при выборе одного из значений может потребовать двойного связанного списка.

Answer 6

Я могу вспомнить одну причину, но это не очень хорошая причина.Предположим, у нас есть хеш-таблица размером 100. Теперь предположим, что значения A и G добавлены в таблицу.Возможно, A хэширует в слот 75. Теперь предположим, что G также хэширует до 75, и наша политика разрешения коллизий заключается в том, чтобы переходить на постоянный размер шага 80. Поэтому мы пытаемся перейти к (75 + 80)% 100 = 55. Теперь,вместо того, чтобы начинать с начала списка и проходить вперед на 85, мы могли бы начать с текущего узла и перейти назад на 20, что быстрее.Когда мы дойдем до узла, в котором находится G, мы можем пометить его как надгробный камень, чтобы удалить его.

Тем не менее, я рекомендую использовать массивы при реализации хеш-таблиц.