Java 컬렉션을 위한 치트 시트 Java 초보자를 위한 필수 자료

모든 컬렉션과 동시 컬렉션의 특성, 구현 방법, 성능을 최대한 짧은 시간에 검토합니다. "Java에 능숙하다"는 데 그다지 자신이 없는 모든 사람이 읽기에 적합합니다.

List

ArrayList

배열로 구현됩니다. 공간을 절약하지만 어레이에는 용량 제한이 있습니다. 한도를 초과하면 용량이 50% 증가하고 System.arraycopy()를 사용하여 새 어레이에 복사되므로 어레이 크기를 추정하는 것이 가장 좋습니다. 기본적으로 요소가 처음 삽입될 때 크기 10의 배열이 생성됩니다.

배열 첨자-get(i)/set(i,e)로 요소에 액세스하면 성능이 뛰어나며 이는 배열의 기본 장점입니다.

배열의 끝 부분에 직접 요소를 추가하는 add(e)의 성능도 높지만, 아래 첨자를 눌러 요소를 삽입하고 삭제하는 경우 --add(i,e), Remove( i), 제거(e) , 영향을 받은 요소 중 일부를 이동하려면 System.arraycopy()를 사용해야 하며 이는 성능이 더욱 저하됩니다.

LinkedList

는 양방향 연결리스트로 구현되었습니다. 연결된 목록에는 용량 제한이 없지만 이중 연결 목록 자체는 더 많은 공간을 사용하고 추가 연결 목록 포인터 작업이 필요합니다.

첨자-get(i)/set(i,e)로 요소에 액세스하면 포인터를 제자리로 이동하기 위해 연결 목록을 비극적으로 순회하게 됩니다(i>배열 크기의 절반이면 이동됩니다). 끝부터).

요소를 삽입하거나 삭제할 때 이전 노드와 다음 노드의 포인터만 수정할 수 있지만, 첨자가 가리키는 위치로 이동하려면 여전히 연결 리스트 포인터의 일부를 순회해야 합니다. 연결된 목록의 양쪽 끝 - add(), addFirst(), RemoveLast() 또는 iterator()에서 제거()를 사용하여 포인터 이동을 저장합니다.

CopyOnWriteArrayList

동시성에 최적화된 ArrayList. CopyOnWrite 전략을 사용하여 먼저 스냅샷을 복사하여 수정한 다음 내부 포인터가 수정 후 새 배열을 가리키도록 합니다.

스냅샷 수정은 읽기 작업에서 보이지 않기 때문에 쓰기 잠금만 있고 읽기 잠금은 없습니다. 또한 복제 비용이 많이 들 뿐만 아니라 일반적으로 읽기는 많고 쓰기는 적은 시나리오에 적합합니다. . 업데이트 빈도가 높거나 배열이 큰 경우 Collections.synchronizedList(list)를 사용하고 모든 작업에 동일한 잠금을 사용하여 스레드 안전성을 보장하는 것이 좋습니다.

배열을 순회하여 요소가 이미 존재하는지 확인하는 addIfAbsent(e) 메서드를 추가했습니다. 성능은 상상할 수 있는 것만큼 좋지 않습니다.

보충

어떤 구현을 사용하든 상관없이 값(contains(e), indexOf(e), Remove(e))으로 아래 첨자를 반환하려면 비교를 위해 모든 요소를 ​​순회해야 하며 성능은 상상할 수 있지만 그다지 좋지는 않을 것입니다.

요소 값으로 정렬된 SortedList가 없으며 스레드 안전 클래스에 잠금이 없는 ConcurrentLinkedList가 없습니다. Set 및 Queue에서 동등한 클래스를 사용하면 일부 목록 관련 항목이 부족해집니다. 행동 양식.

Map

HashMap

Entry[] 배열로 구현된 해시 버킷 배열입니다. 배열 첨자는 해시 값을 사용하여 버킷 배열의 크기를 모듈로로 얻을 수 있습니다. 열쇠의.

