Proxy

Они там по-ходу хеши используют для связки значения с узлом, а из самих узлов строят AVL-дерево, которым всё это сортируют.

С теоретической точки всё правильно:
Добавление:

O(1) на один хеш + O(1) на другой + O(log n) для добавления в дерево.
И того O(log n)

А с массивами надо было бы искать место вставки O(log n) + пододвигать элементы справа O(n).
И того O(n) - оценка хуже

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

Может я и напрасно назвал эти сортированные коллекции интересными.
SortedList только в динамической памяти не мусорит и должен показать приемлемую скорость.

А мне ascommons нравятся. Правда юзаю только log, reflect и async.

Ну так это опять же, наивная реализация. Можно же сделать B+tree из массивов, например. Ну и не добавлением единым, есть еще много других операций. Наверняка тот, кто будет использовать такую коллекцию создает ее для того, чтобы сортировать.

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

Можно попробовать разложить дерево в массив и сохранять список индексов, из которых удалялись элементы (один элемент - значение, 2 следующих - индекс правого и левого поддерева)
Хотя AVL-дерево так эффективно как куча на массив не ляжет. Плюс там линкованный список разложить на массив - уже весело, а реализовывать вращение поддеревьев, которые лежат в массиве - там сплошное жонглирование индексами будет (и не продебажить - у тебя линейная структура с индексами заплетёнными в клубок)

Вот в AS3 всегда так: нельзя просто взять и реализовать эффективный алгоритм с Википедии - накладные расходы на поддержание структуры данных весь прирост съедят. Да и в Java, наверно, с этим не легче.