컬렉션 사용 팁

1. 컬렉션 목록

기억하시겠지만 Java에는 동일한 유형의 객체를 저장하기 위한 편리한 도구인 컬렉션이 있습니다.

주요 컬렉션 관련 인터페이스를 기억해 봅시다.

List , Set , Map 및 Queue .

늘 그렇듯이 도구가 반드시 좋거나 나쁜 것은 아닙니다. 중요한 것은 도구를 의도한 목적에 맞게 사용하고 있는지 여부입니다. 그러기 위해서는 어떤 컬렉션을 언제 사용해야 하는지 알기 위해 특정 기능을 철저히 이해해야 합니다.

1. 목록

가장 많이 사용되는 컬렉션부터 시작하겠습니다.

평범한 오래된 배열에 가능한 한 가깝게 나열하십시오 .

이 컬렉션을 사용하면 배열을 사용하는 경우 컬렉션 자체의 크기에 대해 걱정하지 않고 동일한 유형의 개체 목록을 편리하게 저장할 수 있습니다. 컬렉션의 요소는 인덱스로 액세스됩니다. 개체가 있는 위치를 정확히 알고 있고 요소를 자주 추가하거나 제거할 필요 없이 자주 액세스해야 하는 경우 목록이 이상적 입니다.

2. 설정

세트는 완전히 다른 구조를 가지고 있습니다.

세트 는 고유한 객체를 저장해야 할 때 가장 적합합니다. 예를 들어 각 작성자가 고유한 라이브러리의 작성자 집합입니다. 그러나 우리는 특정 작가를 그냥 가져갈 수는 없습니다. Set을 사용하면 라이브러리에 특정 작성자가 있는지 빠르게 확인할 수 있습니다. 즉, Set에 고유한 개체가 있는지 확인할 수 있습니다 . 또한 전체 컬렉션을 반복하여 각 요소에 액세스할 수 있지만 그렇게 하는 것이 최적은 아닙니다.

즉, 우리 라이브러리의 경우 세트는 모든 고유 작성자의 컬렉션을 나타내어 특정 작성자가 있는지 빠르게 확인할 수 있습니다.

3. 지도

맵은 각 파일이 서명되고 개별 개체 또는 전체 구조를 저장할 수 있는 파일 캐비닛과 비슷합니다. 맵은 한 값에서 다른 값으로 매핑을 유지해야 하는 경우에 사용해야 합니다.

Map 의 경우 이러한 관계를 키-값 쌍이라고 합니다.

저자 객체를 키로 사용하고 책의 목록( List 객체)을 값으로 사용하여 라이브러리에서 이 구조를 사용할 수 있습니다 . 따라서 저자 개체가 라이브러리에 있는지 확인하기 위해 Set을 확인한 후 동일한 저자 개체를 사용하여 Map 에서 자신의 책 목록을 가져올 수 있습니다 .

4. 대기열

Queue 는 놀라운 컬렉션입니다! — 대기열의 동작을 구현합니다. 그리고 대기열은 LIFO (후입선출) 또는 FIFO (선입선출)일 수 있습니다. 또한 대기열은 양방향 또는 "이중 종단"일 수 있습니다.

이 구조는 클래스에 추가된 개체를 받은 순서대로 사용해야 할 때 유용합니다. 예를 들어 우리 도서관을 이용하십시오.

새로 도착한 방문자를 대기열 에 추가하고 차례로 서비스를 제공하여 그들이 온 책을 발행할 수 있습니다.

보시다시피 이러한 각 구조는 의도된 목적에 맞게 사용된다면 좋습니다. 그리고 단일 라이브러리 예제에서 네 가지 유형의 컬렉션 모두에 대한 좋은 용도를 찾았습니다.

2. 복잡성

이미 언급했듯이 위에서 고려한 컬렉션은 인터페이스이므로 사용하려면 구현이 있어야 합니다.

현미경으로 못을 박는 것이 최선의 아이디어가 아닌 것처럼 컬렉션의 모든 구현이 모든 상황에 적합한 것은 아닙니다.

작업에 적합한 도구를 선택할 때 일반적으로 다음 두 가지 특성을 살펴봅니다.

• 도구가 작업에 얼마나 잘 맞습니까?
• 작업이 얼마나 빨리 완료됩니까?

우리는 작업에 적합한 도구를 선택하는 방법을 알아내는 데 시간을 보냈지만 그 속도는 새로운 것입니다.

컴퓨팅에서 도구의 속도는 종종 시간 복잡도로 표현되며 대문자 O로 표시됩니다.

도대체 시간복잡도가 뭘까요?

간단히 말해서 시간 복잡도는 컬렉션의 알고리즘이 특정 작업(요소 추가/제거, 요소 검색)을 수행하는 데 필요한 시간을 나타냅니다.

ArrayList 대 LinkedList

List 인터페이스 의 두 가지 구현인 ArrayList 및 LinkedList를 사용하여 이를 살펴보겠습니다 .

외관상 이러한 컬렉션 작업은 비슷합니다.

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

