Как правильно удалять элементы хэш таблицы?

Ссылка скопирована
C# Алгоритмы
1 ответ

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

Но я сталкиваюсь с такой проблемой во время определения того, является ли удаляемый элемент последним в цепочке коллизий:
Например, я помещаю ключ 2 в таблицу и он получает позицию 15, затем помещаю ключ 5 в таблицу, для него вычисляется позиция 14, но она занята неким элементом, далее квадратичным пробингом вычисляется позиция 15, она так-же занята, затем вычисляется позиция 1 и она свободна, он помещается в позицию 1.
Сейчас мы имеем, что элемент с ключом 2 находится в 15 позиции, а элемент с ключом 5 находится в позиции 1 и в цепочке коллизий 14 15 1.
Теперь, пытаясь удалить элемент с ключом 2 (в позиции 15) я не могу никак узнать, могу ли я отметить его ячейку как свободную.

Как решать эту проблему?

Дополнительно:

Судя по всему метод открытой адресации - это проосто нехороший метод для решения проблем хеширования. Я не знаю, толи преподаватели пошли очень душные. Толи студенты любопытные, но всех
тянет как магнитом к open addressing (OA), хотя многие продуктовые библиотеки коллекций C++/C#/Java
просто не используют OA по дефолту. Они берут Separate Chaining и это работает всегда хорошо.

Я-бы сделал следующую рекомендацию. Поскольку удаление элемента при OA - тяжелая операция,
которая требует перепроверки всех элементов цепочки ключа, то лучше вообще не удалять а
пере-создавать новую таблицу или отказаться от OA в пользу Separate Chaining.

  • Зачем при удалении проверять всю цепочку? Или вы про обычный поиск элемента? Ну так эта часть не сложнее чем добавление/поиск.
  • Вы обязаны проверять всю цепочку до тех пор пока
    - не найдете нужный элемент
    - не найдете пустое место
    - пока идут надгробные камни
    - пока вы не исчерпали лимит проверок. Например при размере OA hashtable например в
    миллион элементов и при линейном опробировании вы можете по кругу пройти
    всю адресную емкость таблицы.

Ответы:

Никак. Конечно, можно проверить, что там дальше ячейка пустая через k*k для всех возможных k (или что ячейка на (k-1)^2 назад пуста), но это слишком долго. И не сработает во всех случаях. Поэтому так и не делают вообще. Обычно "удаленные" значения убирают при перехешировании, которое все-равно придется делать при достаточном заполнении таблицы.

  • Да, рехеширование это дело решает, просто на него не хочу надеяться, вдруг оно будет излишне редким.
  • Герман, При этом вы отметили ответом "не удаляйте, а если надо, то пересоздавайте таблицу", что и есть то самое рехеширование.
  • Герман, Кстати, оно не может быть очень редким. Оно случится ровно тогда, когда вы достаточное количество раз добавите элементы в таблицу. Оно обязательно случиться, если у вас элементов/"надгробий" (удаленных заглушек) станет в таблице слишком много. И оно при этом случится достаточно редко, чтобы амартизированно не ухудшать временную сложность добавления/удаления с O(1).
Нужно решить такую задачу?

Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.

Заказать помощь
Лучший ответ
1
Елена Вебер Ответ

Для удаления элементов из хэш таблицы в PHP можно воспользоваться функцией unset(). Эта функция удаляет указанный элемент по его ключу. Вот пример использования unset() для удаления элемента из хэш таблицы:

$hashTable = array(
    'key1' => 'value1',
    'key2' => 'value2',
    'key3' => 'value3'
);
 
// Удаляем элемент с ключом 'key2'
unset($hashTable['key2']);
 
print_r($hashTable);

$hashTable = array( 'key1' => 'value1', 'key2' => 'value2', 'key3' => 'value3' ); // Удаляем элемент с ключом 'key2' unset($hashTable['key2']); print_r($hashTable);

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

Если вы хотите удалить все элементы из хэш таблицы, можно воспользоваться функцией unset() в цикле:

$hashTable = array(
    'key1' => 'value1',
    'key2' => 'value2',
    'key3' => 'value3'
);
 
foreach($hashTable as $key => $value) {
    unset($hashTable[$key]);
}
 
print_r($hashTable);

$hashTable = array( 'key1' => 'value1', 'key2' => 'value2', 'key3' => 'value3' ); foreach($hashTable as $key => $value) { unset($hashTable[$key]); } print_r($hashTable);

Этот код удалит все элементы из хэш таблицы, и на экран будет выведен пустой массив.

Таким образом, для удаления элементов из хэш таблицы в PHP используйте функцию unset() с указанием ключа элемента, который вы хотите удалить.

Другие ответы (0)

Пока нет других ответов. Будьте первым, кто поможет автору.

Ответить на вопрос

комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Вам также может быть интересно

VPN Как правильно настроить vless для Android TV? 0 ответов Pyrogram Как правильно зарегистрировать юзер бота в Telegram? 0 ответов печатные-платы Как заставить запускаться программу M3.exe от компании Hanxing AOI в инспекционной машине на Windows 7 Pro? 0 ответов Telegram Как добиться, чтобы Telegram прислал мне именно смс код, а не через звонок его диктовал? 0 ответов