O (1) Удалить операцию

Question

Существует ли какая-либо структура данных или вариация существующей структуры данных, которая предлагает O (1) или постоянную сложность времени для операции удаления?

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

Answer 1

А как насчет HashSets?Они предлагают постоянную производительность по времени для добавления / удаления / содержит / размер.

В Java это называется HashSet

Answer 2

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

Вы на правильном пути.В Java то, что вы описываете, называется LinkedHashSet .

Идея такова: у вас есть 2 структуры данных:

1. LinkedList [двусвязный список] элементов
2. HashMap: Elements-> Nodes - каждый ключ в хэш-карте сопоставляется с соответствующим узлом в связанном списке.

Используя этот DS, вы получаете следующие операции:

add(x):
  if map.containsKey(x):
    return
  list.addLast(x)
  map.put(x,list.getLastNode()) 

delete(x):
  if (map.containsKey(x) == false):
    return
  list.deleteNode(map.get(x))
  map.delete(x)

Обратите внимание, что для добавления и удаления используются O(1), они выполняют только окончательное число операций O(1) на карте и в списке.

Answer 3

Вы ищете выборочное (для объекта) удаление в этой записи O?Я думаю, что если это большая коллекция объектов, необходимых для времени Х, но после этого они все отбрасываются, то пул памяти, который вы можете просто пометить как «свободный», понимая, что вся выделенная из него память теперь недействительна,работа (используется при выгрузке уровня для игры при подготовке к загрузке нового, если вы хотите пример.)

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

Answer 4

Да, их несколько.Удаление верхнего элемента стека - O (1), что допустимо, потому что у вас есть доступ только к вершине стека.Хеш-таблицы также имеют амортизированное удаление O (1) для любого элемента таблицы.

Answer 5

Конечно, есть, но с матерью всех предостережений .

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

Редактировать

Ответ, первоначально говоривший о отсортированном массиве , ноэто был неправильный выбор слов (извините, не английский родной).Я имел в виду indexed , как в классическом случае массива (например, C) - по сути, это означает, что в доступе к элементам массива нет скрытого O (> 1) (для установки удаленного флага).

Еще один момент: я имею в виду только удаление, а не поиск и удаление