보시다시피 두 컬렉션 유형 모두 요소 추가, 가져오기 및 제거가 동일하게 보입니다. 이는 동일한 인터페이스에서 구현되기 때문입니다. 그러나 그것이 유사성이 끝나는 곳입니다.

List 인터페이스 의 서로 다른 구현으로 인해 이 두 구조는 다른 것보다 더 효율적으로 다른 작업을 수행합니다.

요소를 제거하고 추가하는 것을 고려하십시오.

ArrayList 의 중간에서 요소를 제거해야 하는 경우 목록에서 제거한 요소 다음에 오는 부분을 덮어써야 합니다.

5개의 요소 목록이 있고 세 번째 요소를 제거하려고 한다고 가정합니다.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

이 경우 제거로 인해 하나의 셀이 해제되므로 3번째가 있던 곳에 4번째 요소를 작성하고 4번째가 있던 5번째 요소를 작성해야 합니다.

이것은 매우 비효율적입니다.

목록 중간에 요소를 추가할 때도 마찬가지입니다.

LinkedList는 다르게 구성됩니다. 이전 요소와 다음 요소의 참조만 변경하면 되므로 요소 체인에서 제거하려는 개체를 제외하기 때문에 요소를 추가하거나 제거하는 것이 빠릅니다.

동일한 5개 요소 목록의 예로 돌아가서 세 번째 요소를 제거한 후 두 번째 요소의 참조를 다음 요소로 변경하고 네 번째 요소의 참조를 이전 요소로 변경하기만 하면 됩니다.

요소가 목록에 추가되면 동일한 프로세스가 발생하지만 그 반대입니다.

ArrayList 에 비해 LinkedList 에서 해야 할 작업이 얼마나 적은지 확인하십시오 . 그리고 그것은 단지 5개의 요소입니다. 목록에 요소가 100개 이상 있으면 LinkedList 의 우월성이 더욱 두드러질 것입니다.

그러나 인덱스로 요소에 액세스하면 상황이 어떻게 바뀔까요?

여기서는 모든 것이 정반대입니다.

ArrayList는 일반 배열로 구성되어 있으므로 인덱스로 요소를 가져오는 것은 매우 쉽습니다. 단순히 포인터를 특정 위치로 이동하고 해당 셀에서 요소를 가져옵니다.

그러나 LinkedList 는 그런 식으로 작동하지 않습니다. 특정 인덱스가 있는 요소를 찾으려면 목록의 모든 요소를 ​​살펴봐야 합니다.

이 모든 것을 Big O로 표현해볼까요?

인덱스로 요소에 액세스하는 것으로 시작하겠습니다.

ArrayList 에서는 요소가 목록에 있는 위치에 관계없이 한 단계로 발생합니다. 끝이든 시작이든.

이 경우 시간 복잡도는 O(1) 입니다 .

LinkedList 에서 필요한 인덱스 값과 동일한 수의 요소를 반복해야 합니다.

이러한 작업의 시간 복잡도는 O(n) 입니다 . 여기서 n은 필요한 요소의 인덱스입니다.

여기에서 big-O 괄호 안에 넣은 숫자가 수행된 작업의 수에 해당함을 알 수 있습니다.

쉘 제거 및 추가로 돌아갑니까?

LinkedList부터 시작하겠습니다.

요소를 추가하거나 제거하기 위해 많은 수의 작업을 수행할 필요가 없고 이 작업의 속도는 요소가 있는 위치에 전혀 의존하지 않기 때문에 복잡도는 O(1)로 표현 되며 일정하다.

ArrayList 에 대한 이 작업의 시간 복잡도는 선형 복잡도라고 하는 O(n) 입니다 .

선형 복잡성이 있는 알고리즘에서 실행 시간은 처리할 요소의 수에 직접적으로 의존합니다. 또한 목록의 시작 부분에 있는지 또는 끝 부분에 있는지 여부에 따라 요소의 위치에 따라 달라질 수 있습니다.

시간 복잡도는 대수적일 수도 있습니다. 이것은 O(log n) 으로 표현됩니다 .

예를 들어 10개의 숫자로 구성된 정렬된 TreeSet을 고려하십시오. 숫자 2를 찾고 싶습니다.

목록이 정렬되어 있고 중복 항목이 없기 때문에 목록을 반으로 나누고 원하는 숫자가 포함된 절반을 확인하고 관련 없는 부분을 버린 다음 원하는 요소에 도달할 때까지 이 과정을 반복할 수 있습니다. 궁극적으로 log(n) 개의 요소를 처리한 후 숫자를 찾거나 찾지 못할 것입니다.

다음은 컬렉션의 나머지 부분에 대한 시간 복잡도를 요약한 표입니다.

인기 있는 컬렉션의 시간 복잡도를 보여주는 표가 있으므로 많은 컬렉션 중에서 ArrayList , HashSet 및 HashMap 을 가장 자주 사용하는 이유에 대한 답을 얻을 수 있습니다 .

단순히 대부분의 작업에 가장 효율적이라는 것입니다 :)