Java 초보자를 위한 필수 치트 시트

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

List

ArrayList

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

배열 첨자로 요소에 액세스 – get(i)/set(i,e)는 배열의 기본 장점인 높은 성능을 제공합니다.

배열의 끝 부분에 요소를 직접 추가하는 성능 –add(e)도 높지만, 첨자 –add(i,e), 제거(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로 설정되면 모든 읽기 및 쓰기 액세스가 계산됩니다).

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

TreeMap

은 red-black 트리로 구현되며, iterator()가 지원되면 Comparable 인터페이스를 구현한 Key 값을 기준으로 오름차순으로 정렬할 수 있습니다. 또는 들어오는 비교기에 의해 제어됩니다. 트리에 요소를 삽입/삭제하는 데 드는 비용은 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이고 값은 모두 동일한 개체를 사용하는 거짓 값이기 때문입니다. 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())을 직접 사용합니다.

큐

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

–일반 대기열–

LinkedList

예, 이중 연결 목록으로 구현된 LinkedList는 목록이자 대기열입니다. Null 배치를 허용하는 유일한 대기열입니다.

ArrayDeque

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

일반 배열은 FIFO를 지원하고 배열의 헤드에서 요소를 빠르게 제거하기 위해 빠르게 요소를 추가할 수 있으며 루프 배열을 사용해야 합니다. 헤드와 테일에 두 개의 첨자가 있습니다. : 요소를 팝할 때 헤드는 헤드 아래에 있습니다. 요소를 추가할 때 인덱스가 증가하고 배열 공간의 끝에 도달하면 해당 요소는 순환적으로 배열 0에 할당되고 꼬리 첨자는 0을 가리킵니다. 다음 요소가 삽입되고 배열 [1]에 할당되며 꼬리 첨자는 1을 가리킵니다. 큐 끝에 있는 첨자가 큐의 헤드를 따라잡는 경우 이는 배열의 모든 공간이 사용되었으며 배열이 두 배로 늘어난다는 의미입니다.

PriorityQueue

바이너리 힙을 사용하여 구현된 우선순위 큐는 더 이상 FIFO가 아니지만 요소에 의해 구현된 Comparable 인터페이스 또는 Comparator에 전달된 비교 결과를 기반으로 큐에서 제거됩니다. 값, 우선 순위가 높을수록 더 일찍 대기열에서 제거됩니다. 그러나 iterator()의 반환은 정렬되지 않습니다.

–스레드 안전 큐–

ConcurrentLinkedQueue/ConcurrentLinkedDeque

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

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

PriorityBlockingQueue

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

DelayQueue

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

– 스레드로부터 안전한 차단 대기열 –

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

ArrayBlockingQueue

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

LinkedBlockingQueue/LinkedBlockingDeque

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

보충제

JDK7에는 LinkedTransferQueue가 있습니다. transfer(e) 메소드는 생산자가 넣은 요소를 소비자가 가져간 다음 시간이 있을 때 배워야 합니다.