Java 데이터 구조

인터페이스 목록

이 인터페이스는 가장 자주 사용하는 두 가지 실현이 있다. 바로 Array List와 Linked List이다.우리 는 하나하나 를 깊이 있게 이해합시다

패턴 목록

이 구조의 이름에서 우리는 내부에서 간단한 수조를 사용하는 것을 알게 되었다.
그러나 이런 구조는 동적 사이즈를 가지고 있다.ensureCapacity() 방법은 사용하는 간단한 그룹을 증가시킬 수 있습니다.이 방법이 호출될 때, 사용되는 그룹의 불러오는 상황을 검사합니다. 필요하면 현재 + 현재 60%와 같은 용량의 새 그룹을 만듭니다.System.arraycopy 방법을 호출함으로써 우리는 모든 요소를 낡은 그룹에서 새 그룹으로 복사합니다.우리는 간단한 수조가 있기 때문에 원소를 얻고 삭제하는 데는 O(1)-항정 시간이 필요하다.색인에 따라 검색하려면 모든 그룹을 훑어봐야 하기 때문에 O (n) 개의 작업이 필요합니다.

체인 미터

이 구조는 목록에서 다음 및 이전 객체에 대한 링크가 있는 객체를 기반으로 합니다.이 구조는 Array List의 장점 중 하나일 뿐입니다. 즉, 시작할 때 삽입하는 것이 Array List에서 실행하는 것보다 빠릅니다.그래서 이런 구조는 어떤 임무에 적합할 수 있지만, 나는 이런 임무를 만난 적이 없다.

창고

이런 구조는 우리에게 다음 방법인 밀어내기, 팝업, 투표를 제공했다.그 밖에 후진 선출, 즉 후진 선출을 실시한다.예를 들어 만약에 우리가 창고 요소 102123을 팝이나 롤을 호출하면 123을 얻을 수 있다.하지만 팝업은 스택에서 123을 삭제합니다.폴링은 스택에서 요소를 삭제하지 않습니다.내부에서, 그것은 간단한 그룹을 사용한다.

인터페이스 세트

이 데이터 구조는 유일한 요소를 저장하기 위해서만 생성됩니다.집합에 원소가 포함되지 않았는지 어떻게 검사합니까?이를 위해, 우리는 약간의 실현이 있다.얘기 좀 하자.첫 번째 해시 집합은 대상에서 equals를 호출하여 요소를 비교합니다.두 번째 트리 집합은 비교 인터페이스를 실현할 수 있는 요소만 저장하거나 구조 함수를 통해 트리 집합에 비교기를 제공해야 한다.

해시집

내부에 HashMap을 사용하면 유일한 키만 저장할 수 있습니다.이런 구조는 삽입 순서를 보장할 수 없다. 이것은 우리가 삽입 순서의 다른 순서에서 요소를 얻는 것을 의미한다.이렇게 하면 추가, 삭제, 포함, 크기 등 일정한 기본 작업 시간이 있습니다.그것은 일정한 시간을 실행하는 해시 함수에 의해 제공된다.

순차 트리

