Почему удаление элементов хэш-таблицы с использованием двусвязного списка - O (1)?

Ответ 1

Представленная здесь проблема: рассмотрим, что вы смотрите на определенный элемент хеш-таблицы. Как дорого его удалять?

Предположим, у вас есть простой связанный список:

v ----> w ----> x ----> y ----> z
                |
            you're here

Теперь, если вы удалите x, вам нужно соединить w с y, чтобы связать ваш список. Вам нужно получить доступ к w и сообщить ему, чтобы он указывал на y (вы хотите иметь w ----> y). Но вы не можете получить доступ к w из x, потому что он просто связан! Таким образом, вам нужно пройти весь список, чтобы найти w в операциях O (n), а затем сообщить ему ссылку на y. Это плохо.

Тогда предположим, что вы дважды связаны:

v <---> w <---> x <---> y <---> z
                |
            you're here

Прохладный, вы можете получить доступ к w и y отсюда, чтобы вы могли подключить два (w <---> y) в операции O (1)!

Ответ 2

В общем, вы правы - алгоритм, который вы опубликовали, берет сам элемент как входной, но не только его ключ:

Обратите внимание, что CHAINED-HASH-DELETE принимает в качестве входного элемента элемент x, а не его key k, так что нам не нужно искать x сначала.

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

Ответ 3

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

Ответ: это немного сложно, но по сути да, мы можем - по крайней мере, обычно. Мы не (обычно) должны пройти весь связанный список, чтобы найти предыдущий элемент. Вместо этого мы можем поменять местами данные между текущим элементом и следующим элементом, а затем удалить следующий элемент.

Единственное исключение - это когда/если нам нужно/нужно удалить последний элемент в списке. В этом случае нет следующего элемента для обмена. Если вам действительно нужно это сделать, нет реального способа избежать поиска предыдущего элемента. Тем не менее, есть способы, которые обычно будут работать, чтобы избежать этого - один из них заключается в том, чтобы прервать список с помощью часового, вместо нулевого указателя. В этом случае, поскольку мы никогда не удаляем node со значением дозорного, нам никогда не придется удалять последний элемент в списке. Это оставляет нам относительно простой код, что-то вроде этого:

template <class key, class data>
struct node {
    key k;
    data d;
    node *next;
};

void delete_node(node *item) {
    node *temp = item->next;
    swap(item->key, temp->key);
    swap(item->data, temp->data);
    item ->next = temp->next;
    delete temp;
}

Ответ 4

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

Ответ 5

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

Если после запуска Find(x) вы решите, что хотите удалить возвращаемый объект, вы обнаружите, что внутри хэш-таблицы, возможно, придется снова искать свой объект. Это все равно будет O (1), а не большая сделка, но вы обнаружите, что вы удаляете очень много, вы можете сделать немного лучше. Вместо прямого возврата пользовательского элемента верните указатель на основной хеш node. Затем вы можете воспользоваться некоторыми внутренними структурами. Поэтому, если в этом случае вы выбрали дважды связанный список, чтобы выразить свою цепочку, то во время процесса удаления нет необходимости повторно компилировать хэш и снова искать коллекцию - вы можете опустить этот шаг. У вас достаточно информации для выполнения права на удаление с места, где вы сидите. Дополнительная осторожность должна быть предпринята, если node, который вы отправляете, является головкой node, поэтому для обозначения местоположения вашего node в исходном массиве может использоваться целое число, если оно является заголовком связанного списка.

Компромисс - это гарантированное пространство, которое занимает дополнительный указатель, и возможное ускорение удаления (и немного более сложный код). С современными рабочими столами пространство обычно очень дешево, поэтому это может быть разумным компромиссом.

Ответ 6

Кодовая точка зрения: для реализации этого можно использовать unordered_map в С++.

unordered_map<value,node*>mp;

Где node* - указатель на структуру, хранящую ключ, левый и правый указатели!

Как использовать:

Если у вас есть значение v, и вы хотите удалить, что node просто выполните:

• Доступ к этому значению узлов, например mp[v].

• Теперь просто сделайте левую указательную точку с node справа.

И вуаля, все готово.

(Просто чтобы напомнить, в С++ unordered_map требуется среднее значение O (1) для доступа к сохраненному определенному значению.)

Ответ 7

Учебник ошибочен. У первого члена списка нет привычного "предыдущего" указателя, поэтому необходим дополнительный код, чтобы найти и отменить связь элемента, если он окажется первым в цепочке (обычно 30% элементов являются главой их цепочки, если N = M, (при отображении N элементов в M слотов, каждый слот имеет отдельную цепочку.))

EDIT:

Лучше использовать обратную ссылку - использовать указатель для ссылки, которая указывает на нас (как правило, → следующая ссылка предыдущего node в списке)

struct node {
   struct node **pppar;
   struct node *nxt;
   ...
   }

удаляется, а затем становится:

*(p->pppar) = p->nxt;

И приятной особенностью этого метода является то, что он работает одинаково хорошо для первого node в цепочке (чей указатель pppar указывает на некоторый указатель, который не является частью node.

ОБНОВЛЕНИЕ 2011-11-11

Потому что люди не видят моей точки зрения, я попытаюсь проиллюстрировать. В качестве примера есть хэш-таблица table (в основном массив указателей) и buch узлов one, two, three один из которых должен быть удален.

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one->next = two , two-next = three, three->next = NULL;
                one->prev = NULL, two->prev = one, three->prev = two;


    /* How to delete element one :*/
    if (one->prev == NULL) {
            table[31] = one->next;
            }
    else    {
            one->prev->next = one->next
            }
    if (one->next) {
            one->next->prev = one->prev;
            }

Теперь очевидно, что код Oove равен O (1), но есть что-то противное: ему все еще нужен array и индекс 31, поэтому в большинстве случаев a node является "автономным", и указатель на node достаточно, чтобы удалить его из своей цепочки, кроме, когда это будет первый node в своей цепочке; тогда потребуется дополнительная информация, чтобы найти table и 31.

Затем рассмотрим эквивалентную структуру с указателем на указатель в качестве обратной ссылки.

    struct node {
            struct node *next;
            struct node **ppp;
            char payload[43];
            };

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one-next = two , two-next = three, three->next = NULL;
                one->ppp = &table[31], two->ppp = &one->next, three->ppp = &two-next;

    /* How to delete element one */
    *(one->ppp) = one->next;
    if (one->next) one->next->ppp = one->ppp;

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

Часто в сценарии {prev, next} особых случаев избегают, добавляя фиктивный node в начале двойного связанного списка; Но это нужно также выделять и инициализировать.