요소를 삽입할 때 두 개의 키가 동일한 버킷에 속하는 경우(예: 해시 값 1과 17이 모듈로 16 이후 첫 번째 해시 버킷에 속함) Entry는 다음 속성을 사용하여 여러 키를 구현합니다. 단방향 연결 목록에 저장된 항목, 버킷에 나중에 입력된 항목은 버킷의 현재 항목 옆을 가리킵니다.

해시 값이 17인 키를 찾을 때 먼저 첫 번째 해시 버킷을 찾은 다음 연결 목록을 사용하여 버킷의 모든 요소를 ​​순회하고 키 값을 하나씩 비교합니다.

Entry 수가 버킷 수의 75%에 도달하면(많은 기사에서 사용된 버킷 수가 75%에 도달했다고 말하지만 코드에 따르면 사실이 아님) 버킷 배열이 확장됩니다. 기하급수적으로 모든 원본 항목이 재할당되므로 여기서 추정하는 것이 가장 좋습니다.

모듈러스를 가져오는 데 비트 연산(hash & (arrayLength-1))을 사용하는 것이 더 빠르므로 배열의 크기는 항상 2의 N승입니다. 17이면 32로 변환됩니다. 요소가 처음 배치될 때 기본 초기 값은 16입니다.

Iterator()는 순서가 잘못된 것으로 보이는 해시 버킷 배열을 따라 순회합니다.

JDK8에는 기본값이 8인 새 임계값이 추가됩니다. 버킷의 항목이 임계값을 초과하면 단방향 연결 목록에 저장되지 않고 레드-블랙 트리에 저장됩니다. 키 검색 속도를 높이려면

LinkedHashMap

HashMap을 확장하여 메모리를 가장 많이 소모하는 데이터 구조로 알려진 이중 연결 목록의 구현을 추가합니다. iterator()가 지원되면 항목은 삽입 순서에 따라 정렬됩니다(그러나 업데이트는 계산되지 않습니다. accessOrder 속성이 true로 설정되면 모든 읽기 및 쓰기 액세스가 계산됩니다).

항목에 포인터 앞/뒤에 속성을 추가하고 삽입 시 헤더 항목 앞에 자신을 추가하는 방식으로 구현됩니다. 모든 읽기 및 쓰기 액세스를 정렬해야 하는 경우 앞/뒤 항목의 앞/뒤를 함께 연결하여 연결 목록에서 삭제해야 합니다.

트리맵

공간적 제약으로 인해 자세한 내용은 입문 튜토리얼을 참조하세요. iterator()가 지원되면 정렬은 키 값을 기준으로 이루어지며, 이는 Comparable 인터페이스를 구현하는 키의 오름차순으로 정렬되거나 들어오는 Comparator에 의해 제어될 수 있습니다. 트리에 요소를 삽입/삭제하는 데 드는 비용은 HashMap의 비용보다 커야 한다고 생각할 수 있습니다.

가장 큰 키와 가장 작은 키를 얻기 위한 firstKey(), lastKey() 또는 맵의 특정 세그먼트를 잘라내는 sub(fromKey, toKey), tailMap(fromKey)와 같은 SortedMap 인터페이스를 지원합니다.

ConcurrentHashMap

동시 최적화된 HashMap에는 기본적으로 16개의 쓰기 잠금이 있으며(더 많이 설정할 수 있음) 차단 가능성을 효과적으로 분산시키고 읽기 잠금이 없습니다.

데이터 구조는 Segment[]입니다. Segment 내부에는 해시 버킷 배열이 있으며 각 Segment에는 잠금이 있습니다. Key는 먼저 해당 세그먼트가 어느 세그먼트에 있는지 계산한 다음 어느 해시 버킷에 있는지 계산합니다.

putIfAbsent(key, value)와 반대되는 CAS를 구현하는 교체(key, value) 및 교체(key, oldValue, newValue)와 같은 ConcurrentMap 인터페이스를 지원합니다.

넣기/제거 작업은 원자적 작업이므로 읽기 잠금이 없으며(예: 넣기는 배열 요소/항목 포인터에 대한 할당 작업) 읽기 작업에서는 중간 상태를 볼 수 없습니다. 업데이트 작업.

