[CS면접 및 자바 면접 준비] 컬렉션 프레임워크

컬렉션 프레임워크

컬렉션 프레임워크란?

➕

• 다수의 데이터를 쉽고 효과적으로 관리할 수 있는 표준화된 방법을 제공하는 클래스의 집합을 의미합니다.
• 자바 컬렉션에는 List, Set, Map 인터페이스를 기준으로 여러 구현체가 존재하고, 이에 더해 Stack, Queue 인터페이스도 존재합니다.
• Java에서 Collection 이란 데이터의 집합, 그룹을 의미
• JCF(Java Collection Framework)는 객체들을 한 곳에 모아 관리하고, 편하게 사용하기 위해 제공되는 환경
• 데이터, 자료구조인 컬렉션과 이를 구현하는 클래스를 정의하는 인터페이스를 제공한다.
• List, Map, Set, Stack, Queue 등이 있다.
• 다수의 데이터를 다루는데 자료구조를 직접 구현하지 않고 편하게 사용할 수 있다.
• 배열과 다르게 객체를 보관하기 위한 공간을 미리 정하지 않아도 된다. 상황에 따라 객체의 수를 동적으로 정한다.

배열과 리스트의 차이란?

➕ **Array는 메모리 상에 데이터가 연속적으로 저장**되고,

List는 메모리 상에 데이터가 비연속적으로 저장된다.

(Array와 List의 차이를 묻는 것은 Array와 LinkedList의 차이를 묻는 것이 일반적이다.)

• 크기가 가변적인 배열이 필요하다면 ArrayList
• LinkedList의 삭제, 추가 시간 복잡도는 O(N)이지만 Array나 ArrayList보다 빠름
  • 데이터의 삭제 추가가 많을 때 -> LinkedList
  • 데이터의 접근이 많을 때 -> Array, ArrayList
• Array, ArrayList는 인덱스가 있지만 LinkedList는 없다.
  • 인덱스가 필요하면 Array, ArrayList
  • 인덱스가 필요 없다면 LinkedList
• 아래 사진에서 수정해야 할 부분
  • ArrayList는 순차적이지 않다. 실제 개체는 연속된 위치에 저장되지 않고 실제 개체의 참조는 인접한 위치에 저장된다.