HashSet이 HashMap을 기반으로 하면 TreeSet이 TreeMap을 기반으로 합니다.이 데이터 구조는 추가, 삭제, 포함 등 작업의 시간 O (log (n) 를 보장합니다.트리 매핑이 트리를 사용하기 때문입니다.이 시리즈는 자연 주문을 보증합니다.예:

Set numbers = new TreeSet<>();

numbers.add(2);

numbers.add(1);

for(Integer number : numbers) { System.out.println(number);} 

콘솔에서 인쇄

1
2

LinkedHashSet

이 집합은next로 유명합니다. - 이전의 실현과 달리 삽입 순서를 보장합니다.따라서 이 데이터 구조를 교체하면 요소의 삽입 순서를 볼 수 있습니다.이전 set 구현과 마찬가지로 내부에서 LinkedHashMap을 사용합니다.우리가 원소를 추가하려고 시도할 때,alredy는 그것을 집합에 추가합니다. - 이 작업은 원소의 순서에 영향을 주지 않습니다.기본 작업의 경우 작업을 추가, 삭제 및 포함하는 연속 시간 O(n)를 제공합니다.빈 요소를 포함할 수 있습니다.이 집합의 성능에 대해 두 개의 변수인 initial Capacity와loadFactor를 사용합니다.먼저 내부에서 사용하는 맵의 초기 용량을 설명한 다음에 맵의 메모리 통 사용 수를 늘려야 하는 시기를 설명합니다.

매거집

이 실현은 매거 유형을 위한 것입니다.이 메서드에 EnumSet 인스턴스가 전달되면 containsAll, retainAll 같은 대규모 작업의 실행 속도가 빨라집니다.이 집합이 교체될 때, 원소의 자연 순서를 볼 수 있습니다.반환된 교체기가 ConcurrentModificationException을 내보내지 않았습니다.이 밖에 교체기는 수정을 표시할 수도 있고 수정을 표시하지 않을 수도 있다.연속된 시간에 수행되는 모든 기본 작업

NavigableSet 회사

이런 실현에는 집합에서 내비게이션을 하는 것과 같은 좋은 옵션이 있다.이것은 우리가 제공한 것보다 더 낮거나 더 큰 원소를 얻을 수 있다는 것을 의미한다.우리는 우리가 제공한 원소보다 크거나 작은 원소를 얻을 수 있다.또한 DescendangSet 방법을 호출하여 이 집합을 반전시킬 수 있습니다

인터페이스 대기열

이 집합은 선진적인 선출 메커니즘, 즉 선진적인 선출을 사용한다.그것에 대해 어떤 조작을 하기 전에, 우리는 이 집합 요소를 저장할 수 있다.추가, 삭제와 같은 모든 기본 작업이 존재합니다.그러나 이런 방법은 두 버전에 존재한다.첫 번째 버전이 이상을 일으키면 작업이 실패하면 다른 버전은 이상을 일으키지 않고 null과 같은 특수 값을 되돌려줍니다.이 구조에 null을 추가할 수 있습니다.그러나 이 인터페이스를 실현하는 LinkedList는 null개의 요소를 삽입할 수 있습니다.이 방법은 그것을 병렬적으로 접근할 수 있는 방법을 제공하지 않았다.병렬 환경에서 대기열을 사용하려면 BlockingQueue를 사용하십시오. 이것은 차단 방법을 제공합니다.

텍

이런 실현은 우리가 대기열의 양쪽 끝-시작과 끝을 동시에 처리할 수 있게 한다.DE는 양단의 이니셜입니다.엄격한 크기 대기열을 만들 수도 있고 동적 크기 대기열을 만들 수도 있습니다.이 밖에 대기열에는 두 가지 기본 조작을 위한 방법 버전이 존재하기 때문이다.만약 조작이 실패한다면, 한 버전은 이상을 던지고, 다른 버전은 특수한 값을 되돌려줍니다. 이 값은 우리에게 조작 실패 신호를 보냅니다.색인 액세스가 없습니다.

패턴 대기열

이름에서 알 수 있듯이 이 대열은 간단한 수조에 기초한 것이다.크기에 구애받지 않고 필요한 경우 스토리지 용량을 확보합니다.할당 시간을 위해 더 많은 조작을 집행하다.

우선권

이 대기열이 실현하는 주요 작업 원리는 우리가 집합에 새로운 요소를 추가할 때, 집합에서 정확한 순서를 실현하기 위해 정렬 방법을 호출하는 것이다.이런 상황에서 우선권은 무엇입니까?간단합니다. 트리 집합으로서 요소는 일부 속성을 통해 비교할 수 있어야 합니다. 이 속성을 선택해야 하거나, 이 집합에서 요소의 정확한 순서를 위해 비교기를 제공해야 합니다.methodspoll (이 집합에서 삭제하는 것이 아니라) 을 호출할 때, 현재 우선순위가 가장 높은 요소를 얻을 수 있습니다.이 집합은 추가/제공, 삭제/당김 등 작업에logariphm 속도를 제공하고 포함 등 작업에 선형 시간을 제공합니다.

인터페이스 맵

하히토

이름부터 우리 구조에 이르기까지 해시 함수를 사용한다.이 구조는 우리가null 요소를 키나 값으로 사용할 수 있도록 합니다.반복할 때, 요소가 삽입 순서에 따라 배열되지 않는 것을 볼 수 있습니다.이 구조의 성능에 대해 구조 함수를 통해 전달되는 두 개의 매개 변수를 사용한다.그것은 부하 계수와 초기 용량이다.초기 용량은 통의 수량을 결정한다.부하 인자는 저장통의 계수를 정확하게 저장하기 위해 언제 방법을 호출할지 결정한다.

ConcurrentHashMap

이 맵은 동시 사용이 필요합니다.반대로 해시 맵은 맵의 라인이 안전하게 실현되는 것이다.이 맵의 실체는volatile로 표시되어 있습니다. 이것은 모든 스레드가 이 실체의 실제 버전을 가지고 있어야 한다는 것을 의미합니다.

내비게이션 맵

이 인터페이스는 SortMap 인터페이스를 확장하고 지도 요소를 뛰어넘어 내비게이션을 하는 방법인 lower Entry,floor Entry,ceiling Entry,higher Entry를 추가했습니다.이 방법은 null을 되돌릴 수 있습니다.descendingMap을 호출하여 직선과 역순으로 훑어볼 수 있습니다.내비게이션 방법도 있는데 지도 등 일부 지도를 추출하는 방법을 제공한다.(자/머리/끝) 매핑 방법에 낮은 경계와 높은 경계를 포함합니다.대기열에 이 방법의 두 버전이 존재하기 때문에 마지막 요소와 첫 번째 요소를 가져오는 방법이 있습니다.

트리 맵

그것은 내비게이션 지도를 기반으로 한 붉은색과 검은색 나무다.원소는 자연 순서나 비교기에 따라 정렬되며, 비교기는 반드시 구조 함수에 따라 제공해야 한다.

흔했어

이 모든 구조물(ConcurentHashMap 제외)은 안전하지 않습니다.이것은 당신이 몇 개의 라인을 가지고 싶다면 공유된 자원이 있어야 한다는 것을 의미한다.이 모든 것은 너의 임무에 적합하지 않다.
또한 반복 작업에서 집합을 수정하려고 시도할 때 ConcurrentModificationException을 받았습니다. 이것은 반복 작업에서 집합을 변경하려고 시도했음을 나타냅니다.이것은 허락하지 않는다!이 조작에 대해 우리는 자바 특수 패키지에 있는 병렬 데이터 구조를 사용해야 한다.
UPD:
주석 ConcurrentModificationException에서 순환 중iterate 요소를 삭제하려고 시도할 때 던집니다.교체할 때 집합에서 원소를 삭제하려고 합니다.교체기를 사용해야 합니다.

while(iterator.hasNext()) {
    if (iterator.next() == 1) {
        iterator.remove();
    }
}

고마워요!

트위터에 @VoronyanskyE