Цитата:
|
Опять же, комментарий мой. Наивность реализации заключается в том, что для сортированной хеш-таблицы было бы куда выгоднее использовать массив, или два массива, вместо использования двух (а в реальности трех) хеш таблиц.
|
Они там по-ходу хеши используют для связки значения с узлом, а из самих узлов строят AVL-дерево, которым всё это сортируют.
С теоретической точки всё правильно:
Добавление:
O(1) на один хеш + O(1) на другой + O(log n) для добавления в дерево.
И того O(log n)
А с массивами надо было бы искать место вставки O(log n) + пододвигать элементы справа O(n).
И того O(n) - оценка хуже
Но это в теории.
А на практике вряд ли это будет работать быстрее (может быть только на очень больших числах), потому что создание объекта-узла в динамической памяти дорого, плюс куча операций и вызовов функций.
Может я и напрасно назвал эти сортированные коллекции интересными.
SortedList только в динамической памяти не мусорит и должен показать приемлемую скорость.