(https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https://blog.kakaocdn.net/dn/cJFemK/btroM6XXMAW/7CBVQIsIQTwTQQ4OtDIKaK/img.png)

List란?

➕ List인터페이스를 직접 @override를 통해 사용자가 정의하여 사용할 수 있다. 대표적인 구현체로는 `ArrayList`와 `LinkedList`가 있다. 순서가 있는 데이터의 집합으로 중복을 허용한다.

List와 Vector의 차이

➕

• 벡터는 데이터 삽입시 원소를 밀어내지만 리스트는 노드를 연결만 하기 때문에,
• 삽입 삭제 부분에서 리스트가 시간복잡도의 우위를 가집니다.
• 벡터는 랜덤부분접근이 가능하지만 리스트는 더블링크드리스트(노드가 양쪽으로 연결)로 되어있기 때문에 랜덤 접근이 되지 않습니다.
• 검색적인 측면에서는 벡터가 우위에 있습니다.
• 벡터는 리스트와 달리 되는 항상 동기화 장점이자 단점을 가지고 있습니다. 멀티 쓰레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있지만, 단일쓰레드 환경 일때도 동기화를 하기 때문에 List보다 성능이 떨어집니다.

ArrayList란?

➕ Java의 Vector를 개선한, 배열로 구현된 List 데이터가 저장되는 순서가 같다. 사실상 배열과 같은 자료구조이기 때문에, List의 연산 자체의 수행 시간 속도는 배열과 같다. 다방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 조회 기능이 뛰어나다.

LinkedList란?

➕ 다음 노드의 주소를 기억하고 있는 List타입으로, 배열에 비해 삽입과 삭제가 간단하다. 탐색의 경우는 첫 번째 노드부터 탐색하기 때문에 속도가 느리다. 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치정보만 수정하면 되기에 유용하다 Stack, Queue, 양방향 큐 등을 만들기 위한 용도로 쓰인다.

Map란?

➕ 대표적으로 HashMap이 존재한다. 키 -밸류의 쌍으로 이루어진 데이터의 집합, 데이터의 순서를 보장하지 않는다. 키의 중복을 허용하지 않으나 값의 중복은 허용한다. key에 대한 순서를 보장하기 위해서는 LinkedHashMap을 사용한다.

HashaMap이란?

➕ Key값에 함수를 적용하여 나오는 Index에 Value를 저장하는 Entry객체를 저장하는 구조인데, 중복과 순서가 허용되지 않으며 null값이 나올 수 있다. 여기서 키와 값은 모두 객체이다. 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다.

HashTable이란?

➕ HashMap보다는 느리지만 동기화를 지원한다. HashMap과 다른 점은 Key값 혹은 Value값에 null을 넣으면 컴파일 에러 발생

HashMap과 HashTable의 차이점은?

➕

• HashTable은 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java 2에서 처음 선보인 JCF(Java Collections Framework)에 속한 API이다.
• HashTable 또한 Map 인터페이스를 구현하고 있기때문에 HashMap과 HashTable이 제공하는 기능은 같다.

차이점

• 보조 해시 함수
  • HashMap은 보조 해시 함수를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
• 동기화
  • HashTable은 synchronized 메소드를 사용해 동기화를 지원하는 반면에, HashMap은 동기화를 지원하지 않는다.

TreeMap이란?

➕ Red-Black Tree 자료구조를 이용한 Map이다. Tree(트리) 구조이기에 어느 정도 순서를 보장한다. 정렬된 순서대로 key, Value를 저장하여 검색이 빠르며 자동 정렬(오름 차순)된다. 문자열일 경우 유니코드로 정렬한다. 일반적으로 Map으로써 HashMap보다 성능이 떨어진다.

TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸린다.

하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다.

TreeMap과 TreeSet의 차이점은?

➕ TreeSet은 그냥 값만 저장하지만, TreeMap은 키와 값으로 구성된 Entry를 저장한다.

Red-Black Tree란?

➕ 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한 쪽으로 치우쳐지지 않도록 균형을 맞추는 것

Set이란?

➕ 대표적인 구현체로 HashSet이 존재한다 value에 대해서 중복된 값을 저장하지 않는다. Map과 같이 Set도 순서를 보장하지 않아서 순서를 보장하기 위해서는 LinkedHashSet을 사용한다.

HashSet

➕ HashMap에서 key값이 없는 자료형 집합이라고 생각해도 된다. 값이 포함되어 있는지 아닌지만 관심이 있다. 순서와 중복 값을 허용하지 않는다. 가장 빠른 임의 접근 속도라는 특징이 있다.

TreeSet

➕ Red-Black Tree자료구조를 사용한 Set이다. 정렬 방법을 지정할 수 있다.

Set과 Map의 타입이 Wrapper Class가 아닌 Object를 받을 때 중복 검사는 어떻게 진행하는가?

➕ hashCode() 메서드를 오버라이딩하여 리턴된 해시코드 값이 같은지 판단합니다. 값이 다르다면 다른 객체로 판단하고, 해시코드 값이 같다면 equals()메서드를 오버라이딩 하여 다시 비교합니다.

위의 개념을 위해서는 동일성과 동등성을 먼저 알아야한다.
**동일성** : 두 개의 객체가 완전히 하나의 같은 객체인지 판단하는 것. 즉 , 메모리에 저장된 주소공간이 완전히 같을 경우 동일성이 보장된다.

**동등성** : 두 객체의 주소공간이 달라도 단순히 가지고 있는 값만 같다면 동등성이 보장된다.

이는 단순 문자열(원시형)과 객체로 생성한 값 사이의 차이점과 동일하다.

그 다음으로는 equals의 필요성이다.
equals가 필요한 이유는 객체지향의 캡슐화 개념때문이기도 하다.
내부 사앹 정보를 숨긴 채로 두 객체의 동등성 정보를 파악해야 하는데, 따라서 상태 간 비교가 아닌 더 큰 개념에서 객체와 객체 사이의 정보를 비교해야 한다.
그러므로 equals의 오버라이딩이 필요하다.

• 예시코드(equals 그대로 사용)
  • 내부 상태가 완전히 같아도 동등성을 보장할 수 없다.
  • public static void main(String[] args) { Car car1 = new Car(1,"sonata"); Car car2 = new Car(1,"sonata"); System.out.println(car1.equals(car2)); //false }
• 예시코드(equals를 재정의)
  • 동등성이 보장된다.
  • public class Car { private final int id; private final String name; public Car(int id, String name) { this.id = id; this.name = name; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Car car = (Car) o; if (id != car.id) { return false; } return Objects.equals(name, car.name); } } public static void main(String[] args) { Car car1 = new Car(1,"sonata"); Car car2 = new Car(1,"sonata"); System.out.println(car1.equals(car2)); //true }

마지막으로 가장 중요한 hashcode는 왜 필요한가이다.
equals만 잘 재정의하면 모든 객체의 동등성이 보장될 것 같지만 그렇지 않다.
Hash값을 사용하는 Hash Collection 자료구조(HashMap, HashSet, HashTable)때문에 발생한다.

• 예시코드
  • Set을 사용하여 완전히 상태가 같은 객체를 두 번 넣어지만 길이가 1이아닌 2가 나온다.
  • 동등성 보장에 실패한 것이다.
  • 원인은 아래의 사진과 같다.
  • public static void main(String[] args) { Set<Car> cars = new HashSet<>(); cars.add(new Car(1, "sonata")); cars.add(new Car(1, "sonata")); System.out.println(cars.size()); // 2 -> HashSet 사이즈가 1이 아닌 2임 }
• 보장되지 않는 이유
  • Hash를 사용하는 Collection들은 객체의 동등성 비교를 다음 고정과 같이 수행한다.
  • 일단 hashcode값이 서로 같아야만 equals메소드로 객체비교를 수행한다.
  • hashcode와 equals를 모두 재정의 해줘야 객체의 동등성이 비교된다.

 

 

다른 면접 질문 보러가기

 

https://sunro1994.tistory.com/196