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

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

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

Давайте спроектируем структуры данных для кэширующего прокси. Нам нужна карта от 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. (Действительно ли это плохо, спорно, учитывая, что хэш должен быть дешевым, а цепочка должна быть короткой. Я подозреваю, что комментарий, который вы спрашивать об этом было в основном бесполезно.)

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

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

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

class BaseListItem {
  BaseListItem *prev, *next;

  ...

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

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

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

В принципе, двусвязный список поддерживает 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, вам все равно придется найти его предшественника, чтобы удалить его.