길의 시작
오늘 저는 " Java 컬렉션 프레임워크 "와 같은 흥미로운 주제, 간단히 말해서 컬렉션에 대해 이야기하고 싶습니다 . 코드 작업의 대부분은 어떤 형태로든 데이터를 처리하는 것입니다. 사용자 목록 가져오기, 주소 목록 가져오기 등 어떻게든 정렬하고, 검색하고, 비교하세요. 이것이 컬렉션에 대한 지식이 핵심 기술로 간주되는 이유입니다. 그래서 나는 그것에 대해 이야기하고 싶습니다. 또한 Java 개발자 인터뷰에서 가장 일반적인 질문 중 하나는 컬렉션입니다. 예를 들어 "컬렉션의 계층 구조를 그립니다." 온라인 컴파일러는 우리가 가는 길에 도움이 될 것입니다. 예를 들어 " Tutorialspoint
Online Java Compiler " 또는
Repl.it을 사용할 수 있습니다. 모든 데이터 구조를 알아가는 길은 일반 변수(변수)부터 시작됩니다. Oracle 웹 사이트에서는 다양한 주제가 "경로" 또는 트레일로 표시됩니다. 그래서 자바를 알아가는 길을 “
트레일: 자바 언어 배우기: 목차 ”라고 합니다. 그리고 언어의 기본(예: 언어 기본)은 변수로 시작됩니다. 따라서 간단한 코드를 작성해 보겠습니다.
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
이 코드는 하나의 변수에 대해서만 훌륭하고 아름답다는 점을 제외하면 모든 면에서 좋습니다. 여러 개가 있으면 어떻게해야합니까? 배열은 한 가지 유형의 데이터를 저장하기 위해 발명되었습니다. Oracle과 동일한 Trail에는 어레이 전용 섹션이 별도로 있습니다.
이 섹션은 " 배열 " 이라고 합니다 . 배열 작업도 매우 간단합니다.
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
배열은 여러 값을 한 곳에 저장하는 문제를 해결합니다. 그러나 여기에는 제한이 있습니다. 배열 크기는 일정합니다. 예에서와 같이 크기 = 2라고 말하면 2와 같습니다. 그게 다야. 더 큰 배열을 원하면 새 인스턴스를 만들어야 합니다. 또한 배열에서는 요소를 찾는 것도 까다로운 일입니다. 방법이 있지만
Arrays.binarySearch이 검색은 정렬된 배열에서만 작동합니다(정렬되지 않은 배열의 경우 결과는 정의되지 않거나 단순히 예측할 수 없습니다). 즉, 검색을 할 때마다 정렬해야 합니다. 삭제하면 값만 지워집니다. 따라서 우리는 여전히 배열에 실제로 얼마나 많은 데이터가 있는지 알지 못하고 배열에 몇 개의 셀이 있는지만 알 수 있습니다. 배열에 대한 지식을 새로 고치려면 다음을 따르세요.
그리고 Java 언어 개발의 결과로 오늘 이야기할 JDK 1.2에 Java Collections Framework가 등장했습니다.
수집
처음부터 비용 계산을 시작하십시오. 왜 컬렉션인가? 용어 자체는 "유형 이론" 및 "추상 데이터 유형"과 같은 것에서 유래되었습니다. 그러나 당신이 어떤 큰 문제도 보지 않는다면, 우리에게 여러 가지가 있을 때 우리는 그것을 '사물의 집합'이라고 부를 수 있습니다. 아이템을 수집하는 사람들. 일반적으로 수집이라는 단어 자체는 Lat에서 유래되었습니다. collectionio "수집, 수집." 즉, 컬렉션은 무언가의 컬렉션, 일부 요소의 컨테이너입니다. 그래서 우리는 요소 모음을 가지고 있습니다. 우리가 할 수 있는 일은 다음과 같습니다.
보시다시피 우리는 꽤 논리적인 것을 원할 수도 있습니다. 또한 우리는 여러 컬렉션으로 무언가를 하고 싶을 수도 있다는 것을 알고 있습니다.
따라서 Java 개발자는 모든 컬렉션에 대한 이러한 일반적인 동작을 설명하기 위해
java.util.Collection 인터페이스를 작성했습니다 . Collection 인터페이스는 모든 컬렉션이 시작되는 곳입니다. 컬렉션은 하나의 아이디어이며 모든 컬렉션이 어떻게 작동해야 하는지에 대한 아이디어입니다. 따라서 컬렉션이라는 용어는 인터페이스로 표현됩니다. 당연히 인터페이스에는 구현이 필요합니다. 인터페이스
java.util.Collection에는 추상 클래스
AbstractCollection, 즉 다른 구현의 뼈대를 나타내는 일부 "추상 컬렉션"이 있습니다(클래스 위의 JavaDoc에 작성된 대로
java.util.AbstractCollection). 컬렉션에 관해 말하면서, 다시 돌아가서 컬렉션을 반복하고 싶다는 점을 기억해 봅시다. 이는 요소를 하나씩 반복하고 싶다는 의미입니다. 이것은 매우 중요한 개념입니다. 따라서 인터페이스는
Collection에서 상속됩니다
Iterable. 이것은 매우 중요합니다. 왜냐면... 첫째, 모든 Iterable은 해당 내용을 기반으로 Iterator를 반환할 수 있어야 합니다. 둘째, Iterable의 모든 항목은 루프에서 사용할 수 있습니다
for-each-loop. 그리고 , , 와
AbstractCollection같은 메소드가 구현되는 것은 반복자의 도움으로 이루어집니다 . 그리고 컬렉션을 이해하는 길은 가장 일반적인 데이터 구조 중 하나인 목록에서 시작됩니다. .
containstoArrayremoveList
기울기
따라서 목록은 컬렉션 계층 구조에서 중요한 위치를 차지합니다.
보시다시피 목록은
java.util.List 인터페이스를 구현합니다 . 목록은 순서대로 배열된 요소 모음을 가지고 있음을 나타냅니다. 각 요소에는 배열과 마찬가지로 인덱스가 있습니다. 일반적으로 목록을 사용하면 동일한 값을 가진 요소를 가질 수 있습니다. 위에서 말했듯이
List요소의 인덱스에 대해 알고 있습니다.
get이를 통해 인덱스별로 요소를 가져오거나( ) 특정 인덱스에 대한 값을 설정할 수 있습니다(
set). 컬렉션 메소드를 사용
add하면
addAll이를
remove실행할 인덱스를 지정할 수 있습니다. 또한 y
List에는 이라는 자체 버전의 반복자가 있습니다
ListIterator. 이 반복자는 요소의 인덱스를 알고 있으므로 앞으로 반복할 뿐만 아니라 뒤로도 반복할 수 있습니다. 컬렉션의 특정 위치에서 생성될 수도 있습니다. 모든 구현 중에서 가장 일반적으로 사용되는 두 가지가 있습니다:
ArrayList및
LinkedList. 먼저 배열( )을 기반으로 한
ArrayList리스트( )이다 .
이를 통해 요소 에 대한 "임의 액세스"를 얻을 수 있습니다 . 랜덤 액세스는 원하는 인덱스가 있는 요소를 찾을 때까지 모든 요소를 반복하는 대신 인덱스별로 요소를 즉시 검색하는 기능입니다. 이를 달성할 수 있는 기반이 바로 어레이입니다. 그에 비해 연결리스트(Linked List)가 있다. 연결된 목록의 각 항목은 데이터 자체와 다음(다음) 및 이전(이전)에 대한 링크를 저장하는 형식으로 표시됩니다 . 따라서 "순차 액세스
" 를 구현합니다 . 5번째 요소를 찾으려면 첫 번째 요소에서 마지막 요소로 이동해야 한다는 것은 분명합니다. 다섯 번째 요소에 직접 액세스할 수는 없습니다. 4번째 요소에서만 접근할 수 있습니다. 개념의 차이점은 다음과 같습니다.
ListArrayLinkedListEntryEntryLinkedList
아시다시피 직장에서도 차이가 있습니다. 예를 들어 요소를 추가합니다. 요소
LinkedList는 단순히 체인의 링크처럼 연결됩니다. 그러나
ArrayList요소를 배열에 저장합니다. 그리고 우리가 알고 있듯이 배열은 크기를 변경할 수 없습니다. 그러면 어떻게 작동하나요
ArrayList? 그리고 그것은 매우 간단하게 작동합니다. 배열의 공간이 부족해지면 1.5배로 늘어납니다. 확대/축소 코드는 다음과 같습니다.
int newCapacity = oldCapacity + (oldCapacity >> 1); 작동의 또 다른 차이점은 요소의 변위입니다. 예를 들어 중간에 요소를 추가하거나 제거하는 경우입니다.
LinkedList요소 에서 제거하려면 해당 요소에 대한 참조를 제거하면 됩니다. 의 경우
ArrayList를 사용할 때마다 요소를 이동해야 합니다
System.arraycopy. 따라서 요소가 많을수록 더 많은 작업을 수행해야 합니다. 더 자세한 설명은 다음 문서에서 확인할 수 있습니다.
ArrayList를 조사한 후에는 "전임자"인 java.util.Vector 클래스 를 기억하지 않을 수 없습니다 . 컬렉션 작업 방법(추가, 삭제 등)이 동기화된다는 점
Vector에서 다릅니다 .
ArrayList즉, 하나의 스레드(
Thread)가 요소를 추가하면 다른 스레드는 첫 번째 스레드가 작업을 마칠 때까지 기다립니다.
ArrayList스레드 안전성이 요구되지 않는 경우가 많기 때문에 해당 클래스에 대한 JavaDoc에 명시적으로 명시된 대로 이러한 경우에는 클래스를 사용하는 것이 좋습니다
Vector. 또한
Vector크기가 1.5배가 아닌
ArrayList2배로 증가합니다. 그렇지 않으면 동작은 동일합니다. 즉,
Vector배열 형태의 요소 저장이 숨겨지고 요소 추가/제거는 에서와 동일한 결과를 가져옵니다
ArrayList. 사실
Vector우리가 이것을 기억한 데에는 이유가 있었습니다. Javadoc을 살펴보면 "직접 알려진 하위 클래스"에서
java.util.Stack 과 같은 구조를 볼 수 있습니다 . 스택은 LIFO
last-in-first-out(후입선출) 구조인 흥미로운 구조입니다. 영어로 번역된 스택은 스택(예: 책 더미와 같은)입니다. 스택은
peek(look, view),
pop(push),
push(push)와 같은 추가 메서드를 구현합니다. 이 메소드는
peek보기로 번역됩니다(예를 들어
가방 내부를 엿보는 것은 " 가방 내부를 들여다보기 " 로 번역되고 ,
열쇠 구멍을 통해 엿보는 것은 " 열쇠 구멍을 통해 엿보기 " 로 번역됩니다 ). 이 방법을 사용하면 스택의 "상단"을 볼 수 있습니다. 스택에서 마지막 요소를 제거하지 않고(즉, 제거하지 않고) 가져옵니다. 메서드는
push새 요소를 스택에 푸시(추가)하고 반환하며, 요소 메서드는
pop제거된 요소를 푸시(제거)하고 반환합니다. 세 가지 경우(예: peek, pop 및 push) 모두 마지막 요소(예: "스택의 최상위")에서만 작업합니다. 이것이 스택 구조의 주요 특징입니다. 그런데 "A Programmer's Career"(Cracking Coding Interview)라는 책에 설명된 스택을 이해하는 흥미로운 작업이 있습니다. "스택" 구조(LIFO)를 사용하여 "큐"를 구현해야 하는 흥미로운 작업이 있습니다. ” 구조(FIFO). 다음과 같아야 합니다.
이 작업에 대한 분석은 "
스택을 사용하여 큐 구현 - 큐 ADT(LeetCode의 "스택을 사용하여 큐 구현") "에서 찾을 수 있습니다. 그래서 우리는 새로운 데이터 구조인 큐로 원활하게 이동합니다.
대기줄
대기열은 우리 삶에서 친숙한 구조입니다. 상점, 의사에게 줄을 서세요. 먼저 온 사람(선입)이 가장 먼저 대기열에서 나옵니다(선출). Java에서 대기열은
java.util.Queue 인터페이스로 표시됩니다 . 대기열의 Javadoc에 따르면 대기열은 다음 메서드를 추가합니다.
보시다시피 주문 방법(실행하지 못하면 예외가 발생함)과 요청 방법(실행할 수 없어도 오류가 발생하지 않음)이 있습니다. 요소를 제거하지 않고 요소를 가져오는 것도 가능합니다(Peek 또는 요소). 큐 인터페이스에는 유용한 후속 인터페이스인
Deque 도 있습니다 . 이것이 소위 "양방향 대기열"입니다. 즉, 이러한 큐를 사용하면 이 구조를 처음부터 끝까지 사용할 수 있습니다. 문서에는 "Deques를 LIFO(Last-In-First-Out) 스택으로 사용할 수도 있습니다. 이 인터페이스는 레거시 Stack 클래스보다 우선적으로 사용해야 합니다."라고 나와 있습니다. 즉, 대신 Deque 구현을 사용하는 것이 좋습니다. 스택. Javadoc은 Deque 인터페이스가 설명하는 메소드를 보여줍니다.
어떤 구현이 있는지 살펴보겠습니다. 그리고 우리는 흥미로운 사실을 보게 될 것입니다 - LinkedList가 대기열 진영에 들어갔습니다. 즉, LinkedList는
List, 및 를 모두 구현합니다
Deque. 그러나 예를 들어 "대기열만"도 있습니다
PriorityQueue. 그녀는 자주 기억되지 않지만 헛된 것입니다. 첫째, 이 대기열에서는 "비교할 수 없는 개체"를 사용할 수 없습니다. 비교기를 지정하거나 모든 객체를 비교할 수 있어야 합니다. 둘째, "이 구현은 대기열에 넣기와 대기열에서 빼기 방법에 O(log(n)) 시간을 제공합니다." 대수적 복잡성에는 이유가 있습니다. 힙을 기반으로 PriorityQueue를 구현했습니다. Javadoc에서는 "균형 잡힌 바이너리 힙으로 표현되는 우선순위 큐"라고 말합니다. 이에 대한 저장소 자체는 일반 배열입니다. 필요할 때 자랍니다. 힙이 작으면 2배로 증가합니다. 그리고 50%씩. 코드의 설명: "작으면 두 배 크기, 그렇지 않으면 50% 증가". 우선순위 큐와 바이너리 힙은 별도의 주제입니다. 자세한 내용은 다음을 참조하세요.
구현으로
java.util.ArrayDequejava.util.Deque 클래스를 사용할 수 있습니다 . 즉, 리스트는 연결리스트와 배열을 이용하여 구현할 수 있고, 큐는 배열이나 연결리스트를 이용하여 구현할 수도 있다. 및 인터페이스에는 "차단 대기열"을 나타내는 하위 항목이 있습니다 . 일반 대기열과 비교한 인터페이스 변경 사항은 다음과 같습니다.
QueueDequeBlockingQueueBlockingDeque
차단 대기열의 몇 가지 예를 살펴보겠습니다. 그러나 그들은 흥미있다.
예를 들어 BlockingQueue는 PriorityBlockingQueue ,
동기 큐 , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue 에 의해 구현됩니다 . 그러나
BlockingDeque그들은 표준 컬렉션 프레임워크의 모든 것을 구현합니다
LinkedBlockingDeque. 각 대기열은 별도의 검토 주제입니다. 그리고 이 검토의 프레임워크 내에서 우리는 클래스 계층 구조를 뿐만 아니라
List다음과 함께 묘사할 것입니다
Queue.
다이어그램에서 볼 수 있듯이 Java 컬렉션 프레임워크의 인터페이스와 클래스는 서로 밀접하게 얽혀 있습니다. 계층 구조의 또 다른 분기를 추가해 보겠습니다
Set.
세트
Set— "세트"로 번역됩니다.
Set요소 저장에 대한 추상화 측면 에서 큐 및 목록과 다릅니다.
Set- 물건이 담긴 가방처럼, 물건이 어떻게 위치하는지, 어떤 순서로 놓여 있는지 알 수 없습니다. Java에서 이러한 세트는
java.util.Set 인터페이스로 표시됩니다 . 문서에 따르면
Set이는 "중복 요소를 포함하지 않는 컬렉션"입니다. 흥미롭게도 인터페이스 자체는
Set인터페이스에 새로운 메소드를 추가하지 않고
Collection요구사항(중복을 포함해서는 안 되는 사항에 대한)만 명확하게 합니다. 또한 이전 설명에서 단순히
Set요소를 가져올 수는 없습니다. Iterator는 요소를 가져오는 데 사용됩니다.
Set이와 관련된 여러 인터페이스가 더 있습니다. 첫 번째는 입니다
SortedSet. 이름에서 알 수 있듯이
SortedSet이러한 세트가 정렬되어 있으므로 요소가 인터페이스를 구현하거나
Comparable지정됨을 나타냅니다
Comparator. 또한 다음과 같은
SortedSet몇 가지 흥미로운 방법을 제공합니다.
first그 밖에도 메소드 (값 기준으로 가장 작은 요소)와 (값 기준으로 가장 큰 요소) 가 있습니다
last.
SortedSet상속인이 있습니다 -
NavigableSet. 이 인터페이스의 목적은 적절한 요소를 보다 정확하게 식별하는 데 필요한 탐색 방법을 설명하는 것입니다. 흥미로운 점은
NavigableSet일반적인 반복자(가장 작은 것부터 큰 것까지)에 역순으로 반복자를 추가한다는 것 입니다
descendingIterator. 또한 요소가 역순으로 표시된 자신의 보기(View)를 얻는
NavigableSet방법을 사용할 수 있습니다 . 결과 요소를 통해 원본 요소를 변경할 수 있기 때문에
descendingSet이를 호출합니다 . 즉, 본질적으로 원본 데이터를 다른 방식으로 표현한 것이지 복사본이 아닙니다. 흥미롭게 도 는 (최소) 및 (최대) 요소를 처리할 수 있습니다 . 즉, 이 요소를 가져와서 세트에서 제거합니다. 어떤 종류의 구현이 있나요? 첫째, 가장 유명한 구현은 해시 코드인
HashSet을 기반으로 합니다 . 똑같이 잘 알려진 또 다른 구현은 레드-블랙 트리(
TreeSet )를 기반으로 합니다 . 다이어그램을 완성해 보겠습니다.
ViewSetNavigableSetQueuepollFirstpollLast
컬렉션 내에서는 계층 구조, 즉 은둔자를 분류하는 것이 남아 있습니다. 언뜻보기에는 제쳐두고 있습니다
java.util.Map.
지도
맵은 데이터가 키로 저장되는 데이터 구조입니다. 예를 들어 키는 ID 또는 도시 코드일 수 있습니다. 그리고 이 키를 사용하여 데이터가 검색됩니다. 카드가 따로 표시되어 있다는 점이 흥미롭습니다. 개발자에 따르면("
Java 컬렉션 API 디자인 FAQ " 참조) 키-값 매핑은 컬렉션이 아닙니다. 그리고 맵은 키 모음, 값 모음, 키-값 쌍 모음으로 더 빨리 생각할 수 있습니다. 이것은 정말 흥미로운 동물입니다. 카드는 어떤 방법을 제공하나요?
Java API 인터페이스 java.util.Map을 살펴보겠습니다 . 왜냐하면 맵은 컬렉션이 아니기 때문에(컬렉션에서 상속되지 않음)
contains. 그리고 이것은 논리적입니다. 맵은 키와 값으로 구성됩니다. 메소드는 다음 중 무엇을 확인해야 하며
contains혼동하지 않는 방법은 무엇입니까? 따라서 인터페이스에는 (키 포함)과 (값 포함)
Map의 두 가지 버전이 있습니다 . 이를 사용하면 일련의 키(동일한 키)를 얻을 수 있습니다 . 그리고 이 메서드를 사용하면 맵에서 값 모음을 얻을 수 있습니다. 맵의 키는 고유하며 이는 데이터 구조에서 강조됩니다 . 값은 반복될 수 있으며 이는 컬렉션 데이터 구조에서 강조됩니다. 또한 이 방법을 사용하면 키-값 쌍 세트를 얻을 수 있습니다. 가장 자세한 분석에서 어떤 카드 구현이 있는지 자세히 알아볼 수 있습니다.
containsKeycontainsValuekeySetSetvaluesSetentrySet
나는 또한 , 와
HashMap매우 유사한 것이 무엇인지 보고 싶습니다 . 심지어 유사한 인터페이스도 있습니다: 및 , 및 . 따라서 최종 지도는 다음과 같습니다.
HashSetTreeMapTreeSetNavigableSetNavigableMapSortedSetSortedMap
컬렉션이
Set내부적으로 를 사용한다는 흥미로운 사실로 마무리할 수 있습니다
Map. 여기서 추가된 값은 키이고 값은 어디에서나 동일합니다. 이는 컬렉션이 아니지만 실제로는 로 구현되는 컬렉션
Map및 반환 이라는 점에서 흥미롭습니다 . 조금 초현실적이지만 결과는 그랬습니다)
SetMap
결론
좋은 소식은 이번 리뷰가 여기서 끝난다는 것입니다. 나쁜 소식은 이것이 매우 리뷰 기사라는 것입니다. 각 컬렉션의 각 구현은 별도의 기사가 필요하며 우리 눈에 숨겨진 각 알고리즘에 대해서도 마찬가지입니다. 하지만 이 검토의 목적은 인터페이스가 무엇인지, 인터페이스 간의 연결이 무엇인지 기억하는 것입니다. 신중하게 읽은 후에는 기억에서 컬렉션 다이어그램을 그릴 수 있기를 바랍니다.
음, 평소와 같이 일부 링크는 다음과 같습니다.
#비아체슬라프
GO TO FULL VERSION