[Java] 컬렉션 프레임워크 활용

 

배열의 한계

• 배열 사이즈가 정적이기 때문에 추가 연산시 자리가 부족할 수 있다.
• 배열의 중간 원소 삽입이나 삭제가 힘들다.
• 배열 사이즈가 정적임을 대비해 너무 크게 할당할 경우 메모리 낭비가 심해진다.

 

이러한 한계를 극복한 것이 컬렉션이다.

 

컬렉션

• 배열을 동적으로 변경해서 사용자가 사용할 수 있도록 만든 프레임워크이다.
• 제너릭으로 되어있고, 객체 생성시 타입을 지정한다.
• 동일 타입의 데이터를 저장할 수 있다. 
• 장점
  • 일관된 API
  • 프로그래밍 노력 감소
  • 프로그램 속도 및 품질 향상

 

클래스/ 인터페이스 구조도

 

주요 인터페이스 

 

List<E> 

• 순서 유지
• 인덱스 존재
• 원소 중복 가능
  •  ArrayList
    • Array를 이용해서 내용 유지
    • 배열 크기 부족해지면 50%로 늘림
    • 연속적 주소 할당
    • 검색 성능 👍🏻
      • 연속적으로 주소 할당되어 있으므로 검색 성능이 좋음
    • 추가 / 삭제 성능 👎🏻
      • 중간 원소 추가나 삭제가 일어날 경우 앞으로 댕겨주거나 뒤로 밀어주는 작업 필요
    • not synchronized
  • Vector
    • JDK 1.0
    • 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하기 위함
    • synchronized
    • "Re-sizable Array" + "Synchronization”
      • 이러한 디자인보다는 크기 조정할 수 있는 배열 ArrayList이 있고 동기화할 때마다 Collections.synchronizedList()을 사용하는 게 좋음
    • 모든 메소드 동기화 → 시간 오래걸림, 애플리케이션 성능 저하 👎🏻
      • 모든 작업을 동기화하는 것보다 동기화할 작업 집합이 필요
    • 대신에 *Collections.synchronizedList,* ConcurrentQueue 사용
    • Array 이용해서 내용 유지
    • 배열 크기 부족해지면 2배로 늘림
  • LinkedList
    
    • 비연속적 주소 할당
    • 양방향 연결 리스트 doubly linked list 로 구현
      • next_node 주소 뿐만 아니라 prev_node 주소도 가지고 있음
      • single linked list보다 검색 성능이 향상
    • 추가 / 삭제 성능 👍🏻
      • 추가나 삭제가 일어날 경우 변경되는 노드만 다시 연결
    • 검색 성능 👎🏻
      • 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색 필요
  • 📌 ArrayList는 검색이 많은 경우에 사용하고 LinkedList는 삽입/삭제 시 사용

 

Set<E>

• 집합 개념
• 기본적으로 순서 유지 보장 ❌
• 인덱스라는 개념이 없음
• 원소 중복 불가
  • hashCode() 와 equals() 가 true 이면 동일한 객체라고 판단