ConcurrentSkipListMap

JDK6의 새로운 동시성 최적화 SortedMap은 SkipList로 구현됩니다. SkipList는 레드-블랙 트리에 대한 단순화된 대안이며 공간 제한으로 인해 소개 튜토리얼을 참조하십시오. Concurrent 패키지는 CAS 기반 잠금 없는 알고리즘을 지원하기 때문에 이를 사용하는 반면, 레드-블랙 트리에는 좋은 잠금 없는 알고리즘이 없습니다.

매우 특별합니다. 크기()는 임의로 조정할 수 없으며 통계를 위해 순회됩니다.

보충

null의 경우 HashMap 및 LinkedHashMap은 임의적입니다. TreeMap이 Comparator를 설정하지 않은 경우 키는 null이 될 수 없습니다. JDK7에서는 ConcurrentHashMap의 값이 null이 될 수 없습니다. , JDK8 ConcurrentSkipListMap의 키와 값은 모두 null이 될 수 없습니다. ConcurrentSkipListMap에서는 JDK의 모든 키와 값이 null이 될 수 없습니다.

Set

Set은 거의 항상 Map을 사용하여 내부적으로 구현됩니다. 왜냐하면 Map의 KeySet은 Set이고 값은 false 값이며 모두 동일한 객체를 사용하기 때문입니다. Set의 특성은 내부 Map 구현의 특성도 상속합니다.

HashSet: 내부적으로 HashMap입니다.

LinkedHashSet: 내부적으로는 LinkedHashMap입니다.

TreeSet: 내부적으로 TreeMap의 SortedSet입니다.

ConcurrentSkipListSet: 내부적으로 ConcurrentSkipListMap의 동시성에 최적화된 SortedSet입니다.

CopyOnWriteArraySet: 내부적으로는 동시성이 최적화된 CopyOnWriteArrayList 집합입니다. 해당 addIfAbsent() 메서드는 위에서 언급한 것처럼 요소 중복 제거를 달성하는 데 사용됩니다.

보충: ConcurrentHashSet이 누락된 것 같습니다. 내부적으로 ConcurrentHashMap을 간단하게 구현해야 하는데 JDK에서는 이를 제공하지 않습니다. Jetty는 자체적으로 하나를 봉인했으며 Guava는 이를 구현하기 위해 java.util.Collections.newSetFromMap(new ConcurrentHashMap())을 직접 사용합니다.

Queue

Queue는 양쪽 끝에서 들어오고 나가는 List이므로 배열이나 연결리스트로도 구현할 수 있습니다.

　--일반 큐--

　LinkedList

　예, 이중 연결 리스트로 구현된 LinkedList는 List이자 Queue입니다. Null 배치를 허용하는 유일한 대기열입니다.

　ArrayDeque

　 원형 배열로 구현된 양방향 Queue입니다. 크기는 2의 배수이고 기본값은 16입니다.

일반 배열은 FIFO를 지원하고 배열의 헤드에서 요소를 빠르게 제거하려면 끝에 요소를 빠르게 추가할 수 있으며 루프 배열을 사용해야 합니다. 헤드와 테일에 두 개의 첨자가 있습니다. : 요소를 팝할 때 헤드는 다음과 같습니다. 요소를 추가할 때 아래 첨자가 증가합니다. 요소가 배열 공간의 끝에 도달하면 해당 요소는 루프에서 배열 [0]에 할당됩니다. 이때 팀의 선두가 0보다 크다는 것은 팀의 선두에 요소가 튀어나와 공석이 생겼다는 뜻이다.) 동시에 팀의 꼬리는 0을 가리킨다. 다음 요소가 삽입되면 배열 [1]에 할당되고 꼬리 첨자는 1을 가리킵니다. 큐 끝에 있는 첨자가 큐의 헤드를 따라잡는 경우 이는 배열의 모든 공간이 사용되었으며 배열이 두 배로 늘어난다는 의미입니다.

