Здравствуйте, Ikemefula, Вы писали:

I>Протести
I>1. удаление
I>2. добавление 1 млн элементов
I>3. итерации по всему списку

Удаление я пока что не рассматривал,
поскольку большинство задач это Вставка и Поиск в хештаблице.
Удаление обычно ограничивается Clear.

I>Например hashset выдыхается на удалении, здесь у него O(N^^2) и все становится грустно.

Попробуй протестировать hashset на вставки.

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

Нельзя, по памяти будет не оптимально для рандом значений.

PC_>>Бенчмарки можно глянуть здесь
PC_>>http://www.sql.ru/blogs/stebelek/1269
I>главное что бы расход памяти не был O(N^^2) Где, кстати расход памяти ?

В колонке вроде есть расход памяти, тоже экономней расходует ...