Вот иногда есть много всяких int'ов, и нужно их всех запомнить. Можно применить для этого Arraylist, но мсдн говорит что он медленный, можно применить для этого хэш-коллекцию (забыл как называется), но там ненужное свойство "Value" есть. Что использовать оптимальнее всего?

Если ты уверен, что такой подход не доставит тебе проблем при отладке, а затем и при поддержке проекта (с символьными переменными гораздо проще разбираться, нежели с записями вроде list[5]), то следует использовать List<int>. Он и быстрее ArrayList, да и проверку типов осуществляет на этапе компиляции.

Ну, я под ArrayList имел List<int> ввиду 

Ну и почему тогда он медленный?

При поиске значений хэш<int> теоретически быстрее. Дык вот я и думаю, а есть ли что-то быстрее хэша и эрэйлиста.

Для хешируемых коллекций (SortedList, Dictionary, HashTable) помимо самого значения нужен ключ, причём уникальный. Если int-ы удовлетворяют этому требованию, то можно идля ключа использовать то же значение. Выгода будет в случае необходимости часто производить поиск по коллекции (занимает всегда О(1), при этом, если разумно задать Capacity, то и добавление будет тоже О(1)).

Иначе - List<int>. Про медленность - очень спорно, хоть поиск "в лоб" и занимает О(n), но обращение к элементам и их добавление  практически такое же, как и у массивов (он на базе массива и сделан, просто обернули удобными методами и автоматическим расширением).

У меня такой вопрос. Если использовать просто ArrayList добавление какая сложность
удаление какая сложность максимум естественно. И поиск.
И насколько быстрее это в List<int>.
Просто у меня задача которая требует количество итераций не более log(n). Насколько возможно такая реализация.

И ещё 1 вопрос. При исползования нумератора для коллекции. Если я удаляю элемент с первой позиции это занимает O(1) шаг в arrayList или максимум O(n)?
Буду благодарен за ответы, чем быстрее тем лучше