PriorityQueue

바이너리 힙을 사용하여 구현된 우선순위 큐. 자세한 내용은 입문 튜토리얼을 참조하세요. 더 이상 FIFO가 아니지만 요소 또는 비교 결과에 의해 구현된 Comparable 인터페이스를 기반으로 큐에서 제거됩니다. Comparator 에 전달되면 값이 작을수록 우선순위가 높아지고 가장 먼저 대기열에서 제거됩니다. 그러나 iterator()의 반환은 정렬되지 않습니다.

　--스레드 안전 큐--

　ConcurrentLinkedQueue/ConcurrentLinkedDeque

　연결된 목록을 기반으로 하는 무제한 동시성 최적화 큐는 CAS에 의존하는 잠금 없는 알고리즘을 구현합니다.

ConcurrentLinkedQueue의 구조는 단방향 연결 목록과 두 개의 포인터(head/tail)입니다. 왜냐하면 대기열에 합류할 때 대기열의 tail 요소의 다음 포인터를 수정하고 tail이 가리키는 항목을 수정해야 하기 때문입니다. 새로 결합된 요소 두 개는 원자적일 수 없으므로 특별한 알고리즘이 필요합니다. 공간 제한으로 인해 소개 튜토리얼을 참조하세요.

　PriorityBlockingQueue

　 무제한 동시성에 최적화된 PriorityQueue도 바이너리 힙을 기반으로 합니다. 공개 읽기-쓰기 잠금을 사용합니다. BlockingQueue 인터페이스는 구현되었지만 차단 대기열 특성은 없습니다. 공간이 부족할 경우 자동으로 확장됩니다.

DelayQueue

내부적으로 무한한 PriorityQueue를 포함합니다. 요소는 Delayed 인터페이스를 구현해야 하며 호출될 때마다 트리거 시간 이전의 시간을 반환해야 합니다. 0보다 작으면 트리거할 시간이라는 의미입니다.
pull()할 때 peek()를 사용하여 큐의 헤드에 있는 요소를 확인하여 트리거 시간에 도달했는지 확인합니다. ScheduledThreadPoolExecutor는 비슷한 구조를 사용합니다.

　--스레드로부터 안전한 차단 큐--

　 BlockingQueue의 큐 길이는 생산자와 소비자의 속도가 너무 멀지 않아 메모리 소모를 방지하도록 제한됩니다. 대기열 길이는 설정된 후에는 변경할 수 없습니다. 대기열에 들어갈 때 대기열이 가득 차거나 대기열에서 나갈 때 대기열이 비어 있는 경우 다양한 기능의 효과가 아래 표에 표시됩니다.

예외를 보고할 수 있음 부울 값 반환 대기를 차단할 수 있음 대기 시간 설정 가능

Enqueue add(e) Offer(e) put(e) Offer(e, timeout, unit)

Dequeue Remove() poll() take() poll( 시간 초과, 단위)

View element() peek() 없음 없음

ArrayBlockingQueue

루프 배열을 기반으로 구현된 고정 길이 동시 최적화 BlockingQueue. 대기열이 가득 찼거나 비어 있을 때 차단 상태를 관리하기 위한 일반적인 읽기-쓰기 잠금과 notFull 및 notEmpty라는 두 가지 조건이 있습니다.

LinkedBlockingQueue/LinkedBlockingDeque

연결된 목록을 기반으로 하는 긴 동시성 최적화 BlockingQueue를 선택할 수 있으므로 길이를 Integer.MAX_VALUE로 설정할 수 있습니다. Linked List의 특성을 살려 takeLock과 putLock 두 개의 잠금을 분리하고, notEmpty와 notFull을 사용하여 대기열이 가득 차거나 비어 있을 때에도 계속해서 차단 상태를 관리합니다.

보충

JDK7에는 LinkedTransferQueue가 있습니다. transfer(e) 메소드는 생산자가 넣은 요소를 제거하고 소비자가 반환하는 것을 보장합니다. 시간이 있을 때 배워보세요.