• 구현 클래스
  • hashing
    • hash function
      • 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 맵핑하는 함수
        • h(key) = value
        • key - 맵핑 전 데이터
        • hash value - 매핑 후 해시값
        • hashing - 매핑하는 과정 자체
    • hashing 과정
      • hash table이라는 가상공간을 만들어 기억공간을 할당하고 hash function을 이용하여 레코드 키에 대한 hash table 내의 home address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식
      • hash function (”타깃 코더”) = home address
    • hash table해쉬 테이블
    • 해시 충돌
      • 해쉬함수는 해쉬값보다 보통 많은 키값을 해쉬값으로 변환
      • 서로 다른 두 개의 키에 대해 동일한 해시값 반환해시 충돌 (이름을 0~15 사이의 정수값으로 매핑하는 해시 함수의 예)
      • 해결 방법
        • Direct-address table
          • 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블
          • 해시 충돌 발생 ❌
          • 전체 키가 실제 사용하는 키보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 마련해야 하는 탓에 메모리 효율성 저하
          • 해시함수를 사용하여 key를 해시값으로 매핑하고 이 해시값을 index 또는 주소 삼아 데이터의 value을 키와 함께 저장하는 자료구조를 해시테이블
          • 보통은 해시테이블 크기 (𝑚)가 실제 사용하는 키 (𝑛)보다 적은 해시테이블 사용
            • 데이터가 많고 메모리 등 리소스 문제도 생기기 때문
            • load factor(α) = 𝑛/𝑚
              • 해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는가
              • 1보다 크면 해쉬 충돌
        • Chaining 자바
          • 충돌시 연결 리스트에 추가
          • 중복된 해시값이 있는 경우 해당 슬롯을 연결 리스트로 저장
          • 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)
          • 트리로 구성하여 시간 복잡도 줄일 수 있음 O(logn) 자바
        • Open Addressing
          • 충돌 발생시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터 저장
          • 오픈 어드레싱은 충돌을 피하기 위한 다른 방법으로 key를 해시 테이블에 직접 저장
          • 구현 간편하고 검색도 미세하게 빨라짐
          • 성능이 좋지만 슬롯이 80% 차게 되면 급격하게 성능저하가 일어남
        • 언어별 해결방법 채택언어 방식

          C++	개별 체이닝
          Java	개별 체이닝
          Go	개별 체이닝
          Ruby	오픈 어드레싱
          Python	오픈 어드레싱

    • 장점
      • 적은 리소스로 많은 데이터를 효율적으로 관리하기 위함
      • 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로 프로세스를 관리할 수 있음
      • 인덱스에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있음 𝑂(1)
      • 해시함수는 언제나 동일한 해시값을 리턴하고 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있음
      • 인덱싱은 계산이 간단한 함수로 작동하기 때문에 효율적
    • 문제점
      • 해쉬는 rehashing 될때 비정상적인 시간 걸릴 수 있음
      • 해쉬는 페이지 폴트 발생 가능
        • 페이지 폴트 - 프로그램이 자신의 주소 공간에는 존재하지만 시스템 RAM에는 현재 없는 데이터나 코드에 접근 시도하였을 경우 발생하는 현상
        • 페이지간 전환이 많아지면 느려짐
      • 해쉬는 효율적인 lookup을 위해 버켓 안의 모든 요소 스왑 가능
      • 해쉬 테이블 리사이징 가능 - 성능 갑자기 다운됨
      • 해쉬는 메모리 낭비가 있을 수 있음
  • HashSet
    
    • 해쉬 테이블에 원소 저장
    • 삽입 / 삭제 / 조회 연산 → 평균 $O(1)$ 보장
    • 삽입시 최악의 경우 $O(n)$
      • 해쉬 테이블 리사이징 할 경우
    • 원소 삽입 순서 유지 ❌
    • 동일한 객체 저장하지 않음
  • LinkedHashSet해쉬 테이블연결 리스트
    • 해쉬 테이블과 연결 리스트가 결합된 형태
    • 원소 삽입 순서 유지
  • TreeSet
    
    • 크기 순서 유지
      • 속도는 HashSet 보다 느림
    • 이진 검색 트리 기반
      • 이진 검색 트리 중 [레드-블랙 트리](<https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC>) 이용
        • red-black tree
        • self-balancing binary search tree
      • 검색 / 정렬 👍🏻
        • 레드-블랙 트리는 roughly하게 balaned하므로 $O(\log {n})$
      • 추가 / 삭제 오래 걸림 👎🏻
        • 최대 3번의 트리 회전이 필요함
        • 복잡하지만 복잡도는 여전히 $O(\log {n})$
      • 해쉬에 비해 일관된 성능을 가지지만 범위 검색 불가능
        • 해쉬는 rehashing 될때 비정상적인 시간 걸릴 가능성 존재
      • 연속된 삽입을 통해 지역성 유지가 쉬움
        • 더 적은 I/O 발생
    • 하나의 노드는 데이터, 왼쪽 자식, 오른쪽 자식로 구성
    • 원소 삽입 순서 유지 ❌
    • 입력된 순서대로 값을 저장하지 않음

 

