Существует этот метод Collections.sort(), который внутренне вызывает Arrays.sort(). Это использует сортировку слиянием для сортировки данных, которые имеют порядок O (nlogn). И еще одна информация: если количество сортируемых элементов меньше 7, используется сортировка вставки.
Как и в случае Vector и ArrayList, ниже приведены сложности, поскольку он использует простой массив
- get (index) - O (1)
- add (Объект) - O (n)
- insertAt (int pos, Object value) - O (n)
- удалить (Объект) - O (n)
Еще одна вещь состоит в том, что HashSet внутренне использует HashMap, заботясь только о ключах карты и об объектах, которые игнорируются или не используются, так что нет двух разных реализаций. И HashMap использует бесстолкновительное или идеальное хеширование, генерируя уникальные хеш-коды для каждого объекта. Итак, в идеале порядок будет 1 для вставки и извлечения данных.
Часто в коллекциях Java, особенно в списках, существует обычное сравнение между двумя конкретными реализациями, ArrayList и LinkedList. Порядок LinkedList выглядит следующим образом.
- get (index) - O (n)
- add (Object) - O (1) (при условии, что в связанном списке сохраняется готовый последний указатель)
- insertAt (int pos, Object value) - O (n)
- удалить (Объект) - O (n)