박성훈의 웹개발

맵(Map)이란?

1) 맵(Map)은 key/value 형태를 가지는 자바 컬렉션이다. 컬렉션 프레임워크에 속하지만 List, Set과 다르게 Collection 인터페이스를 구현하지 않는다.

2) key는 고유하여야 한다. 만약 맵에서 같은 key를 사용하게 된다면 그 값은 덮어 씌워진다.

3) 대표적인 구현 클래스로는 HashMap, TreeMap 등이 있다.

HashMap

1) key 객체에 대한 hashCode() 메소드로 생성된 해시값을 사용하여 value를 저장하고 조회한다.

2) 순서를 보장하지 않는다. 입력순서를 보장받으려면 LinkedHashMap을 사용하면 된다.

3) HashMap은 멀티 쓰레드 환경에서 Thread Safe하지 않다. 이것이 HashTable과의 차이점이다.Thread Safe하지 않지만 모든면에서 HashTable보다 HashMap이 우위에 있다. HashTable은 1.1 이전의 레거시 코드를 위해서 유지가 될 뿐이지만 HashMap은 자바8에서도 계속 개선되고 있다. 만약 동기화가 필요하다면 synchronizedMap이나 ConcurrentHashMap 클래스를 이용하는 것이 좋다.

4) 저장방식

- HashMap에는 key/value 쌍을 나타내는 Entry<K, V>라는 내부 클래스가 있는데, HashMap 멤버변수로 Entry<K, V> 배열이 선언되어 있다. 이 배열에 key/value를 저장하게 된다.

- HashMap은 내부적으로 bucket을 사용하는데 bucket은 Map에 저장되는 element를 체계적으로 분산시켜 놓는 방법이라 할 수 있다. 해시값을 통해서 bucketIndex를 생성하고 Entry<K, V> 배열에 인덱스로 활용되어 값을 저장한다. bucket의 수는 load factor에 의해 결정된다.

- 다음은 HashMap put() 메소드의 일부이다.

※ 참고자료

- https://en.wikipedia.org/wiki/Hash_table

- http://d2.naver.com/helloworld/831311

- http://iilii.egloos.com/4457500

리스트(List)란?

1) 자바 콜렉션 프레임워크중에서 가장 많이 사용하는 자료구조는 리스트(List)일 것이다. 리스트는 특정 타입 값들이 순차적으로 정렬된 컬렉션이다. 대표적인 구현 클래스로는 ArrayList, LinkedList 등이 있다.

2) 배열 역시 데이터의 집합을 순차적으로 표현하는 용도이나 사이즈에 제한이 있다. 배열은 생성시 선언한 사이즈에 한해서 사용을 해야하는 단점이 있지만, 리스트의 경우는 사이즈에 대한 한계가 없다. 이 점이 배열보다 앞선 장점이 아닐까 한다.

ArrayList

1) 내부적으로 배열을 사용하는 List 인터페이스의 구현체이며, 배열의 특징을 모두 가지고 있다.

2) ArrayList 객체 생성시 배열과 같이 사이즈를 지정할 수 있다. 이 사이즈는 내부 배열의 초기 사이즈이다. 만약 크기를 지정하지 않는다면 기본 배열크기인 10이 설정된다.

3) 배열이 꽉 차게 된다면, ArrayList는 자동적으로 사이즈가 더 큰 배열을 생성하여 원소들을 재할당한다. 하지만 새로운 배열을 생성후 복사를 하는 과정이 있어야 하기 때문에 시간이 소요되고 메모리도 소모하게 된다는 단점이 있다. 따라서 데이터의 크기가 크거나 예측이 되는 사이즈라면 초기 사이즈 설정을 해주는 것이 더 효율적이다.

4) 배열의 시작 위치나 중간 위치에 새로운 원소를 추가하려고 하면 공간을 만들기 위해 새로운 배열 생성 및 복사를 하여 이동시켜 주는 작업이 진행되어야 하므로 효율적이지 못하다. (역시 배열의 특징)

5) 또한 원소를 삭제해도 배열의 크기는 줄어들지 않으므로 메모리 사용 측면에서 효율적이지 못하다.

LinkedList

1) 다음 노드를 가리키는 참조값이 있으며, 다음 노드만 참조하므로 단방향의 특징을 가지는 List 구현체이다.

2) 리스트의 첫번째 위치나 중간 지점에 데이터를 추가/삭제하게 된다면 다음 노드를 가리키는 참조값만 변경하여 주면 되므로 ArrayList보다 추가/삭제에 효율적이다.

3) 데이터 삭제시 앞뒤의 참조값만 변경해주면 되며, 제외된 값은 GC에 의해 소멸되므로 ArrayList와 달리 메모리 사용 측면에서 효율적이다.

4) ArrayList와 같이 인덱스로 바로 검색을 할 수 없으며 앞에서부터 순회하여 검색하여야 한다.

※ 참고자료

- 자바 프로그래밍 면접, 이렇게 준비한다

버블정렬 (Bubble Sort)

1) 앞뒤로 데이터를 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다. 거품이 보글보글 올라가는 모습과 비슷하다.

2) 가장 구현하기 쉬우나 비효율적인 알고리즘이다.

3) 네이버 지식백과 [버블정렬] 참조

삽입정렬 (Insert Sort)

1) 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다.

2) 정렬된 위치에 삽입하는 방식은 LinkedList를 통해 쉽게 구현할 수 있다. 만약 ArrayList를 사용할 경우 삽입시 모든 원소를 한칸씩 이동하여야 하기 때문에 비효율적이고 속도가 느리다.

3) 네이버 지식백과 [삽입정렬] 참조

퀵정렬 (Quick Sort)

1) pivot값을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 가도록 하여 작은 값과 큰 값을 서로 분리해가며 정렬하는 방식이다.

2) 이 알고리즘은 재귀(recursive)적이다.

3) 버블정렬이나 삽입정렬보다 훨씬 효율적인 성능을 발휘한다.

4) 네이버 지식백과 [퀵정렬] 참조

병합정렬 (Merge Sort)

1) 분할정복(Divide and Conquer) 알고리즘이다.

2) 여러개의 데이터를 재귀적으로 반으로 나누어 정렬처리하며, 최종적으로 결합(Combine)을 하는 방식이다.

※ 참고자료

- 자바 프로그래밍 면접, 이렇게 준비한다