JAVA의 공통 컬렉션의 내부 메커니즘 원리 분석

일반적으로 사용되는 컬렉션에 대해서는 누구나 익숙하지만 내부 원리에 대해서는 약간만 이해했을 수도 있습니다. 소스 코드를 읽으면 다음 내용이 이해됩니다.

배열목록

ArrayList 내부는 기본 크기가 10인 동적 객체 배열 컨테이너입니다. 새로운 데이터가 추가될 때마다 원래 컨테이너 크기보다 커지면 Arrays를 통해 컨테이너 크기가 늘어납니다. .copyOf를 원본의 1.5배로 늘리는 등 데이터 크기를 예측할 수 있는 경우 확장으로 인한 리소스 소비를 줄이기 위해 기본적으로 동적 데이터의 크기를 설정할 수 있습니다.

get() - 아래 첨자 직접 읽기 - O(1)

add(E) - 끝에 직접 추가 - O(1)

add(idnex, 마) - 데이터 삽입 후 다음 데이터 이동 필요 - O(n)

remove(index) - 삭제 후 이동 필요 - O(n)

LinkedList

LinkedList는 새로운 데이터를 추가할 때 실제로 linklast를 호출하여 연결리스트 끝에 데이터를 삽입하는 방식으로, 삭제 시 바로 찾을 수 있습니다. 🎜>시간 복잡도:

get() - 순회 필요 - O(n)

add(E) - 호출 linklast 끝에 직접 추가하려면 - O(1)

add(index, E) - 원래 인덱스 위치에서 먼저 데이터를 찾은 후 링크된 전후의 데이터를 다시 지정해야 합니다. list - O(n)

remove() - RemoveLast를 직접 호출하여 마지막 데이터 삭제 - O(1 )

remove(index) - 원본 인덱스에서 데이터를 찾아야 함 위치 우선 - O(n)

Hash

Map
HashMap은 실제로 내부 배열이며, 각 배열은 단방향 연결 목록입니다. HashMap의 배열은 (key, value, next) 속성을 포함하는 Entry라는 클래스입니다. 배열 첨자는 hash(key)%len에 의해 획득됩니다. 배열을 얻은 후 HashMap에는 로드 계수(기본값 0.75)가 있습니다. 그런 다음 hash(key)%len의 값이 다음과 같은 경우 질문이 발생합니다. Put 동안 동일하면 충돌이 발생하지 않습니까? HashMap의 처리 방법은 원래 Entry[0] = A가 있고 이제 인덱스가 0인 B가 오면 Entry[0] = B, B.next = A이고 또 다른 C가 오면 다음과 같습니다. Entry[0] = C, C.next = B 등이 됩니다. 이런 식으로 Entry는 연결된 목록을 형성하고, 가져올 때 연결된 목록을 순회하여 값을 얻습니다.

여기서 언급해야 할 점은 hashMap을 사용할 때 도입된 키 객체가 hashCode()와equal()의 두

함수

를 다시 작성해야 한다는 것입니다. 그 이유는 소스를 참조할 수 있습니다. 코드 판단 조건(if (e.hash == hash && ((k = e.key) == key || key.equals(k)))), hashCode()를 다시 작성하지 않으면 해당 배열을 찾을 수 없습니다. Equal( )을 다시 작성하지 않으면 키 값의 내용이 동일한지 여부를 판단할 수 없습니다.

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null总是放在数组的第一个链表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍历链表  
        for (Entry<k> e = table[i]; e != null; e = e.next) {  
            Object k;  
            //如果key在链表中已存在，则替换为新value  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
}</k>

보충: 해시맵은 java8 이후에 최적화되었습니다. 단일 연결 목록의

쿼리

시간 복잡도는 극단적인 경우 O(n)입니다. 성능 문제가 있을 수 있으므로 연결 목록 길이가 8보다 큰 경우 Java8은 저장 쿼리의 효율성을 향상시키기 위해 저장에 O(log n)의 시간 복잡도를 갖는 레드-블랙 트리를 사용합니다.

LinkedHashMap

LinkedHashMap의 내부 이중 연결 리스트와 HashMap의 조합은 다중 반복 순서를 지원하며, 기본값은 삽입 순서이며 액세스 순서일 수도 있습니다.

액세스 순서(accessOrder=true): get을 호출하여 액세스한 요소는 체인의 끝에 배치되고 체인의 시작 부분부터 반복이 시작됩니다.

삽입 순서(accessOrder= false): 삽입순서 반복 나옴

TreeMap

TreeMap은 Red-Black Tree를 기반으로 내부적으로 구현되며, CompareTo를 통해 자연스럽게 키 유형별로 정렬됩니다. 기본. TreeSet의 하위 레벨은 TreeMap입니다.

위 내용은 JAVA의 공통 컬렉션의 내부 메커니즘 원리 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!