상용 데이터 구조 - Collection

환경: JDK 1.8
List：
질서 있 게 반복 가능 - Array List: 1, 바 텀 은 배열 입 니 다.2. 기본 용량 은 10 입 니 다.3. 최대 용량 (Integer. MAX VALUE - 8);4. 확장 시 신 용량 은 구 용량 의 1.5 배, 즉 신 용량 = 구 용량 * 1.5;5. 비 스 레 드 안전.

//       
public static int getArrayListCapacity(ArrayList> arrayList) {
        Class arrayListClass = ArrayList.class;
        try {
            Field field = arrayListClass.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] objects = (Object[])field.get(arrayList);
            return objects.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
            return -1;
        } catch (IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }

add 방법

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 1️⃣
        elementData[size++] = e; //2️⃣
        return true;
    }

add 방법 은 두 줄 코드 입 니 다.️⃣처 는 확장 여 부 를 판단 하 는 것 을 나타 낸다.2️⃣처 는 가입 한 e 를 배열 의 끝 에 두 겠 다 고 밝 혔 다.
동시 다발 상황 이 발생 했 을 때 왜 Array List 는 스 레 드 가 안전 하지 않 은 지, 바 텀 배열 에 빈 자리 가 있 을 때 1, 스 레 드 1 을 실행 하 는 지 살 펴 보 자.️⃣，빈 위치 가 있 기 때문에 용량 을 늘 리 지 않 습 니 다. 이때 라인 1 은 CPU 를 양보 합 니 다.2. 스 레 드 2 실행 1️⃣빈 자리 가 있 기 때문에 용량 을 늘 리 지 않 습 니 다.️⃣그 후에 배열 이 가득 찼 습 니 다.3. 그리고 스 레 드 1 에서 CPU 를 가 져 와 2 를 실행 합 니 다.️⃣，이때 데이터 가 가득 차 서 추가 할 때 배열 아래 에 표 시 된 크로스 오 버 2, 곧 확장 1, 스 레 드 1 이 실 행 될 것 임 을 알려 줍 니 다.️⃣후, 수조 가 용량 을 늘 리 기 시작 한 후, 집행 2️⃣，size + 의 과정 은 읽 기 - 고치 기 - 세 가지 절 차 를 쓰 는 것 입 니 다. size = 10;2. 스 레 드 2 실행 1️⃣이후 스 레 드 1 이 확장 되 었 기 때문에 더 이상 확장 할 필요 가 없다.️⃣，스 레 드 가 실행 되 지 않 았 기 때문에, 이 때 size = 10;3. 따라서 두 스 레 드 가 동시에 size = 10 의 아래 에 데 이 터 를 표시 할 때 더러 운 데이터 가 발생 합 니 다.
그렇다면 어떻게 확장 할 것 인가?

 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 3️⃣
            return Math.max(DEFAULT_CAPACITY, minCapacity); //4️⃣
        }
        return minCapacity;
        }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); //5️⃣
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

3️⃣무 참 구조 함 수 를 진행 할 때 add 방법 을 처음 호출 할 때 배열 의 초기 화 를 진행 합 니 다. 4.️⃣둘 의 최대 치, minCapacity = 0, DEFAULT 가 져 오기CAPACITY = 10 이상 의 절 차 는 초기 화 과정 이 고 실제 확 대 된 소스 코드 는 다음 과 같다.

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

new Capacity 는 새 배열 의 길이 입 니 다. new Capacity = oldCapacity + (oldCapacity > > 1) 라 는 말 은 오래된 배열 의 길이 + 오래된 배열 의 길 이 를 오른쪽으로 한 자리 옮 기 고 new Capacity = 1.5oldCapacity. 즉, ArrayList 집합 이 확장 되면 이전 1.5 배로 확대 한 다 는 뜻 입 니 다.아래 의 코드 는 쉽게 이해 할 수 있 습 니 다. 모두 가 직접 보고 오래된 배열 의 데 이 터 를 새 배열 로 복사 합 니 다.
remove 방법

public E remove(int index) {
        rangeCheck(index); //6️⃣

        modCount++;
        E oldValue = elementData(index); //7️⃣

        int numMoved = size - index - 1; //8️⃣
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved); //9️⃣
        elementData[--size] = null; // clear to let GC do its work 1️⃣0️⃣

        return oldValue;
    }

6️⃣index 가 합 법 적 인지 판단 하 는 것 입 니 다. 즉, index > = size 는 이상 을 던 집 니 다.

/**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

7️⃣삭제 할 값 8 가 져 오기️⃣이동 할 아래 표 시 를 가 져 오 는 것 입 니 다 9️⃣삭제 위치 뒤의 데 이 터 를 앞으로 이동 시 키 는 겁 니 다.
add 방법 과 remove 방법 을 통 해 알 수 있 듯 이 삽입 과 삭 제 는 배열 을 복사 하고 이동 해 야 하기 때문에 효율 이 낮 기 때문에 Array List 는 비교적 많은 업무 논 리 를 삽입 하고 삭제 하 는 데 적합 하지 않다.
조회 하 다.

/**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index); //1️⃣1️⃣

        return elementData(index); //1️⃣2️⃣
    }

검색 이 간단 하 다 는 것 을 알 수 있다.️⃣1️⃣먼저 index 가 합 법 적 인지 판단, 1️⃣2️⃣그 다음 에 아래 표 시 를 통 해 값 을 얻 고 시간 복잡 도 는 O (1) 이 며 조회 가 매우 효율 적 입 니 다.

Set: 무질서 중복 불가, null 하나만 존재

HashSet 1, 밑바닥 은 HashMap 이다.2. 구체 적 인 API 는 HashMap 을 참조 할 수 있 습 니 다.