ETS Operations Runtime

Question

Что такое время выполнения delete_object для сумки ETS? Учитывая, что есть n записи с одинаковым ключом kБудет ли время выполнения delete_object быть O(n) или же O(1)? Если это действительно O(1)как lookup операция вернуть все кортежи отсортированные по времени вставки?

Спасибо!

Answer 1

Это сообщение в списке рассылки erlang относится к 2011 году, но я предполагаю, что оно, вероятно, все еще имеет место:

http://erlang.org/pipermail/erlang-questions/2011-October/061705.html

Ответ, данный Сверкером Эрикссоном, подразумевает, что время поиска будет O(n) по количеству равных ключей:

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