Map<K, V>

• Key, Value 쌍으로 이루어진 구조
• 기본적으로 순서 유지 보장 ❌
• 인덱스라는 개념이 없음
• 키 중복 불가 / 원소 중복 가능
• 구현 클래스
  
  • HashMap
    • JDK 2
    • 삽입 순서 유지되지 않음
    • 해쉬 테이블에 키 값을 저장
    • 삽입 / 삭제 / 조회 연산 → 평균 $O(1)$ 보장
    • 삽입시 최악의 경우 $O(n)$
      • 해쉬 테이블 리사이징 할 경우
    • not synchronized
    • 보조 해쉬 함수를 이용
      • 보조 해쉬 함수 사용하지 않는 Hashtable에 비해 해쉬 충돌이 덜 발생
      • 보조 해쉬 함수 구현
      • static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
    • Hashtable 구현에는 거의 변화가 없지만 HashMap은 지속적으로 개선됨
    • 웹 개발시 활용 🕸
      • 웹 애플리케이션 서버의 경우에는 HTTPRequest가 생성될 때마다 여러 개의 HashMap이 생성
      • 수많은 HashMap 객체가 1초도 안 되는 시간에 생성되고 GC 대상이 됨
      • JSON ↔️ HashMap
  • LinkedHashMap해쉬 테이블연결 리스트
    • 해쉬 테이블과 연결 리스트가 결합된 형태
    • 원소 삽입 순서 유지
  • TreeMapTreeMap 구조
    • 크기 순서 유지
    • 이진 검색 트리 기반
      • 이진 검색 트리 중 [레드-블랙 트리](<https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC>) 이용
        • red-black tree
        • self-balancing binary search tree
        • 해쉬에 비해 일관된 성능을 가지지만 범위 검색 불가능
          • 해쉬는 rehashing 될때 비정상적인 시간 걸릴 가능성 존재
        • 연속된 삽입을 통해 지역성 유지가 쉬움
          • 더 적은 I/O 발생
      • 검색 / 정렬 👍🏻
        • 레드-블랙 트리는 roughly하게 balaned하므로 $O(\log {n})$
      • 추가 / 삭제 오래 걸림 👎🏻
        • 최대 3번의 트리 회전이 필요함
        • 복잡하지만 복잡도는 여전히 $O(\log {n})$
    • 하나의 노드는 key, value, 왼쪽 자식, 오른쪽 자식으로 구성
    • 원소 삽입 순서 유지 ❌
    • 입력된 순서대로 값을 저장하지 않음

 

Stack<E>

• 책이 쌓이는 것처럼 📚 나중에 넣은 객체가 먼저 빠져나가는 자료구조
  • 입력 1 → 2 → 3 → 4
  • 출력 4 → 3 → 2 → 1
• Last In, First Out (LIFO)
• 예시
  • Stack 메모리
    • 할당 순서 a → b → c → i
    • 해제 순서 i → c → b → a
  • int a = 3; int b = 5; int c = 7; for(int i = 0; ... ){ }
• Stack<E> stack = new Stack<>();
  • Stack은 클래스
  • Stack은 Vector를 상속받아 만듦

 

Queue<E>

• 사람이 줄서있는 것처럼 먼저 넣은 객체가 먼저 빠져나가는 자료구조
  • 입력 1 → 2 → 3 → 4
  • 출력 1 → 2 → 3 → 4
• First In, First Out (FIFO)
• Queue<E> queue = new LinkedList<>();
  • Queue는 인터페이스
  • 실제 구현은 LinkedList 통해 구현
  • Queue는 구현 방법을 명시하고 있지 않다는 점에서 ADT 관점